Java 集合中的排序演算法淺析

作者：京東物流 秦彪

1.  引言

排序是一個Java開發者，在日常開發過程中隨處可見的開發內容，Java中有豐富的API可以調用使用。在Java語言中，作為集合工具類的排序方法，必定要做到通用、高效、實用這幾點特征。使用什麼樣排序演算法會比較合適，能夠做到在儘量降低時間、空間複雜度的情況下，又要兼顧保證穩定性，達到優秀的性能。可能從性能角度出發首先會想到的是快速排序，或者歸併排序。作為jdk提供的通用排序功能，使用又如此頻繁，肯定有獨特之處，一起來看學習下期中的奧秘。

文中不會過多的介紹幾大基本排序演算法的方式、由來和思想，主要精力集中在一塊探討java中排序方法所使用的演算法，以及那些是值得我們學習和借鑒的內容。文中如有理解和介紹的錯誤，一起學習，一起探討，一起進步。

2.  案例

日常使用最為頻繁的排序，莫過於如下代碼案例，給定一個現有的序列進行一定規則下的排序，配合java8的stream特性，可以很方便的對一個集合進行排序操作（排序規則只是對排序對象及排序方案的限定，不在本文討論範圍內）。

List<Integer> list = Arrays.asList(10, 50, 5, 14, 16, 80);
System.out.println(list.stream().sorted().collect(Collectors.toList()));

在代碼執行的過程中SortedOps.java類中 Arrays.sort(array, 0, offset, comparator); 執行了Array集合類型的sort排序演算法。

@Override
public void end() {
    Arrays.sort(array, 0, offset, comparator);
    downstream.begin(offset);
    if (!cancellationWasRequested) {
        for (int i = 0; i < offset; i++)
            downstream.accept(array[i]);
    }
    else {
        for (int i = 0; i < offset && !downstream.cancellationRequested(); i++)
            downstream.accept(array[i]);
    }
    downstream.end();
    array = null;
}

如果使用Collections.sort() 方法如下列印 list1 和 list2 結果一樣，且調用的都是 Arrays 集合類中的 sort 方法。

List<Integer> list1 = Arrays.asList(10, 50, 5, 14, 16, 80);
System.out.println(list1.stream().sorted().collect(Collectors.toList()));

List<Integer> list2 = Lists.newArrayList();
list2.addAll(list1);
Collections.sort(list2);
System.out.println(list2);
// 輸出：
// [5, 10, 14, 16, 50, 80]
// [5, 10, 14, 16, 50, 80]

2.  Collections.sort 方法介紹

Collections類中關於sort方法定義如下：

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

通過該方法註釋，查看到有三項值得關註的信息，大概意思是該方法實現了穩定且預設升序排序的功能。

1. Sorts the specified list into ascending order, according to the Comparable natural ordering of its elements.
2. This sort is guaranteed to be stable equal elements will not be reordered as a result of the sort.
3. The specified list must be modifiable, but need not be resizable.

進入sort，代碼進入到List類的sort方法，發現方法將入參list先轉為了數組Object[]，之後利用Arrays.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);
    }
}

首先在這裡思考一個問題為什麼要轉為數組，問題答案已經在方法的英文註釋中說明白了。

* The default implementation obtains an array containing all elements in
* this list, sorts the array, and iterates over this list resetting each
* element from the corresponding position in the array. (This avoids the
* n<sup>2</sup> log(n) performance that would result from attempting
* to sort a linked list in place.)

是為了避免直接對List的鏈表進行排序，從而耗費O(n2logn) 時間複雜度。當然這裡在this.toArray()時，為了將list強行變為數組會損失一些性能和空間開銷，源碼中使用了System.arraycopy調用底層操作系統方法進行數據複製，詳細內容可以查看相關實現。 繼續進入Arrays類的sort方法定義中，我們沒有使用比較器，LegacyMergeSort.userRequested表示進入老的歸併排序演算法，預設是關閉的，直接進入本文重點關註的TimSort.sort(…)方法。

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);
    }
}

3.  TimSort 演算法介紹

Timsort是一個自適應的、混合的、穩定的排序演算法，是由Tim Peter於2002年發明的，最早應用在Python中，現在廣泛應用於Python、Java、Android 等語言與平臺中，作為基礎的排序演算法使用。其中Java語言的Collection.sort在JDK1.6使用的是普通的歸併排序，歸併排序雖然時間複雜度低，但是空間複雜度要求較高，所以從JDK1.7開始就更改為了TimSort演算法。

