Collections源码sort方法解读

首先看jdk1.5源码中的Collections.java中的sort方法源码:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
	(1):Object[] a = list.toArray();
	(2):Arrays.sort(a);    
	(3):ListIterator<T> i = list.listIterator();
	      for (int j=0; j<a.length; j++) {
	           i.next();
	           i.set((T)a[j]);
	       }
 }

这个方法的定义：<T extends Comparable<? super T>> 表示该方法中传递的泛型参数必须实现了Comparable中的compareTo(T o)方法，否则进行不了sort排序。

把这个方法细分为3个步骤：

（1）将list装换成一个对象数组

（2）将这个对象数组传递给Arrays类的sort方法（也就是说collections的sort其实本质是调用了Arrays.sort）

（3）通过（2）步骤排好序后指定list的iterator位置，返回一个排好序的list

 

然后进入Arrays.java查看sort源代码：

 

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

 很显然主要的排序方法是private static void mergeSort(Object[] src, Object[] dest,int low,int high, int off)

方法原理为：

  根据指定比较器产生的顺序对指定对象数组的指定范围进行排序。排序的范围从索引 low（包括）一直到索引 high（不包括）。（如果 low==high，则排序范围为空。）此范围内的所有元素都必须是通过指定比较器可相互比较的（也就是说，对于该范围中的任何 e1 和 e2 元素而言，c.compare(e1, e2) 不得抛出 ClassCastException）。因此也就是前面提到的必须实现Comparable中的compareTo(T o)方法。

 

最后进入sort核心排序算法mergeSort源代码：

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++];
        }
    }

 ①：这个方法接收Object[] src,Object[] dest两个数组，根据调用它的方法可以看出只需要对dest[]这个数组中的元素

       进行排序后，传递过来的List<T> list也即排好了序，src[]数组用来进行中介的，也即后面的方法需要调用（所以

      这两个数组必须区分作用），这里有个判断条件为length < INSERTIONSORT_THRESHOLD，

      INSERTIONSORT_THRESHOLD为Arrays的一个常量为7，它定义了如果数组元素小于7的话就直接用swap方法

      排序，提高了程序的执行效率。

 

 ②：当数组元素大于7的时候，程序先将数组拆分成低区间和高区间两个区间，再调用两个递归对这两个区间元素进行排

       序。在递归时还得判断已经划分的区间元素是否还多于7位，如果多于7位的话继续划分成两个区间，这样循环递归调

       用。在这个方法中，要特别注意src[]和dest[]的参数传递位置，调用递归方法时，是将src[]数组作为排序对象进行排

       序，src[]排序后，在通过③或④方法将dest[]数组依据src进行排序。最终达到List<T> list排序的结果。

 

  ③：如果初始元素个数大于等于7个的话（小于7的直接在①方法排好序返回）进过②方法后，只有两种情况：两个排好序

       的低区间和高区间。这个方法作用是：如果低区间列表中的最高元素小于高区间列表中的最低元素，则表明该次递归

       循环的区间段已经排好序，然后将这段数据复制到dest[]数组中。反之则进入方法④。

 

   ④：进入该方法表明该次递归循环的低区间的数字最高元素大于高区间列表中的最低元素，也就是说低区间的数组元素值

         都大于高区间的数组元素值，因此将src中的高区间元素和低区间元素调换放入dest数组中。这样一次递归循环就调

         用完毕，如果还有循环就继续排序下去，否则排序就已经完成。

 

 闲来无事写下这个排序的笔记，作为以后忘记时的参考！！