java.lang.Object java.util.Collections簡(jiǎn)介

此類僅包含操作或返回集合的靜態(tài)方法趁仙。
它包含多樣的對(duì)集合進(jìn)行操作的算法壮啊，“包裝器”疲恢，返回由指定集合支持的新集合爹袁，以及其他一些細(xì)碎功能炊琉。

如果提供給它們的集合或類對(duì)象為null，則此類的方法都拋出NullPointerException

該類中包含的多態(tài)算法的文檔通常包括實(shí)現(xiàn)的簡(jiǎn)要說(shuō)明 厅翔。 這些描述應(yīng)被視為實(shí)現(xiàn)說(shuō)明 乖坠，而不是說(shuō)明的一部分 。 只要規(guī)范本身得到遵守刀闷，實(shí)現(xiàn)者就可以隨意替代其算法熊泵。 （例如，sort使用的算法不一定是一個(gè)mergesort甸昏，但它必須是穩(wěn)定的 算法）

如果集合不支持適當(dāng)?shù)耐蛔冊(cè)Z(yǔ)顽分，例如set方法，則該類中包含的“破壞性”算法施蜜，即修改其操作的集合的算法被指定為拋出UnsupportedOperationException卒蘸。 如果調(diào)用對(duì)集合沒有影響，這些算法可能但不是必須拋出此異常翻默。 例如缸沃，在已經(jīng)排序的不可修改列表上調(diào)用sort方法可以拋出UnsupportedOperationException

Collections的sort方法代碼：

public static <T> void sort(List<T> list, Comparator<? super T> c) {
        list.sort(c);
    }
public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
    }

<T extends Comparable<? super T>> 表示該方法中傳遞的泛型參數(shù)必須實(shí)現(xiàn)了Comparable中的compareTo(T o)方法，否則進(jìn)行不了sort排序
其sort方法實(shí)現(xiàn)都委托給了java.util.List接口的默認(rèn)實(shí)現(xiàn)的sort方法

default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

方法細(xì)節(jié)奏：

（1）將list轉(zhuǎn)換成一個(gè)Object數(shù)組
（2）將這個(gè)Object數(shù)組傳遞給Arrays類的sort方法（也就是說(shuō)Collections的sort本質(zhì)是調(diào)用了Arrays.sort）
（3）完成排序之后修械，再一個(gè)一個(gè)地趾牧，把Arrays的元素復(fù)制到List中

public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

注意到sort有一個(gè)條件判斷，

• 當(dāng)LegacyMergeSort.userRequested==true肯污，采用legacyMergeSort
• 否則采用ComparableTimSort

LegacyMergeSort.userRequested的字面意思大概就是“用戶請(qǐng)求傳統(tǒng)歸并排序”翘单，這個(gè)分支調(diào)用的是與jdk5相同的方法來(lái)實(shí)現(xiàn)功能。

ComparableTimSort是改進(jìn)后的歸并排序蹦渣，對(duì)歸并排序在已經(jīng)反向排好序的輸入時(shí)表現(xiàn)為O(n^2)的特點(diǎn)做了特別優(yōu)化哄芜。對(duì)已經(jīng)正向排好序的輸入減少回溯。對(duì)兩種情況（一會(huì)升序柬唯，一會(huì)降序）的輸入處理比較好（摘自百度百科）认臊。

• legacyMergeSort代碼：

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

• mergeSort代碼

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

①：對(duì)dest[]排序，傳遞過(guò)來(lái)的List<T> list也就排好了序权逗，src[]數(shù)組用做中介美尸，即后面的方法需要調(diào)用，這里有個(gè)判斷條件為length < INSERTIONSORT_THRESHOLD
INSERTIONSORT_THRESHOLD為Arrays的一個(gè)常量7斟薇，它定義了如果數(shù)組元素小于7用插入排序
②：當(dāng)數(shù)組元素不小于7，
* 先將數(shù)組拆分成低區(qū)間和高區(qū)間
* 再調(diào)用兩個(gè)遞歸對(duì)區(qū)間元素排序恕酸。在遞歸時(shí)注意還會(huì)判斷已劃分區(qū)間元素是否還不少于7堪滨，如果不小于7繼續(xù)劃分成兩個(gè)區(qū)間，這樣循環(huán)遞歸調(diào)用

特別注意src[]和dest[]的參數(shù)位置蕊温，調(diào)用遞歸時(shí)袱箱，是將src[]數(shù)組作為排序?qū)ο筮M(jìn)行排序遏乔，src[]排序后，在通過(guò)③或④方法將dest[]數(shù)組依據(jù)src進(jìn)行排序发笔。最終達(dá)到List<T> list排序的結(jié)果盟萨。