Timsort 的時間複雜度是 O(n log n)，與歸併排序的時間複雜度相同，那它的優勢是啥呢，實際上可以認為TimSort排序演算法是歸併排序演算法的優化版，從它的三個特征就可以看出，第二個特征“混合的”，沒錯，它不單純是一種演算法，而是融合了歸併演算法和二分插入排序演算法的精髓，因此能夠在排序性能上表現優異。其它兩個特征自適應和穩定性會在文章後面講到。首先從演算法性能統計上做個對比：

可以看出TimSort排序演算法，平均和最壞時間複雜度是O(nlogn)，最好時間複雜度是O(n)，空間複雜度是O(n)，且穩定的一種排序演算法。在穩定演算法中，從性能效果上對比來看和二叉排序演算法一樣。

3.1 TimSort的核心思想

那TimSort演算法的核心思想是什麼呢，首先原始的TimSort對於長度小於64的數據（java中是32），會直接選擇二分插入排序，效率很高。其次，TimSort演算法的初衷認為現實中的數據總是部分有序的。這句話很關鍵，怎麼理解呢，比如列表[5, 2, 8, 5, 7,23, 45, 63]，裡面的[5, 2] 和 [8, 5] 和 [7, 23, 45,63] 各子列表中就是有序的，要麼升序要麼降序，這就是TimSort的基本根據。

基於此會發現待排序列表已經部分有序了，所以會在排序過程中儘量不要破壞這種順序，就可以做到減少排序時間消耗。基本思想說完了，由此引出TimSort演算法的幾個概念：run和minrun。

run是指連續升序或者連續降序的最長子序列（降序和升序可以相互轉換），而minrun是一個設定值，實際上是每個run的長度最小值。所以TimSort會對待排序序列進行劃分，找出連續有序的子序列，如果子序列長度不滿足這點要求，就將後續數據插入到前面的子序列中。

舉個例子，待排序序列[5, 2, 8, 5, 7,23, 45, 63]， 如果minRun = 3，那分割後的run會有以下：[2, 5, 8]、[5,7,23,45,63] 兩個子序列，最終通過合併這兩個run得到[2,5,5,7,8,23,45,63]

是不是有個疑問： minrun怎麼選擇得到的？該值是通過大量的統計計算給出的minrun長度建議是在32 ~ 64之間取值效率比較高，具體在java代碼中可能會有所不同。

接著來看，假設現在有序子序列已經拆分好了，需要進入到合併過程中了，TimSort是如何合併子序列的。對於歸併排序我們都知道，序列先歸後並，兩兩組合利用一個空數組直接進行比較就合併了。但是在TimSort演算法中，合併過程是實時的，每次算出一個run就可能做一次合併。這個過程利用了棧結構，且需要遵循相鄰的run才可以合併，也就是只有相鄰的棧元素可以進行合併。

規則如下：假設當前有三個run子序列依次入棧，現在棧頂有三個元素從上至下依次為x3、x2、x1，它們的長度只要滿足以下兩個條件中的任何一個就進行合併：

（1）x1 <= x2 + x3

（2）x1 <= x2

滿足這個條件的三個序列，像漢諾塔一樣長度由下往上依次減小。剛纔提到合併run的過程是實時的，也就是每產生一個run就進行一次合併操作。舉例說明下，當前假設待排序序列[2,6,8,4,2,5,7,9,10,11,4,25,64,32,78,99]，其中再假設minrun=3是合理的。合併過程是這樣的，註意這裡的壓棧和彈棧不一定需要對子序列本身進行操作，不是真的將子序列放入棧中，而只需要run標識以及長度即可，因為棧元素比較的是run長度。

（1）首先第一個run0是[2,6,8]，而第二個run1是[2,4,5]，此時依次將其放入棧中，發現滿足第二個條件，這兩個run進行合併，合併後將舊序列從棧中彈出，得到新的run0是[2,2,4,5,6,8]，再次壓入棧中。

（2）繼續從原序列中找到新的run1是[7,9,10,11]，壓入棧中，此時run0和run1不滿足條件不需要合併。繼續從原序列中找到run2是[4,25,64]，壓入棧中，此時滿足第一個條件，這裡的run1和run2需要進行合併，合併後將舊序列從棧中彈出，新run1是[4,7,9,10,11,25,64]，壓入棧中。

（3）此時發現run0和run1滿足第二個條件，繼續合併彈出舊序列，得到新run0是[2,2,4,4,5,6,7,8,9,10,11,25,64]，壓入棧中。

（4）繼續從原序列中找到新的run1是[32,78,99]，壓入棧中。此時發現沒有更多元素，而條件是不滿足的，依然進行一次合併，彈出舊序列，壓入合併後的新子序列run0是[2,2,4,4,5,6,7,8,9,10,11,25,32,64,78,99]

（5）此時將run0拷貝到原序列就完成了排序

