快捷導(dǎo)航

Java實(shí)現(xiàn)世界上最快的排序算法Timsort的示例代碼

更新時(shí)間：2022年07月01日 14:21:16 作者：編程碼農(nóng)

Timsort?是一個(gè)混合、穩(wěn)定的排序算法，簡(jiǎn)單來(lái)說(shuō)就是歸并排序和二分插入排序算法的混合體，號(hào)稱世界上最好的排序算法。本文將詳解Timsort算法是定義與實(shí)現(xiàn)，需要的可以參考一下

背景

Timsort 是一個(gè)混合、穩(wěn)定的排序算法，簡(jiǎn)單來(lái)說(shuō)就是歸并排序和二分插入排序算法的混合體，號(hào)稱世界上最好的排序算法。Timsort一直是 Python 的標(biāo)準(zhǔn)排序算法。Java SE 7 后添加了Timsort API ，我們從Arrays.sort可以看出它已經(jīng)是非原始類型數(shù)組的默認(rèn)排序算法了。所以不管是進(jìn)階編程學(xué)習(xí)還是面試，理解 Timsort 是比較重要。

// List sort()    
default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
              //數(shù)組排序
        Arrays.sort(a, (Comparator) c);
              ...
    }

// Arrays.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);
        }
    }

    public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }

前置知識(shí)

理解 Timsort 需要先回顧下面的知識(shí)。

指數(shù)搜索

指數(shù)搜索，也被稱為加倍搜索，是一種用于在大型數(shù)組中搜索元素而創(chuàng)建的算法。它是一個(gè)兩步走的過(guò)程。首先，該算法試圖找到目標(biāo)元素存在的范圍 (L，R)，然后在這個(gè)范圍內(nèi)使用二叉搜索來(lái)尋找目標(biāo)的準(zhǔn)確位置。時(shí)間復(fù)雜度為O(lgn)。該搜索算法在大量有序數(shù)組中比較有效。

二分插入排序

插入排序算法很簡(jiǎn)單，大體過(guò)程是從第二個(gè)元素開(kāi)始，依次向前移動(dòng)交換元素直到找到合適的位置。

插入排序最優(yōu)時(shí)間復(fù)雜度也要O(n) ，我們可以使用二分查找來(lái)減少插入時(shí)元素的比較次數(shù)，將時(shí)間復(fù)雜度降為logn。但是注意，二分查找插入排序仍然需要移動(dòng)相同數(shù)量的元素，但是復(fù)制數(shù)組的時(shí)間消耗低于逐一互換操作。

特點(diǎn)：二分插入排序主要優(yōu)點(diǎn)是在小數(shù)據(jù)集場(chǎng)景下排序效率很高。