③：如果初始元素個(gè)數(shù)不小于7進(jìn)過(guò)②方法后，只有兩種情況：兩個(gè)排好序的低區(qū)間和高區(qū)間了讨。這個(gè)方法作用是：

• 如果低區(qū)間列表中的最高元素小于高區(qū)間列表中的最低元素捻激，則表明該次遞歸循環(huán)的區(qū)間段已經(jīng)排好序，然后將這段數(shù)據(jù)復(fù)制到dest[]數(shù)組中前计。
• 反之則進(jìn)入方法④

④：進(jìn)入該方法表明該次遞歸循環(huán)的左區(qū)間最大元素大于右區(qū)間最小元素胞谭，也就是說(shuō)左區(qū)間的數(shù)組元素值都大于高區(qū)間的數(shù)組元素值，因此將src中的高區(qū)間元素和低區(qū)間元素調(diào)換放入dest數(shù)組中男杈。這樣一次遞歸循環(huán)就調(diào)用完畢丈屹，如果還有循環(huán)就繼續(xù)排序下去，否則排序就已經(jīng)完成伶棒。

TimSort.sort()

 /*
     * The next method (package private and static) constitutes the
     * entire API of this class.
     */

    /**
     * Sorts the given range, using the given workspace array slice
     * for temp storage when possible. This method is designed to be
     * invoked from public methods (in class Arrays) after performing
     * any necessary array bounds checks and expanding parameters into
     * the required forms.
     *
     * @param a the array to be sorted
     * @param lo the index of the first element, inclusive, to be sorted
     * @param hi the index of the last element, exclusive, to be sorted
     * @param c the comparator to use
     * @param work a workspace array (slice)
     * @param workBase origin of usable space in work array
     * @param workLen usable size of work array
     * @since 1.8
     */
    static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> 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
        //待排序的個(gè)數(shù)如果小于32（MIN_MERGE）旺垒，使用不歸并的迷你版timsort二分排序
        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<T> 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);
                 // 對(duì)[lo,lo+force]排好序了，當(dāng)然下次的 run length 長(zhǎng)度是force
                runLen = force;
            }

            // 把這次run的基點(diǎn)位置和長(zhǎng)度壓棧肤无，必要時(shí)合并
            ts.pushRun(lo, runLen);
            // TimSort持有數(shù)組a先蒋，根據(jù)區(qū)間來(lái)合并，從而達(dá)到排序
            ts.mergeCollapse();

            // Advance to find next run 準(zhǔn)備下一輪的部分排序
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);

        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }

（1）傳入的待排序數(shù)組若小于閾值MIN_MERGE（Java實(shí)現(xiàn)中為32舅锄，Python實(shí)現(xiàn)中為64）鞭达，則調(diào)用 binarySort，這是一個(gè)不包含合并操作的 mini-TimSort皇忿。

a) 從數(shù)組開始處找到一組連接升序或嚴(yán)格降序（找到后翻轉(zhuǎn)）的數(shù)
b) Binary Sort：使用二分查找的方法將后續(xù)的數(shù)插入之前的已排序數(shù)組畴蹭，binarySort 對(duì)數(shù)組 a[lo:hi] 進(jìn)行排序，并且a[lo:start] 是已經(jīng)排好序的鳍烁。算法的思路是對(duì)a[start:hi] 中的元素叨襟，每次使用binarySearch 為它在 a[lo:start] 中找到相應(yīng)位置，并插入幔荒。

（2）開始真正的TimSort過(guò)程：

（2.1） 選取minRun大小糊闽，之后待排序數(shù)組將被分成以minRun大小為區(qū)塊的一塊塊子數(shù)組

a) 如果數(shù)組大小為2的N次冪，則返回16（MIN_MERGE / 2）
b) 其他情況下爹梁，逐位向右位移（即除以2）右犹，直到找到介于16和32間的一個(gè)數(shù)

• minRun

private static int minRunLength(int n) {  
        assert n >= 0;  
        int r = 0;      // Becomes 1 if any 1 bits are shifted off  
        while (n >= MIN_MERGE) {  
            r |= (n & 1);  
            n >>= 1;  
        }  
        return n + r;  
}