為什麼要設置這麼兩個合併run的嚴格條件，直接壓棧合併豈不更好？目的是為了避免一個較長的有序片段和一個較小的有序片段進行歸併，在合併長度上做到均衡效率才高。

在合併run的過程中會用到一種所謂的gallop(飛奔)模式，能夠減少參與歸併的數據長度，主要過程如下：假設有待歸併的子序列x和y，如果x的前n個元素都是比y首元素小的，那這n個元素實際上就不用參與歸併了。原因就是這n個元素本來已經有序了，歸併後還是在原來的位置。同理而言，如果y的最後幾個元素都比x最後一個元素小，那y的最後這n個元素也就不必參與歸併操作了，這樣就可以減少歸併長度，減少來回覆制多餘數據的開銷。

3.2 Java源碼

探討完TimSort的核心思想及其排序過程，現在來看下java代碼是如何實現的。Java1.8中的TimSort類位置在java.util.TimSort

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;

    if (nRemaining < MIN_MERGE) {
        int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
        binarySort(a, lo, hi, lo + initRunLen, c);
        return;
    }

    TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
    int minRun = minRunLength(nRemaining);
    do {
        int runLen = countRunAndMakeAscending(a, lo, hi, c);

        if (runLen < minRun) {
            int force = nRemaining <= minRun ? nRemaining : minRun;
            binarySort(a, lo, lo + force, lo + runLen, c);
            runLen = force;
        }

        ts.pushRun(lo, runLen);
        ts.mergeCollapse();

        lo += runLen;
        nRemaining -= runLen;
    } while (nRemaining != 0);

    assert lo == hi;
    ts.mergeForceCollapse();
    assert ts.stackSize == 1;
}

變數nRemaining記錄的是待排序列表中剩餘元素個數， MIN_MERGE就是前文中提到的java中的minrun值是32。如果nRemaining<32，用countRunAndMakeAscending(…)方法得到連續升序的最大個數，裡面涉及到升序降序調整。可以看到如果待排序列表小於32長度，就進行二分插入排序binarySort(…)。

如果待排序列表長度大於32，調用TimSort對象的minRunLength(nRemaining) 計算minRun，這裡就體現了動態自適應，具體來看代碼中是如何做的。r為取出長度n的二進位每次右移的一個溢出位值，n每次右移1位，直到長度n小於32。n+r最終結果就是保留長度n的二進位的高5位再加上1個移除位。根據註釋可以看出：

• 如果待排序數組長度為2的n次冪，比如1024，則minRun = 32/2 = 16
• 其它情況的時候，逐位右移，直到找到介於16<=k<=32的值。

假如待排序列表長度是7680，二進位是1111000000000，按照操作後是11110十進位是30，再加上移除位0是30，所以minRun=30

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

接下來在迴圈中進行處理：

（1） 計算最小升序的run長度，如果小於minRun，使用二分插入排序將run的長度補充到minRun要求的長度。

（2） ts.pushRun(lo, runLen) ，通過棧記錄每個run的長度，這裡lo是run的第一個元素的索引用來標記操作的是哪個run，runLen是run的長度。

private void pushRun(int runBase, int runLen) {
    this.runBase[stackSize] = runBase;
    this.runLen[stackSize] = runLen;
    stackSize++;
}

（3）ts.mergeCollapse();  通過計算前面提到的兩個run合併的限定條件，分別是：

• runLen[n-1] <= runLen[n] + runLen[n+1]
• runLen[n] <= runLen[n + 1]

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
        }
    }
}

（4） 這裡的mergeAt(n) 歸併排序過程，之前有提到是經過優化後所謂gallop模式的歸併排序，具體表現在方法中的gallopRight和gallopLeft方法。

int k = gallopRight(a[base2], a, base1, len1, 0, c);
assert k >= 0;
base1 += k;
len1 -= k;
if (len1 == 0)
    return;

len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
assert len2 >= 0;
if (len2 == 0)
    return;

假設有X序列[4,9,21,23]， Y序列[5,7,12,13,14,15,17]，由於X中4小於Y序列最小元素5，所以合併後4必然是第一個元素；而Y序列中尾元素17比X中的[21,23]小，所以X中的[21,23]必然是合併最後兩元素。

4.  DivalQuickSort 演算法介紹

前文案例中提到SortedOps.java類，該類中對於基本類型的排序調用 Arrays.sort(ints); 或 Arrays.sort(longs); 再或 Arrays.sort(doubles); 使用了DivalQuickSort排序演算法。

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

4.1 DivalQuickSort 核心思想

