java类库中Arrays的排序算法探析（Object与泛型类型）

     在Arrays中关于基本类型如int，long，float等都在java类库中Arrays的排序算法探析（基础类型）做了一定分析，本篇主要关于Object类型的sort，以及之后的泛型sort。

 

直接查看源码中的方法定义及实现：

 

    public static void sort(Object[] a) {
        Object[] aux = (Object[])a.clone();
        mergeSort(aux, a, 0, a.length, 0);
    }


    public static void sort(Object[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);//验证参数是否合法
	Object[] aux = copyOfRange(a, fromIndex, toIndex);//创建待排序数组临时存储区
        mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
    }

 

由上可见，两个重载方法的具体实现指向了同一个具体实现，应该是个私有方法：

 

/**
     * Src is the source array that starts at index 0
     * Dest is the (possibly larger) array destination with a possible offset
     * low is the index in dest to start sorting
     * high is the end index in dest to end sorting
     * off is the offset to generate corresponding low, high in src
     */
    private static void mergeSort(Object[] src,
				  Object[] dest,
				  int low,
				  int high,
				  int off) {
	int length = high - low;

	// Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
			 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

 

        当然，如果能直接看代码一眼就完全明白的话，那到此就可以为止了。

先理一下流程：

1 如果待排序的数组大小小于设置的插入排序阈值，则直接采用插入排序解决；

2 如果不满足1，则将其一分为二，递归处理；这样经过多次递归，其实最终还是分段采用插入排序将其拆分为了N个有序的段；

3 到了这里，前面是多个分别有序的段，这里需要将其逐一连接起来，使其更大长度上有序，这一部分展示的就是：如果前一段的最后一个值（也就是前一段的最大值）小于紧挨着的后一个段的第一个值（也就是这一段的最小值），则这两段总体是有序的；

4 如果没有3那种理想状态，则需要我们来处理，这里处理的思想就是：前后两段逐一开始比较，小的先放，依次放第二小的，直到两段都为空；

5 3或4逐级返回，最终构成一个整体的有序数组。

 

再说泛型的排序：

 

 public static <T> void sort(T[] a, Comparator<? super T> c) {
	T[] aux = (T[])a.clone();
        if (c==null)
            mergeSort(aux, a, 0, a.length, 0);
        else
            mergeSort(aux, a, 0, a.length, 0, c);
    }

public static <T> void sort(T[] a, int fromIndex, int toIndex,
				Comparator<? super T> c) {
        rangeCheck(a.length, fromIndex, toIndex);
	T[] aux = (T[])copyOfRange(a, fromIndex, toIndex);
        if (c==null)
            mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
        else
            mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
    }

 可以看出来，泛型排序的处理过程几乎和对象数组的一模一样，值得注意的是，如果Comparator为null，则使用默认的Comparable接口的自然序。下面看具体调用的实现方法：

 

private static void mergeSort(Object[] src,
				  Object[] dest,
				  int low, int high, int off,
				  Comparator c) {
	int length = high - low;

	// Insertion sort on smallest arrays
	if (length < INSERTIONSORT_THRESHOLD) {
	    for (int i=low; i<high; i++)
		for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
		    swap(dest, j, j-1);
	    return;
	}

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off, c);
        mergeSort(dest, src, mid, high, -off, c);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (c.compare(src[mid-1], src[mid]) <= 0) {
           System.arraycopy(src, low, dest, destLow, length);
           return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

 仔细看来，无Comparator的实现和对象数组的事项没有任何差别，具有Comparator的也仅仅在比较使采取的是compare方法来决定数组顺序。

 

这个实现值得学习的有几点：

1 小规模的比较采取的是插入排序，这就避免了递归到一个数组只有一个元素那种情况，在小规模情况下，插入排序实现简单，效率也还可以（类库中设置的是7）；

2 在相邻两段的连接时，如果发现两个段的连接处构成正确顺序，则直接返回，减少了需要逐个比较元素重新插入一遍带来的性能影响；

3 无符号位运算取中间值，代替/；

4 对外接口与对内实现的独立，对外可能有多个接口，但内部实现其实是一样的，这样非常方便于后续调整和性能优化；

总体感觉就是这些方法的实现极大的优化了性能，并且给后续调整留下了空间，便于维护。

 

唯一感到有点不足的就是：

就是临时变量实在是有点多，刚开始难以理解~