這個(gè)函數(shù)根據(jù) n 計(jì)算出對(duì)應(yīng)的 natural run 的最小長(zhǎng)度。MIN_MERGE 默認(rèn)為32姚垃，如果n小于此值念链，那么返回n 本身。否則會(huì)將 n 不斷地右移，直到少于 MIN_MERGE掂墓，同時(shí)記錄一個(gè) r 值谦纱，r 代表最后一次移位n時(shí)，n最低位是0還是1君编。 最后返回 n + r跨嘉，這也意味著只保留最高的 5 位，再加上第六位吃嘿。

（2.2）do-while

（2.2.1）找到初始的一組升序數(shù)列祠乃，countRunAndMakeAscending 會(huì)找到一個(gè)run ，這個(gè)run 必須是已經(jīng)排序的唠椭，并且函數(shù)會(huì)保證它為升序跳纳，也就是說(shuō)，如果找到的是一個(gè)降序的贪嫂，會(huì)對(duì)其進(jìn)行翻轉(zhuǎn)寺庄。

（2.2.2）若這組區(qū)塊大小小于minRun，則將后續(xù)的數(shù)補(bǔ)足力崇，利用binarySort 對(duì) run 進(jìn)行擴(kuò)展斗塘，并且擴(kuò)展后，run 仍然是有序的亮靴。

（2.2.3）當(dāng)前的 run 位于 a[lo:runLen] 馍盟，將其入棧ts.pushRun(lo, runLen);//為后續(xù)merge各區(qū)塊作準(zhǔn)備：記錄當(dāng)前已排序的各區(qū)塊的大小

（2.2.4）對(duì)當(dāng)前的各區(qū)塊進(jìn)行merge，merge會(huì)滿足以下原則（假設(shè)X茧吊，Y贞岭，Z為相鄰的三個(gè)區(qū)塊）：

a) 只對(duì)相鄰的區(qū)塊merge
b) 若當(dāng)前區(qū)塊數(shù)僅為2，If X<=Y搓侄，將X和Y merge
b) 若當(dāng)前區(qū)塊數(shù)>=3瞄桨，If X<=Y+Z，將X和Y merge讶踪，直到同時(shí)滿足X>Y+Z和Y>Z

由于要合并的兩個(gè) run 是已經(jīng)排序的芯侥，所以合并的時(shí)候，有會(huì)特別的技巧乳讥。假設(shè)兩個(gè) run 是 run1,run2 柱查，先用 gallopRight在 run1 里使用 binarySearch 查找run2 首元素 的位置k, 那么 run1 中 k 前面的元素就是合并后最小的那些元素。然后云石，在run2 中查找run1 尾元素 的位置 len2 唉工，那么run2 中 len2 后面的那些元素就是合并后最大的那些元素。最后汹忠，根據(jù)len1 與len2 大小酵紫，調(diào)用mergeLo 或者 mergeHi 將剩余元素合并告嘲。

（2.2.5） 重復(fù)2.2.1 ~ 2.2.4错维，直到將待排序數(shù)組排序完
（2.2.6） Final Merge：如果此時(shí)還有區(qū)塊未merge奖地，則合并它們

（3）示例

注意：為了演示方便，我將TimSort中的minRun直接設(shè)置為2赋焕，否則我不能用很小的數(shù)組演示参歹。。隆判。同時(shí)把MIN_MERGE也改成2（默認(rèn)為32）犬庇，這樣避免直接進(jìn)入binary sort。

初始數(shù)組為[7,5,1,2,6,8,10,12,4,3,9,11,13,15,16,14]
=> 尋找連續(xù)的降序或升序序列 (2.2.1)侨嘀，同時(shí)countRunAndMakeAscending 函數(shù)會(huì)保證它為升序
[1,5,7] [2,6,8,10,12,4,3,9,11,13,15,16,14]

=> 入棧 (2.2.3)
當(dāng)前的棧區(qū)塊為[3]

=> 進(jìn)入merge循環(huán) (2.2.4)
do not merge因?yàn)闂４笮H為1

=> 尋找連續(xù)的降序或升序序列 (2.2.1)
[1,5,7] [2,6,8,10,12] [4,3,9,11,13,15,16,14]

=> 入棧 (2.2.3)
當(dāng)前的棧區(qū)塊為[3, 5]

=> 進(jìn)入merge循環(huán) (2.2.4)
merge因?yàn)閞unLen[0]<=runLen[1]