public static int[] sort(int[] arr) throws Exception {
        // 開(kāi)始遍歷第一個(gè)元素后的所有元素
        for (int i = 1; i < arr.length; i++) {
            // 需要插入的元素
            int tmp = arr[i];
            // 從已排序最后一個(gè)元素開(kāi)始，如果當(dāng)前元素比插入元素大，就往后移動(dòng)
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // 將元素插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }

    public static int[] binarySort(int[] arr) throws Exception {
        for (int i = 1; i < arr.length; i++) {
            // 需要插入的元素
            int tmp = arr[i];
            // 通過(guò)二分查找直接找到插入位置
            int j = Math.abs(Arrays.binarySearch(arr, 0, i, tmp) + 1);
            // 找到插入位置后，通過(guò)數(shù)組復(fù)制向后移動(dòng)，騰出元素位置
            System.arraycopy(arr, j, arr, j + 1, i - j);
            // 將元素插入
            arr[j] = tmp;
        }
        return arr;
    }

歸并排序

歸并排序是利用分治策略的算法，包含兩個(gè)主要的操作：分割與合并。大體過(guò)程是，通過(guò)遞歸將數(shù)組不斷分成兩半，一直到無(wú)法再分割（也就是數(shù)組為空或只剩一個(gè)元素），然后進(jìn)行合并排序。簡(jiǎn)單來(lái)說(shuō)合并操作就是不斷取兩個(gè)較小的排序數(shù)組然后將它們組合成一個(gè)更大的數(shù)組。

特點(diǎn)：歸并排序主要為大數(shù)據(jù)集場(chǎng)景設(shè)計(jì)的排序算法。

public static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
        // 跳出遞歸
        if (start >= end) {
            return;
        }
        // 待分割的數(shù)組長(zhǎng)度
        int len = end - start;
        int mid = (len >> 1) + start;
        int left = start; // 左子數(shù)組開(kāi)始索引
        int right = mid + 1; // 右子數(shù)組開(kāi)始索引
        // 遞歸切割左子數(shù)組，直到只有一個(gè)元素
        mergeSortRecursive(arr, result, left, mid);
        // 遞歸切割右子數(shù)組，直到只有一個(gè)元素
        mergeSortRecursive(arr, result, right, end);
        int k = start;
        while (left <= mid && right <= end) {
            result[k++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
        }
        while (left <= mid) {
            result[k++] = arr[left++];
        }
        while (right <= end) {
            result[k++] = arr[right++];
        }
        for (k = start; k <= end; k++) {
            arr[k] = result[k];
        }
    }

    public static int[] merge_sort(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        mergeSortRecursive(arr, result, 0, len - 1);
        return arr;
    }

Timsort 執(zhí)行過(guò)程

算法大體過(guò)程，如果數(shù)組長(zhǎng)度小于指定閥值（MIN_MERGE）直接使用二分插入算法完成排序，否則執(zhí)行下面步驟：

先從數(shù)組左邊開(kāi)始，執(zhí)行升序運(yùn)行得到一個(gè)子序列。
將這個(gè)子序列放入運(yùn)行堆棧里，等待執(zhí)行合并。
檢查運(yùn)行堆棧里的子序列，如果滿足合并條件則執(zhí)行合并。
重復(fù)第一個(gè)步驟，執(zhí)行下一個(gè)升序運(yùn)行。

升序運(yùn)行

升序運(yùn)行就是從數(shù)組查找一段連續(xù)遞增（升序）或遞減（降序）子序列的過(guò)程，如果子序列為降序則將它反轉(zhuǎn)為升序，也可以將這個(gè)過(guò)程簡(jiǎn)稱為 run。比如數(shù)組 [2,3,6,4,9,30]，可以查找到三個(gè)子序列，[2,3,6]、[4,9]、[30]，或說(shuō)3個(gè) run。

幾個(gè)關(guān)鍵閥值

MIN_MERGE

這是個(gè)常數(shù)值，可以簡(jiǎn)單理解為執(zhí)行歸并的最小閥值，如果整個(gè)數(shù)組長(zhǎng)度小于它，就沒(méi)必要執(zhí)行那么復(fù)雜的排序，直接二分插入就行了。在 Tim Peter 的 C 實(shí)現(xiàn)中為 64，但實(shí)際經(jīng)驗(yàn)中設(shè)置為 32 效果更好，所以 java 里面此值為 32。

降序反轉(zhuǎn)時(shí)為保證穩(wěn)定性，相同元素不會(huì)被顛倒。

minrun

在合并序列的時(shí)候，如果 run 數(shù)量等于或者略小于 2 的冪次方的時(shí)候，合并效率最高；如果略大于 2 的冪次方，效率就會(huì)顯著降低。所以為了提高合并效率，需要盡量控制每個(gè) run 的長(zhǎng)度，通過(guò)定義一個(gè) minrun 來(lái)表示每個(gè) run 的最小長(zhǎng)度，如果長(zhǎng)度太短，就用二分插入排序把 run 后面的元素插入到前面的 run 里面。

一般在執(zhí)行排序算法之前，會(huì)先計(jì)算出這個(gè) minrun（它是根據(jù)數(shù)據(jù)的特點(diǎn)來(lái)進(jìn)行自我調(diào)整），minrun 會(huì)從32到64選擇一個(gè)數(shù)字，因此數(shù)據(jù)的大小除以 minrun 等于或略小于 2 的冪次方。比如長(zhǎng)度是 65 ，那么 minrun 的值就是 33；如果長(zhǎng)度是 165，minrun 就是 42。

看下 Java 里面的實(shí)現(xiàn)，如果數(shù)據(jù)長(zhǎng)度（n） < MIN_MERGE，則返回?cái)?shù)據(jù)長(zhǎng)度。如果數(shù)據(jù)長(zhǎng)度恰好是 2 的冪次方，則返回MIN_MERGE/2
也就是16，否則返回一個(gè)MIN_MERGE/2 <= k <= MIN_MERGE范圍的值k，這樣可以使的 n/k 接近但嚴(yán)格小于 2 的冪次方。

