Collections源码sort方法解读

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

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数组中。这样一次递归循环就调

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

?

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

?

?

?

?

?