1. gallopRight：尋找run1的第一個(gè)元素應(yīng)當(dāng)插入run0中哪個(gè)位置（”2”應(yīng)當(dāng)插入”1”之后）臭挽，然后就可以忽略之前run0的元素（都比run1的第一個(gè)元素小）
2. gallopLeft：尋找run0的最后一個(gè)元素應(yīng)當(dāng)插入run1中哪個(gè)位置（”7”應(yīng)當(dāng)插入”8”之前）咬腕，然后就可以忽略之后run1的元素（都比run0的最后一個(gè)元素大） 這樣需要排序的元素就僅剩下[5,7] [2,6]欢峰，然后進(jìn)行mergeLow
   完成之后的結(jié)果：
   [1,2,5,6,7,8,10,12] [4,3,9,11,13,15,16,14]

=> 入棧 (2.2.3)
當(dāng)前的棧區(qū)塊為[8]
退出當(dāng)前merge循環(huán)因?yàn)闂Ｖ械膮^(qū)塊僅為1

=> 尋找連續(xù)的降序或升序序列 (2.2.1)
[1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16,14]
=> 入棧 (2.2.3)
當(dāng)前的棧區(qū)塊大小為[8,2]

=> 進(jìn)入merge循環(huán) (2.2.4)
do not merge因?yàn)閞unLen[0]>runLen[1]

=> 尋找連續(xù)的降序或升序序列 (2.2.1)
[1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16] [14]

=> 入棧 (2.2.3)
當(dāng)前的棧區(qū)塊為[8,2,5]

=>
do not merege run1與run2因?yàn)椴粷M足runLen[0]<=runLen[1]+runLen[2]
merge run2與run3因?yàn)閞unLen[1]<=runLen[2]

1. gallopRight：發(fā)現(xiàn)run1和run2就已經(jīng)排好序
   完成之后的結(jié)果：
   [1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]

=> 入棧 (2.2.3)
當(dāng)前入棧的區(qū)塊大小為[8,7]
退出merge循環(huán)因?yàn)閞unLen[0]>runLen[1]

=> 尋找連續(xù)的降序或升序序列 (2.2.1)
最后只剩下[14]這個(gè)元素：[1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]

=> 入棧 (2.2.3)
當(dāng)前入棧的區(qū)塊大小為[8,7,1]

=> 進(jìn)入merge循環(huán) (2.2.4)
merge因?yàn)閞unLen[0]<=runLen[1]+runLen[2]
因?yàn)閞unLen[0]>runLen[2]，所以將run1和run2先合并涨共。（否則將run0和run1先合并）

1. gallopRight & 2) gallopLeft
   這樣需要排序的元素剩下[13,15] [14]纽帖，然后進(jìn)行mergeHigh
   完成之后的結(jié)果：
   [1,2,5,6,7,8,10,12] [3,4,9,11,13,14,15,16] 當(dāng)前入棧的區(qū)塊為[8,8]

=>
繼續(xù)merge因?yàn)閞unLen[0]<=runLen[1]

1. gallopRight & 2) gallopLeft
   需要排序的元素剩下[5,6,7,8,10,12] [3,4,9,11]，然后進(jìn)行mergeHigh
   完成之后的結(jié)果：
   [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 當(dāng)前入棧的區(qū)塊大小為[16]

=>
不需要final merge因?yàn)楫?dāng)前棧大小為1

=>
結(jié)束

先看看run的定義举反，翻譯成趨向懊直？一個(gè)run是從數(shù)組給定位置開始的最長(zhǎng)遞增或者遞減序列的長(zhǎng)度，為了得到穩(wěn)定的歸并排序火鼻，這里的降序中使用的“>”室囊，不包含"=",保證stability。原注釋是：

[圖片上傳失敗...(image-619f33-1537956194712)]

具體計(jì)算最長(zhǎng)run長(zhǎng)度：

private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
                                                Comparator<? super T> c) {
    assert lo < hi;
    int runHi = lo + 1;
    if (runHi == hi)
        return 1;

    // Find end of run, and reverse range if descending
    if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
        while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
            runHi++;
        // 如果是遞減序列魁索，那么就得到最長(zhǎng)的融撞，然后逆序
        reverseRange(a, lo, runHi);
    } else {                              // Ascending
        while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
            runHi++;
    }

    return runHi - lo;  // 這個(gè)run的最大長(zhǎng)度
}

舉個(gè)例子吧，如下圖：

排序小數(shù)組

獲得初始的run長(zhǎng)度后蛾默，調(diào)用 binarySort(a, lo, hi, lo + initRunLen, c)懦铺，binarySort 當(dāng)然不會(huì)浪費(fèi)時(shí)間再去排序在求run長(zhǎng)度時(shí)已經(jīng)排好序的頭部（lo->start），然后進(jìn)行二分插入排序支鸡。