private static int minRunLength(int n) {
        assert n >= 0;
        int r = 0;      // 如果低位任何一位是1，就會(huì)變成1
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

MIN_GALLOP

MIN_GALLOP 是為了優(yōu)化合并的過(guò)程設(shè)定的一個(gè)閾值，控制進(jìn)入 GALLOP 模式中， GALLOP 模式放在后面講。

下面是 Timsort 執(zhí)行流程圖

運(yùn)行合并

當(dāng)棧里面的 run 滿足合并條件時(shí)，它就將棧里面相鄰的兩個(gè)run 進(jìn)行合并。

合并條件

Timsort 為了執(zhí)行平衡合并（讓合并的 run 大小盡可能相同），制定了一個(gè)合并規(guī)則，對(duì)于在棧頂?shù)娜齻€(gè)run，分別用X、Y 和 Z 表示他們的長(zhǎng)度，其中 X 在棧頂，它們必須始終維持一下的兩個(gè)規(guī)則：

一旦有其中的一個(gè)條件不被滿足，則將 Y 與 X 或 Z 中的較小者合并生成新的 run，并再次檢查棧頂是否仍然滿足條件。如果不滿足則會(huì)繼續(xù)進(jìn)行合并，直至棧頂?shù)娜齻€(gè)元素都滿足這兩個(gè)條件，如果只剩兩個(gè)run，則滿足 Y > X 即可。

如下下圖例子

當(dāng) Z <= Y+X ，將 X+Y 合并，此時(shí)只剩下兩個(gè)run。
檢測(cè) Y < X ，執(zhí)行合并，此時(shí)只剩下 X，則退出合并檢測(cè)。

我們看下 Java 里面的合并實(shí)現(xiàn)

private void mergeCollapse() {
      
       // 當(dāng)存在兩個(gè)以上run執(zhí)行合并檢查
        while (stackSize > 1) {

          // 表示 Y
            int n = stackSize - 2; 
           
          // Z <= Y + X 
            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { 

              // 如果 Z < X 合并Z+Y ，否則合并X+Y
              if (runLen[n - 1] < runLen[n + 1])
                    n--;
                
                // 合并相鄰的兩個(gè)run，也就是runLen[n] 和 runLen[n+1]
                mergeAt(n); 
            } else if (runLen[n] <= runLen[n + 1]) {
                
                // Y <= X 合并 Y+X
                mergeAt(n);
            } else {
                
                // 滿足兩個(gè)條件，跳出循環(huán)
                break; 
            }
        }
    }

合并內(nèi)存開(kāi)銷

原始?xì)w并排序空間復(fù)雜度是 O(n)也就是數(shù)據(jù)大小。為了實(shí)現(xiàn)中間項(xiàng)，Timsort 進(jìn)行了一次歸并排序，時(shí)間開(kāi)銷和空間開(kāi)銷都比 O(n)小。

優(yōu)化是為了盡可能減少數(shù)據(jù)移動(dòng)，占用更少的臨時(shí)內(nèi)存，先找出需要移動(dòng)的元素，然后將較小序列復(fù)制到臨時(shí)內(nèi)存，在按最終順序排序并填充到組合序列中。

比如我們需要合并 X [1, 2, 3, 6, 10] 和 Y [4, 5, 7, 9, 12, 14, 17]，X 中最大元素是10，我們可以通過(guò)二分查找確定，它需要插入到 Y 的第 5個(gè)位置才能保證順序，而 Y 中最小元素是4，它需要插入到 X 中的第4個(gè)位置才能保證順序，那么就知道了[1, 2, 3] 和 [12, 14, 17] 不需要移動(dòng)，我們只需要移動(dòng) [6, 10] 和 [4, 5, 7, 9]，然后只需要分配一個(gè)大小為 2 臨時(shí)存儲(chǔ)就可以了。

合并優(yōu)化

在歸并排序算法中合并兩個(gè)數(shù)組需要一一比較每個(gè)元素，為了優(yōu)化合并的過(guò)程，設(shè)定了一個(gè)閾值 MIN_GALLOP，當(dāng)B中元素向A合并時(shí)，如果A中連續(xù) MIN_GALLOP 個(gè)元素比B中某一個(gè)元素要小，那么就進(jìn)入GALLOP模式。

根據(jù)基準(zhǔn)測(cè)試，比如當(dāng)A中連續(xù)7個(gè)以上元素比B中某一元素小時(shí)切入該模式效果才好，所以初始值為7。

當(dāng)進(jìn)入GALLOP模式后，搜索算法變?yōu)橹笖?shù)搜索，分為兩個(gè)步驟，比如想確定 A 中元素x在 B 中確定的位置