快速排序使用的是在排序序列中選擇一個數作為分區點pivot，也就是所謂的軸，然後以此軸將數據分為左右兩部分，大於該值的為一個區，小於該值的為一個區，利用分治和遞歸思想實現。如下假設選擇19為pivot值。

雙軸快排，如其名字所示，就是會選取兩個數作為pivot，這樣就會劃分出三個區間，實際在執行中會有4個區間，分別是小於等於pivot1區間；pivot1和pivot2之間區間，待處理區間； 大於等於pivot2區間。如下假設選擇10和19為兩個pivot值。

每次遞歸迭代時遍歷待處理的區域數據，然後比較它應該放的位置，併進行交換操作，逐漸壓縮待處理區域的數據長度，處理掉待處理區域的元素數據；執行完畢一輪數據後交換pivot數值，然後各自區間再進行遞歸排序即可。

4.2 Java源碼

static void sort(int[] a, int left, int right,
                 int[] work, int workBase, int workLen) {
    if (right - left < QUICKSORT_THRESHOLD) {
        sort(a, left, right, true);
        return;
    }

    int[] run = new int[MAX_RUN_COUNT + 1];
    int count = 0; run[0] = left;

    for (int k = left; k < right; run[count] = k) {
        if (a[k] < a[k + 1]) { // ascending
            while (++k <= right && a[k - 1] <= a[k]);
        } else if (a[k] > a[k + 1]) { // descending
            while (++k <= right && a[k - 1] >= a[k]);
            for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
            }
        } else { // equal
            for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                if (--m == 0) {
                    sort(a, left, right, true);
                    return;
                }
            }
        }

        if (++count == MAX_RUN_COUNT) {
            sort(a, left, right, true);
            return;
        }
    }

    if (run[count] == right++) {
        run[++count] = right;
    } else if (count == 1) {
        return;
    }

    byte odd = 0;
    for (int n = 1; (n <<= 1) < count; odd ^= 1);

    int[] b;
    int ao, bo;
    int blen = right - left;
    if (work == null || workLen < blen || workBase + blen > work.length) {
        work = new int[blen];
        workBase = 0;
    }
    if (odd == 0) {
        System.arraycopy(a, left, work, workBase, blen);
        b = a;
        bo = 0;
        a = work;
        ao = workBase - left;
    } else {
        b = work;
        ao = 0;
        bo = workBase - left;
    }

    for (int last; count > 1; count = last) {
        for (int k = (last = 0) + 2; k <= count; k += 2) {
            int hi = run[k], mi = run[k - 1];
            for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                    b[i + bo] = a[p++ + ao];
                } else {
                    b[i + bo] = a[q++ + ao];
                }
            }
            run[++last] = hi;
        }
        if ((count & 1) != 0) {
            for (int i = right, lo = run[count - 1]; --i >= lo;
                b[i + bo] = a[i + ao]
            );
            run[++last] = right;
        }
        int[] t = a; a = b; b = t;
        int o = ao; ao = bo; bo = o;
    }
}

通過看代碼可以看出，java中的雙軸快排在片段數據長度及一定條件的情況下，還使用了其它諸如歸併、插入等排序演算法。

由於DivalQuickSort演算法實現內容比較複雜，文中重點講解了TimSort演算法，待筆者研究透徹後進行補充。

5.  相同環境排序時間對比

想要真正模擬一模一樣運行環境，是困難的。這裡只是模擬相同的數據集，在相同機器上，其實就是平時辦公的機器，統計不同排序演算法排序過程中耗費的時間，這裡的結果僅供參考。

模擬數據：隨機得到1億個範圍在0到100000000內的整型元素構成數組，分別基於快速排序、普通歸併排序、TimSort的排序演算法得到耗時結果如下，單位ms。

通過測試驗證結果來看，在當前數據集規模下，雙軸快排DivalQuickSort表現優異。註：Java中TimSort主要運用引用類型的集合排序中，本次數據驗證並未加入比較。

5.  總結與探討

由於Java提供了很方便的排序API，所以在平時的需求使用過程中一般都是短短幾行代碼調用使用完整排序工作，這也是Java作為一門流行語言最基本的職責所在。當然也會導致我們開發者容易忽視其原理，不能夠學習到裡面的精髓。

文中一起瞭解學習了TimSort演算法和DivalQuickSort的排序思想與java實現。作為基本排序實現被廣泛的應用，肯定有其值得學習與借鑒的地方。可以得知工業用排序演算法，通常都不是一種演算法，而是根據特定條件下的多種演算法混合而成，實際上平時很多使用的經典數據結構都不是一種類型或者一種方式，比如HashMap中隨著數據量大小有鏈表與紅黑樹的轉化，再比如Redis中的各種數據結構不都是一種實現。這些經典優秀的實現都用到了諸如此類的思想。