Java實現世界上最快的排序算法Timsort的示例代碼

背景

Timsort 是一個混合、穩定的排序算法,簡單來說就是歸並排序二分插入排序算法的混合體,號稱世界上最好的排序算法。Timsort一直是 Python 的標準排序算法。Java SE 7 後添加瞭Timsort API ,我們從Arrays.sort可以看出它已經是非原始類型數組的默認排序算法瞭。所以不管是進階編程學習還是面試,理解 Timsort 是比較重要。

// List sort()    
default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
              //數組排序
        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);
    }

前置知識

理解 Timsort 需要先回顧下面的知識。

指數搜索

指數搜索,也被稱為加倍搜索,是一種用於在大型數組中搜索元素而創建的算法。它是一個兩步走的過程。首先,該算法試圖找到目標元素存在的范圍 (L,R),然後在這個范圍內使用二叉搜索來尋找目標的準確位置。時間復雜度為O(lgn)。該搜索算法在大量有序數組中比較有效。

二分插入排序

插入排序算法很簡單,大體過程是從第二個元素開始,依次向前移動交換元素直到找到合適的位置。

插入排序最優時間復雜度也要O(n) ,我們可以使用二分查找來減少插入時元素的比較次數,將時間復雜度降為logn。但是註意,二分查找插入排序仍然需要移動相同數量的元素,但是復制數組的時間消耗低於逐一互換操作。

特點:二分插入排序主要優點是在小數據集場景下排序效率很高。

public static int[] sort(int[] arr) throws Exception {
        // 開始遍歷第一個元素後的所有元素
        for (int i = 1; i < arr.length; i++) {
            // 需要插入的元素
            int tmp = arr[i];
            // 從已排序最後一個元素開始,如果當前元素比插入元素大,就往後移動
            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];
            // 通過二分查找直接找到插入位置
            int j = Math.abs(Arrays.binarySearch(arr, 0, i, tmp) + 1);
            // 找到插入位置後,通過數組復制向後移動,騰出元素位置
            System.arraycopy(arr, j, arr, j + 1, i - j);
            // 將元素插入
            arr[j] = tmp;
        }
        return arr;
    }

歸並排序

歸並排序是利用分治策略的算法,包含兩個主要的操作:分割合並。大體過程是,通過遞歸將數組不斷分成兩半,一直到無法再分割(也就是數組為空或隻剩一個元素),然後進行合並排序。簡單來說合並操作就是不斷取兩個較小的排序數組然後將它們組合成一個更大的數組。

特點:歸並排序主要為大數據集場景設計的排序算法。

public static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
        // 跳出遞歸
        if (start >= end) {
            return;
        }
        // 待分割的數組長度
        int len = end - start;
        int mid = (len >> 1) + start;
        int left = start; // 左子數組開始索引
        int right = mid + 1; // 右子數組開始索引
        // 遞歸切割左子數組,直到隻有一個元素
        mergeSortRecursive(arr, result, left, mid);
        // 遞歸切割右子數組,直到隻有一個元素
        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 執行過程

算法大體過程,如果數組長度小於指定閥值(MIN_MERGE)直接使用二分插入算法完成排序,否則執行下面步驟:

  • 先從數組左邊開始,執行升序運行得到一個子序列
  • 將這個子序列放入運行堆棧裡,等待執行合並
  • 檢查運行堆棧裡的子序列,如果滿足合並條件則執行合並。
  • 重復第一個步驟,執行下一個升序運行

升序運行

升序運行就是從數組查找一段連續遞增(升序)或遞減(降序)子序列的過程,如果子序列為降序則將它反轉為升序,也可以將這個過程簡稱為 run。比如數組 [2,3,6,4,9,30],可以查找到三個子序列,[2,3,6]、[4,9]、[30],或說3個 run

幾個關鍵閥值

MIN_MERGE

這是個常數值,可以簡單理解為執行歸並的最小閥值,如果整個數組長度小於它,就沒必要執行那麼復雜的排序,直接二分插入就行瞭。在 Tim Peter 的 C 實現中為 64,但實際經驗中設置為 32 效果更好,所以 java 裡面此值為 32。

降序反轉時為保證穩定性,相同元素不會被顛倒。

minrun

在合並序列的時候,如果 run 數量等於或者略小於 2 的冪次方的時候,合並效率最高;如果略大於 2 的冪次方,效率就會顯著降低。所以為瞭提高合並效率,需要盡量控制每個 run 的長度,通過定義一個 minrun 來表示每個 run 的最小長度,如果長度太短,就用二分插入排序把 run 後面的元素插入到前面的 run 裡面。

