今后会发布一些分析jdk源码的文章,分析jdk源码有助于更好的理解java,这里也记录一下自己的学习过程,怕以后遗忘。
这次jdk的源码分析从Arrays.sort开始,为什么从它开始呢?凡是学过或者打算面试计算机岗的人员,都不可避免的遇到各种数据结构和算法的问题,而往往这些问题最基本的就是课本里最经典的几大排序算法,以前自己也从来没想过jdk中是怎样实现的,所以特地看了一下Arrays.sort的源代码。
Arrays.sort对外封装的很好,各种数据类型只要直接调用就可以了,以前一直认为里面的实现逻辑是一样的,但是看了源码发现 确实不一样,源码中对于输入的数据做了以下的判断:
对于7种基本数据类型long,int,short,double,float,byte,char,源码给出的排序方法是快速排序
其中主要用到的是sort1方法。
其中,double和float类型,源码还特别做出来一些特别处理,调用sort2方法,但是在sort2中,做了特殊处理后,依然调用了sort1方法,具体的会在在后续的文章中会讲到。

而对于object类型,即复杂的对象类型,源码给出的排序方法是归并排序,而且对于object的比较来说里面涉及到了,clone,comparable等具体知识,会在后续的文章中讲到。
这是为什么区分基本数据类型和object呢?
主要是因为,快速排序不稳定,归并排序稳定,对于基本数据类型来说稳定不稳定无所谓,但是对于复杂对象来说,稳定性就很重要了。至于说稳定性有什么用呢,以前一直觉得没什么用,后来才知道,稳定排序的主要好处是,对于复杂对象来说,往往排序的关键字不只一个,可能会有好几个可以用来排序的关键字,假设按照key1排序后,有需求还要按照key2排序,但是希望key2相同的对象的顺序不变,这就要求key2必须是稳定的,否则可能会改变原来相等的对象在key1排序后的前后位置,举一个简单的例子,拷贝自网友:

一个班的学生已经按照学号大小排好序了,我现在要求按照年龄从小到大再排个序,如果年龄相同的,必须按照学号从小到大的顺序排列。
那么问题来了,你选择的年龄排序方法如果是不稳定的,是不是排序完了后年龄相同的一组学生学号就乱了,你就得把这组年龄相同的学生再按照学号拍一遍。如果是稳定的排序算法,我就只需要按照年龄排一遍就好了。

另外不管是快速排序还是归并排序,说到底都是递归性的排序,也就是一步一步的降低数据的长度从而实现排序,但是jdk源码中并不是降低到1,而是当判断出数组长度小于7的时候,就直接调用的简单插入排序了。这也从侧面反映出了,当数组长度较小是,简单插入排序的效果更好,因为虽然递归性排序(归并及快排)时间复杂度低,但是会有递归调用的开销,而对于数量较小的数据来说,这种开销显然比多来几次比较要大,所以jdk源码在数量小于7时,果断的调用了插入排序,至于为什么是7而不是6或8,我想这应该是经验值。

在后续的代码中,会常出现以下几个常用的方法,下面贴出,方法较为简单,代码里有注释。

// 取x[a],x[b],x[d]中中间值对应的下标
	public static int med3(int x[], int a, int b, int d) {
		return (x[a] < x[b] ? (x[b] < x[d] ? b : x[a] < x[d] ? d : a)
				: (x[b] > x[d] ? b : x[a] > x[d] ? d : a));
	}

	// 交换x[a],x[b]
	public static void swap(int[] x, int a, int b) {
		int t = x[a];
		x[a] = x[b];
		x[b] = t;
	}

	/**
	 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
	 */
	public static void vecswap(int x[], int a, int b, int n) {
		for (int i = 0; i < n; i++, a++, b++)
			swap(x, a, b);
	}

其中med3是用来取三个数中间的中数对应的小标的,swap是交换,这个大家最常见,vecswap是批量交换,即Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].

系列文章目录如下:

  1. jdk源码分析——Arrays.sort(1)_概述

  2. jdk源码分析——Arrays.sort(2)_快速排序的运用与优化

  3. jdk源码分析——Arrays.sort(3)_Double/float浮点数在快速排序中的特殊处理

  4. jdk源码分析——Arrays.sort(4)_复杂对象采用归并排序

jdk源码分析——Arrays.sort(4)_复杂对象采用归并排序

前面的博文介绍了基本数据类型在Arrsys.sort中是采用快速排序来处理的,具体参考前面的博文。而对于复杂对象(Object)来说,jdk Arrays.sort源码中是采用归...

阅读全文

jdk源码分析——Arrays.sort(3)_Double/float浮点数在快速排序中的特殊处理

前一篇文章    jdk源码分析——Arrays.sort(2)_快速排序的运用与优化  已经介绍过了对于int等基本数据类型 Arrays.sort中是如何进行排序的,这篇文章来介绍一下...

阅读全文

jdk源码分析——Arrays.sort(2)_快速排序的运用与优化

针对非double和float类型的基本类型数组来说(文章中用int来举例),Arrays.sort直接进行快速排序,jdk源代码中的快速排序与我们平常看到的快速排序是不一样...

阅读全文

欢迎留言