binarySort要做的就是把后續(xù)的元素依次插入到屬于他們的位置冬念，基點(diǎn)就是已經(jīng)排好序的子數(shù)組（如果沒有的子數(shù)組就是首元素），把當(dāng)前操作的元素稱為pivot牧挣，通過(guò)二分查找急前，找到自己應(yīng)該插入的位置（達(dá)到的狀態(tài)是left==right），找到位置后瀑构，就要為pivot的插入騰出空間裆针，所以需要元素的移動(dòng)刨摩，代碼中如果移動(dòng)少于兩個(gè)元素就直接操作，否則調(diào)用System.arraycopy()世吨，最后插入我們的pivot到正確的位置澡刹。

這樣我想到了之前在學(xué)習(xí)排序的時(shí)候的幾個(gè)算法，其中有個(gè)說(shuō)法是耘婚，對(duì)于小數(shù)組的排序使用插入排序罢浇，大數(shù)組的時(shí)候使用快排，歸并排序之類的沐祷。

/**
* Sorts the specified portion of the specified array using a binary
* insertion sort.  This is the best method for sorting small numbers
* of elements.  It requires O(n log n) compares, but O(n^2) data
* movement (worst case).
*
*/
private static <T> void binarySort(T[] a, int lo, int hi, int start,
    Comparator<? super T> c) {
    assert lo <= start && start <= hi;
    if (start == lo)
        start++;
    for ( ; start < hi; start++) {
        T pivot = a[start];

        // Set left (and right) to the index where a[start] (pivot) belongs
        int left = lo;
        int right = start;
        assert left <= right;
        /*
         * Invariants:  排序過(guò)程的不變量
         *   pivot >= all in [lo, left).
         *   pivot <  all in [right, start).
         */
        while (left < right) {
            int mid = (left + right) >>> 1; 
             // 二分查找找到屬于pivot的位置
            if (c.compare(pivot, a[mid]) < 0)
                right = mid;
            else
                left = mid + 1;
        }
        assert left == right;

        /*
         * The invariants still hold: pivot >= all in [lo, left) and
         * pivot < all in [left, start), so pivot belongs at left.  Note
         * that if there are elements equal to pivot, left points to the
         * first slot after them -- that's why this sort is stable.
         * Slide elements over to make room for pivot.
         */
        int n = start - left;  // The number of elements to move
        // Switch is just an optimization for arraycopy in default case
        switch (n) { // 移動(dòng)元素
            case 2:  a[left + 2] = a[left + 1];
            case 1:  a[left + 1] = a[left];
            break;
            default: System.arraycopy(a, left, a, left + 1, n);
        }
        // 屬于自己的位置
        a[left] = pivot;
    }
}

排序大數(shù)組

接下來(lái)看如果待排序的個(gè)數(shù)>=32時(shí)的過(guò)程嚷闭，首先弄明白minRunLength得到的是什么。注釋很清楚赖临，雖然理論基礎(chǔ)不理解胞锰。

* Roughly speaking, the computation is:
*
*  If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
*  Else if n is an exact power of 2, return MIN_MERGE/2.
*  Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
*   is close to, but strictly less than, an exact power of 2.

如果還是很抽象的話，從32到100得到的min run length如下兢榨，可以直觀的體會(huì)下：

16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,16,17,17,17,17,18,18,18,18,19,19,19,19,20,20,20,20,21,21,21,21,22,22,22,22,23,23,23,23,24,24,24,24,25,25,25

得到 minRun 之后嗅榕，取 minRun 和 nRemaining 的最小值作為這次要排序的序列，初始的有序數(shù)組和前面情況（1）的獲取方式一樣色乾，然后做一次二分插入排序誊册，現(xiàn)在有序序列的長(zhǎng)度是force，這一部分排好序之后暖璧，把本次run的起始位置和長(zhǎng)度存入一個(gè)stack中（兩個(gè)數(shù)組）案怯，后續(xù)就是根據(jù)這些區(qū)間完成排序的。每次push之后就是要進(jìn)行合并檢查澎办，也就是說(shuō)相鄰的區(qū)間能合并的就合并嘲碱，具體的：

/**
 * Examines the stack of runs waiting to be merged and merges adjacent runs
 * until the stack invariants are reestablished:
 *
 *     1\. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
 *     2\. runLen[i - 2] > runLen[i - 1]
 *
 * This method is called each time a new run is pushed onto the stack,
 * so the invariants are guaranteed to hold for i < stackSize upon
 * entry to the method.
 */
private void mergeCollapse() {
    while (stackSize > 1) {
        int n = stackSize - 2;
        if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
            if (runLen[n - 1] < runLen[n + 1])
                n--;
            mergeAt(n);
        } else if (runLen[n] <= runLen[n + 1]) {
            mergeAt(n);
        } else {
            break; // Invariant is established
        }
    }
}

我的理解下，雖然每次run之后都能進(jìn)行合并局蚀，但是為了減少合并帶來(lái)的開銷麦锯，找到了某種規(guī)則，可以在某些條件下避免合并琅绅。接下來(lái)看看具體合并時(shí)的動(dòng)作扶欣。

合并有序區(qū)間

有一種情況是：如果前一個(gè)區(qū)間的長(zhǎng)度小于當(dāng)前區(qū)間長(zhǎng)度，就進(jìn)行merge千扶，每個(gè)區(qū)間是一個(gè)排好序的數(shù)組料祠，現(xiàn)在要合并第i和i+1個(gè)區(qū)間。

首先把 run length更新到 ruLen[i] 中澎羞，刪掉 i+1 的run信息髓绽；接下來(lái)定位區(qū)間2的最小元素在有序區(qū)間1的插入位置，更新區(qū)間1的 run base 和 run length,稱更新后的為區(qū)間1'; 然后查找區(qū)間1'的最大元素在區(qū)間2的正確定位妆绞；此時(shí)此刻這個(gè)數(shù)組已經(jīng)得到了有效的劃分顺呕，如下圖枫攀，只需要合并[base1,len1]和[base2,len2]就可以了，其他段已經(jīng)在正確位置株茶。

private void mergeAt(int i) {
    assert stackSize >= 2;
    assert i >= 0;
    assert i == stackSize - 2 || i == stackSize - 3;

    int base1 = runBase[i];
    int len1 = runLen[i];
    int base2 = runBase[i + 1];
    int len2 = runLen[i + 1];
    assert len1 > 0 && len2 > 0;
    assert base1 + len1 == base2;

    /*
     * （1） 合并了 i,i+1, 把i+2的信息移動(dòng)到之前i+1的位置来涨，就是刪除i+1
     * Record the length of the combined runs; if i is the 3rd-last
     * run now, also slide over the last run (which isn't involved
     * in this merge).  The current run (i+1) goes away in any case.
     */
    runLen[i] = len1 + len2;
    if (i == stackSize - 3) { 
        runBase[i + 1] = runBase[i + 2];
        runLen[i + 1] = runLen[i + 2];
    }
    stackSize--;

    /* 
     *（2）找到區(qū)間2的最小元素若插入到區(qū)間的話，正確索引位置
     * Find where the first element of run2 goes in run1\. Prior elements
     * in run1 can be ignored (because they're already in place).
     */
    int k = gallopRight(a[base2], a, base1, len1, 0, c);
    assert k >= 0;
    base1 += k;
    len1 -= k;
    // 說(shuō)明區(qū)間2的最小元素在區(qū)間1的末尾忌卤，所以完成兩個(gè)區(qū)間的合并排序
    if (len1 == 0)
        return;

    /*
     * （3）查找區(qū)間1'的最大元素在區(qū)間2的正確定位
     * Find where the last element of run1 goes in run2\. Subsequent elements
     * in run2 can be ignored (because they're already in place).
     */
    len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
    assert len2 >= 0;
    // 說(shuō)明區(qū)間1'的最大元素小于區(qū)間2的最小元素扫夜，所以完成排序
    if (len2 == 0)
        return;

    // Merge remaining runs, using tmp array with min(len1, len2) elements
    if (len1 <= len2)
        mergeLo(base1, len1, base2, len2);
    else
        mergeHi(base1, len1, base2, len2);
}

為了性能，在len1<=len2的時(shí)候使用mergeLo驰徊，len1>=len2的時(shí)候使用mergeHi，通過(guò)前面的定位堕阔，到這里的時(shí)候棍厂，有a[base1]>a[base2],a[base1+len1]<a[base2+len2]，合并后超陆，最終完成了排序牺弹。

作者：一生只為虞美人
鏈接：http://www.reibang.com/p/1efc3aa1507b
來(lái)源：簡(jiǎn)書
簡(jiǎn)書著作權(quán)歸作者所有，任何形式的轉(zhuǎn)載都請(qǐng)聯(lián)系作者獲得授權(quán)并注明出處时呀。