一般在執行排序算法之前,會先計算出這個 minrun(它是根據數據的特點來進行自我調整),minrun 會從32到64選擇一個數字,因此數據的大小除以 minrun 等於或略小於 2 的冪次方。比如長度是 65 ,那麼 minrun 的值就是 33;如果長度是 165,minrun 就是 42。

看下 Java 裡面的實現,如果數據長度(n) < MIN_MERGE,則返回數據長度。如果數據長度恰好是 2 的冪次方,則返回MIN_MERGE/2
也就是16,否則返回一個MIN_MERGE/2 <= k <= MIN_MERGE范圍的值k,這樣可以使的 n/k 接近但嚴格小於 2 的冪次方。

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

MIN_GALLOP

MIN_GALLOP 是為瞭優化合並的過程設定的一個閾值,控制進入 GALLOP 模式中, GALLOP 模式放在後面講。

下面是 Timsort 執行流程圖

運行合並

當棧裡面的 run 滿足合並條件時,它就將棧裡面相鄰的兩個run 進行合並。

合並條件

Timsort 為瞭執行平衡合並(讓合並的 run 大小盡可能相同),制定瞭一個合並規則,對於在棧頂的三個run,分別用X、Y 和 Z 表示他們的長度,其中 X 在棧頂,它們必須始終維持一下的兩個規則:

一旦有其中的一個條件不被滿足,則將 Y 與 X 或 Z 中的較小者合並生成新的 run,並再次檢查棧頂是否仍然滿足條件。如果不滿足則會繼續進行合並,直至棧頂的三個元素都滿足這兩個條件,如果隻剩兩個run,則滿足 Y > X 即可。

如下下圖例子

  • 當 Z <= Y+X ,將 X+Y 合並,此時隻剩下兩個run。
  • 檢測 Y < X ,執行合並,此時隻剩下 X,則退出合並檢測。

我們看下 Java 裡面的合並實現

private void mergeCollapse() {
      
       // 當存在兩個以上run執行合並檢查
        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--;
                
                // 合並相鄰的兩個run,也就是runLen[n] 和 runLen[n+1]
                mergeAt(n); 
            } else if (runLen[n] <= runLen[n + 1]) {
                
                // Y <= X 合並 Y+X
                mergeAt(n);
            } else {
                
                // 滿足兩個條件,跳出循環
                break; 
            }
        }
    }

合並內存開銷

原始歸並排序空間復雜度是 O(n)也就是數據大小。為瞭實現中間項,Timsort 進行瞭一次歸並排序,時間開銷和空間開銷都比 O(n)小。

優化是為瞭盡可能減少數據移動,占用更少的臨時內存,先找出需要移動的元素,然後將較小序列復制到臨時內存,在按最終順序排序並填充到組合序列中。

比如我們需要合並 X [1, 2, 3, 6, 10] 和 Y [4, 5, 7, 9, 12, 14, 17],X 中最大元素是10,我們可以通過二分查找確定,它需要插入到 Y 的第 5個位置才能保證順序,而 Y 中最小元素是4,它需要插入到 X 中的第4個位置才能保證順序,那麼就知道瞭[1, 2, 3] 和 [12, 14, 17] 不需要移動,我們隻需要移動 [6, 10] 和 [4, 5, 7, 9],然後隻需要分配一個大小為 2 臨時存儲就可以瞭。

合並優化

在歸並排序算法中合並兩個數組需要一一比較每個元素,為瞭優化合並的過程,設定瞭一個閾值 MIN_GALLOP,當B中元素向A合並時,如果A中連續 MIN_GALLOP 個元素比B中某一個元素要小,那麼就進入GALLOP模式。

根據基準測試,比如當A中連續7個以上元素比B中某一元素小時切入該模式效果才好,所以初始值為7。

當進入GALLOP模式後,搜索算法變為指數搜索,分為兩個步驟,比如想確定 A 中元素x在 B 中確定的位置

  • 首先在 B 中找到合適的索引區間(2k−1,2k+1−1) 使得 x 元素在這個范圍內;
  • 然後在第一步找到的范圍內通過二分搜索來找到對應的位置。

隻有當一次運行的初始元素不是另一次運行的前七個元素之一時,馳騁才是有益的。這意味著初始閾值為 7。

以上就是Java實現世界上最快的排序算法Timsort的示例代碼的詳細內容,更多關於Java 排序算法Timsort的資料請關註WalkonNet其它相關文章!

推薦閱讀: