Arrays.sort和Collections.sort實現(xiàn)原理解析

    1、使用
    排序
    2、原理
    事實上Collections.sort方法底層就是調(diào)用的array.sort方法，而且不論是Collections.sort或者是Arrays.sort方法，跟蹤下源代碼吧，首先我們寫個demo

　　public static void main(String[] args) {

　　List strings = Arrays.asList("6", "1", "3", "1","2");

　　Collections.sort(strings);//sort方法在這里

　　for (String string : strings) {

　　System.out.println(string);

　　}

　　}

　　簡單得不能再簡單的方法了，讓我們一步步跟蹤

　　OK，往下面看，發(fā)現(xiàn)collections.sort方法調(diào)用的list.sort

　　然后跟蹤一下，list里面有個sort方法，但是list是一個接口，肯定是調(diào)用子類里面的實現(xiàn)，這里我們demo使用的是一個Arrays.asList方法，所以事實上我們的子類就是arraylist了。OK，看arraylist里面sort實現(xiàn)，選擇第一個，為什么不選擇第二個呢?(可以看二樓評論，解答得很正確，簡單說就是用Arrays.sort創(chuàng)建的ArrayList對象)

　　OK，發(fā)現(xiàn)里面調(diào)用的Arrays.sort(a, c); a是list,c是一個比較器，我們來看一下這個方法

　　我們沒有寫比較器，所以用的第二項，LegacyMergeSort.userRequested這個bool值是什么呢?

　　跟蹤這個值，我們發(fā)現(xiàn)有這樣的一段定義：

　　> Old merge sort implementation can be selected (for

　　> compatibility with broken comparators) using a system property.

　　> Cannot be a static boolean in the enclosing class due to

　　> circular dependencies. To be removed in a future release.

　　反正是一種老的歸并排序，不用管了現(xiàn)在默認(rèn)是關(guān)的

　　OK，我們走的是sort(a)這個方法，接著進(jìn)入這個

　　接著看我們重要的sort方法

　　static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {

　　assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

　　int nRemaining = hi - lo;

　　if (nRemaining < 2)

　　return; // array的大小為0或者1就不用排了

　　// 當(dāng)數(shù)組大小小于MIN_MERGE(32)的時候，就用一個"mini-TimSort"的方法排序，jdk1.7新加

　　if (nRemaining < MIN_MERGE) {

　　//這個方法比較有意思，其實就是將我們最長的遞減序列，找出來，然后倒過來

　　int initRunLen = countRunAndMakeAscending(a, lo, hi);

　　//長度小于32的時候，是使用binarySort的

　　binarySort(a, lo, hi, lo + initRunLen);

　　return;

　　}

　　//先掃描一次array，找到已經(jīng)排好的序列，然后再用剛才的mini-TimSort，然后合并，這就是TimSort的核心思想

　　ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);

　　int minRun = minRunLength(nRemaining);

　　do {

　　// Identify next run

　　int runLen = countRunAndMakeAscending(a, lo, hi);

　　// If run is short, extend to min(minRun, nRemaining)

　　if (runLen < minRun) {

　　int force = nRemaining <= minRun ? nRemaining : minRun;

　　binarySort(a, lo, lo + force, lo + runLen);

　　runLen = force;

　　}

　　// Push run onto pending-run stack, and maybe merge

　　ts.pushRun(lo, runLen);

　　ts.mergeCollapse();

　　// Advance to find next run

　　lo += runLen;

　　nRemaining -= runLen;

　　} while (nRemaining != 0);

　　// Merge all remaining runs to complete sort

　　assert lo == hi;

　　ts.mergeForceCollapse();

　　assert ts.stackSize == 1;

　　}

　　回到5，我們可以看到當(dāng)我們寫了比較器的時候就調(diào)用了TimSort.sort方法，源碼如下

　　static void sort(T[] a, int lo, int hi, Comparator c,

　　T[] work, int workBase, int workLen) {

　　assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;

　　int nRemaining = hi - lo;

　　if (nRemaining < 2)

　　return; // Arrays of size 0 and 1 are always sorted

　　// If array is small, do a "mini-TimSort" with no merges

　　if (nRemaining < MIN_MERGE) {

　　int initRunLen = countRunAndMakeAscending(a, lo, hi, c);

　　binarySort(a, lo, hi, lo + initRunLen, c);

　　return;

　　}

　　/**

　　* March over the array once, left to right, finding natural runs,

　　* extending short natural runs to minRun elements, and merging runs

　　* to maintain stack invariant.

　　*/

　　TimSort ts = new TimSort<>(a, c, work, workBase, workLen);

　　int minRun = minRunLength(nRemaining);

　　do {

　　// Identify next run

　　int runLen = countRunAndMakeAscending(a, lo, hi, c);

　　// If run is short, extend to min(minRun, nRemaining)

　　if (runLen < minRun) {

　　int force = nRemaining <= minRun ? nRemaining : minRun;

　　binarySort(a, lo, lo + force, lo + runLen, c);

　　runLen = force;

　　}

　　// Push run onto pending-run stack, and maybe merge

　　ts.pushRun(lo, runLen);

　　ts.mergeCollapse();

　　// Advance to find next run

　　lo += runLen;

　　nRemaining -= runLen;

　　} while (nRemaining != 0);

　　// Merge all remaining runs to complete sort

　　assert lo == hi;

　　ts.mergeForceCollapse();

　　assert ts.stackSize == 1;

　　}

　　和上面的sort方法是一樣的，其實也就是TimSort的源代碼

　　3、總結(jié)

　　不論是Collections.sort方法或者是Arrays.sort方法，底層實現(xiàn)都是TimSort實現(xiàn)的，這是jdk1.7新增的，以前是歸并排序。TimSort算法就是找到已經(jīng)排好序數(shù)據(jù)的子序列，然后對剩余部分排序，然后合并起來（文章轉(zhuǎn)載于csdn.net/u011410529/article/details/56668545）