java源码中的数据结构 - 插入排序，快速排序 (附可供调试的源码)

java源码是学习数据结构的好材料，研究这些代码，能够更好的理解算法。

准备工作
java.util.Arrays是一个典型的工具类(构造函数修饰符为private)，该类提供了一组sort1()方法，分别用来可以比较的基本类型进行排序。

private static void sort1(int x[], int off, int len)
private static void sort1(long x[], int off, int len)
private static void sort1(byte x[], int off, int len)
private static void sort1(float x[], int off, int len)
...

仔细比较发现，这组方法除了传入数组的参数类型不同，方法内的代码几乎完全相同，产生这个问题的主要原因是jdk没有为基本类型提供泛型支持，考虑到效率问题，装箱在这里显然是不合适的。

在Arrays类中包含大量重复代码的方法不只sort1，还有swap，binarySearch等，不过这里确实也没有别的好方法，只能希望以后的版本编译器能够提供支持。

另外，这里还有一个需要说明的地方是double和float的比较，为了处理类似NaN, 0.0这样的情况，正确的比较方法应该是:

Double.compare(double1, doble2);
Float.compare(float1, float2);

而在Arrays类中，为了保证sort1的一致性，对double和float类型数组，先使用sort2方法把NaN, 0.0这样的数移到数组最后，再使用sort1方法对剩余部分排序，这部分功能可以参考sort2方法的源码。

private static void sort2(double a[], int fromIndex, int toIndex)
private static void sort2(float a[], int fromIndex, int toIndex)

算法分析
准备工作做完了，现在开始对算法本身进行分析，简便起见，只分析下面这个方法：

private static void sort1(int x[], int off, int len)

1 数组长度小于7时，使用插入排序

	// The part of code in sort1 method
	// Insertion sort on smallest arrays
	if (len < 7) {
		for (int i = off; i < len + off; i++)
			for (int j = i; j > off && x[j - 1] > x[j]; j--)
				swap(x, j, j - 1);
		return;
	}

说明：
印象中有本书说len<20时插入排序比较快，jdk选择的是len<7。
swap()方法用来交换数组中的两个变量。

2 数组长度大于等于7时，使用快速排序
快速排序的原理是首先选取一个元素v，然后把比v大和比v小的元素分别移到v的两边，最后再对v两边的数组分别进行排序。
这里使用的是平衡快排，即选择合适的v，使v尽量位于数组中间值，看看jdk怎么做的：

	// The part of code in sort1 method
	// Choose a partition element, v
	int m = off + (len >> 1); // Small arrays, middle element
	if (len > 7) {
		int l = off;
		int n = off + len - 1;
		if (len > 40) { // Big arrays, pseudomedian of 9
			int s = len / 8;
			l = med3(x, l, l + s, l + 2 * s);
			m = med3(x, m - s, m, m + s);
			n = med3(x, n - 2 * s, n - s, n);
		}
		m = med3(x, l, m, n); // Mid-size, med of 3
	}
	int v = x[m];

从代码可以看出，jdk分了三种情况:
2.1 len = 7
v取的是数组中间元素(x[3])

2.2 len > 7 && len <= 40
看看med3方法：

   
private static int med3(int x[], int a, int b, int c) {
	return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
		(x[b] > x[c] ? b : x[a] > x[c] ? c : a));
}

也就是取数组中三个位置值中处于中间的值。
所以这种情况v的取值是： 首，尾，中间元素中处于中间的值。

2.3 len > 40
仔细分析代码，可以发现，jdk取数组0, n/8, n/4, 3n/8, n/2, 5n/8, 3n/4, 7n/8, n位置的元素值进行运算，这个算法设计的非常巧妙  ，首先步长s=len/8，向右移三位就行了，速度快；其次，通过步长从数组中得到9个点，每3个为一组进行med3元素，产生的3个点再进行一次med3运算，就得到了v值，这样保证v的值尽可能的处于中间的值。

总结：
jdk中sort1排序使用了两种排序算法，并且根据数组的长度做了相应的优化，这是一个工程中比较实用的算法(看注释可以找到算法来源)。另外，附件是从jdk源码中拷贝出来的相关源码，有兴趣的可以自己研究。

评论

3 楼 coffeesweet 2010-03-17  

thank you

2 楼 robertliudeqiang 2010-03-15  

off你可以理解为：

输入一个数组，并不是对整个数组排序，而是从第off位开始，len长度个元素。

1 楼 coffeesweet 2010-03-15  

能问下sort1里的变量off是干什么的吗?