java类库中Arrays的排序算法探析（基础类型）

java.util.Arrays中有非常方便的array转换为list的方法，在 Java中List与Array的转换已经提及了，这里再介绍下其中的排序算法：

在java.util.Arrays中，排序（sort）部分占的篇幅最大，大量用到了重载，一种是根据参数类型的重载，也就是如：

 

public static void sort(long[] a)；
public static void sort(int[] a)；
……

 

 另外一种就是参数个数的重载，是和上面的相对应的：

 

public static void sort(int[] a)；
public static void sort(int[] a, int fromIndex, int toIndex)；

 

 其实在原理上都差不多，第一种重载是根据传入数组的类型选择对应的排序；第二种是根据传入的条件多少来决定，下面以

long[]的实现为例初步分析下过程：

 

 

public static void sort(long[] a) {
	sort1(a, 0, a.length);
    }

 

 其相同类型的重载为：

 

public static void sort(long[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
	sort1(a, fromIndex, toIndex-fromIndex);
    }

 

 可以看出，有起始限制的sort首先是验证传入的起始限界是否合法，而没有起始限制的sort默认就是全排序了：/**

     * Sorts the specified sub-array of longs into ascending order.
     */
    private static void sort1(long x[], int off, int len) {
	// Insertion sort on smallest arrays
        //如果待排序的范围很小，就选择插入排序，最是简洁,复杂度O(n2)
	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;
	}

	// Choose a partition element, v
        //选择快排，先找出一个分区值，这里有个小技巧，取一半时采用的是移位，比    有时候使用的len/2要好一点，预设为中间位置的值
	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，就是找9点点来确定更好的分区点，下面可以看出，这9个点是较均匀的插值，med3是计算x数组中后面三个位置上的哪个值在中间的一个方法
		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，找到分区值
	}
	long v = x[m];

	// Establish Invariant: v* (<v)* (>v)* v*，其实就是构建区域，和分区值相等的区域，所有元素都小于分区值的区域，所有元素都大于分区值的区域，和分区值相等的区域
	int a = off, b = a, c = off + len - 1, d = c;
	while(true) {
            //将与分区值相等的值移到头部，尾部为全部小于分区值的元素
	    while (b <= c && x[b] <= v) {
		if (x[b] == v)
		    swap(x, a++, b);
		b++;
	    }
           //将与分区值相等的值移到尾部，头部为全部大于分区值的元素
	    while (c >= b && x[c] >= v) {
		if (x[c] == v)
		    swap(x, c, d--);
		c--;
	    }
           //中止条件
	    if (b > c)
		break;
	    swap(x, b++, c--);
	}

	// Swap partition elements back to middle，交换，成为三个区域，分别为小于、等于和大于分区值的三个
	int s, n = off + len;
	s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
	s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

	// Recursively sort non-partition-elements，在两边的区域递归
	if ((s = b-a) > 1)
	    sort1(x, off, s);
	if ((s = d-c) > 1)
	    sort1(x, n-s, s);
    }

 

区域交换算法，简洁美：

 

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

 返回三个数中间数的算法，稍微有点晕：

 

/**
     * Returns the index of the median of the three indexed longs.
     */
    private static int med3(long 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));
    }

 关于long数组的排序就结束了！

其它基本类型如int, byte, char处理过程完全类似；

folat和double的后期处理也一样，只是会多一个初始化过程，这是由于浮点数的特性决定的，以float为例，在执行sort1之前的预处理：

 

private static void sort2(float a[], int fromIndex, int toIndex) {
        final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
        /*
         * The sort is done in three phases to avoid the expense of using
         * NaN and -0.0 aware comparisons during the main sort.避免事实上不需要比较，如NaN，-0.0和0.0事实上相等等
         */

        /*
         * Preprocessing phase:  Move any NaN's to end of array, count the
         * number of -0.0's, and turn them into 0.0's.预处理阶段，将NaN移到队尾，计算-0.0的个数并转换为0.0
         */
        int numNegZeros = 0;
        int i = fromIndex, n = toIndex;
        while(i < n) {
            if (a[i] != a[i]) {
		float swap = a[i];
                a[i] = a[--n];
                a[n] = swap;
            } else {
                if (a[i]==0 && Float.floatToIntBits(a[i])==NEG_ZERO_BITS) {
                    a[i] = 0.0f;
                    numNegZeros++;
                }
                i++;
            }
        }

        // Main sort phase: quicksort everything but the NaN's，主流程，和上面long的除了数组类型和元素类型不同之外完全相同
	sort1(a, fromIndex, n-fromIndex);

        // Postprocessing phase: change 0.0's to -0.0's as required。后处理阶段，将之前转换为0.0的归位为-0.0
        if (numNegZeros != 0) {
            int j = binarySearch0(a, fromIndex, n, 0.0f); // posn of ANY zero
            do {
                j--;
            } while (j>=0 && a[j]==0.0f);

            // j is now one less than the index of the FIRST zero
            for (int k=0; k<numNegZeros; k++)
                a[++j] = -0.0f;
        }
    }

 在传入对象数组的时候，采用的是归并排序，算法和上面的快排有所区别，后面探讨。