深入探究TimSort對歸并排序算法的優(yōu)化及Java實現(xiàn)

更新時間：2016年05月04日 11:27:49 作者：Lizo_Is_Me

這篇文章主要介紹了TimSort歸并排序的優(yōu)化及Java實現(xiàn),TimSort 是一個歸并排序做了大量優(yōu)化的版本,需要的朋友可以參考下

簡介
MergeSort對已經(jīng)反向排好序的輸入時復(fù)雜度為O(n^2)，而timsort就是針對這種情況，對MergeSort進行優(yōu)化而產(chǎn)生的，平均復(fù)雜度為n*O(log n),最好的情況為O(n)，最壞情況n*O(log n)。并且TimSort是一種穩(wěn)定性排序。思想是先對待排序列進行分區(qū)，然后再對分區(qū)進行合并，看起來和MergeSort步驟一樣，但是其中有一些針對反向和大規(guī)模數(shù)據(jù)的優(yōu)化處理。

歸并排序的優(yōu)化思想
歸并排序有以下幾點優(yōu)化方法：

和快速排序一樣，對于小數(shù)組可以使用插入排序或者選擇排序，避免遞歸調(diào)用。
在merge()調(diào)用之前，可以判斷一下a[mid]是否小于等于a[mid+1]。如果是的話那么就不用歸并了，數(shù)組已經(jīng)是有序的。原因很簡單，既然兩個子數(shù)組已經(jīng)有序了，那么a[mid]是第一個子數(shù)組的最大值，a[mid+1]是第二個子數(shù)組的最小值。當a[mid]<=a[mid+1]時，數(shù)組整體有序。
為了節(jié)省將元素復(fù)制到輔助數(shù)組作用的時間，可以在遞歸調(diào)用的每個層次交換原始數(shù)組與輔助數(shù)組的角色。
在merge()方法中的歸并過程需要判斷i和j是否已經(jīng)越界，即某半邊已經(jīng)用盡?？梢杂昧硪环N方式，去掉檢測是否某半邊已經(jīng)用盡的代碼。具體步驟是將數(shù)組a[]的后半部分以降序的方式復(fù)制到aux[]，然后從兩端歸并。對于數(shù)組{1,2,3}和{2,3,5},第一個子數(shù)組照常復(fù)制，第二個則從后往前復(fù)制，最終aux[]中的元素為{1,2,3,5,3,2}。這種方法的缺點是使得歸并排序變?yōu)椴环€(wěn)定排序。代碼實現(xiàn)如下：

void merge(int[] a, int lo, int mid, int hi, int[] aux) {
for (int k = lo; k <= mid; k++) {
  aux[k] = a[k];
}
for (int k = mid + 1;k <= hi; k++) {
  aux[k] = a[hi - k + mid + 1];
}
int i = lo, j = hi;   //從兩端往中間
for (int k = lo; k <= hi; k++)
  if (aux[i] <= aux[j]) a[k] = aux[i++];
  else a[k] = aux[j--];
}

TimSort的步驟

分區(qū)

分區(qū)的思想是掃描一次數(shù)組，把連續(xù)正序列（如果是升序排序，那么正序列就是升序序列），或者【嚴格】（保證排序算法的穩(wěn)定性）的反序列做為一個分區(qū)（run），如果是反序列，把分區(qū)里的元素反轉(zhuǎn)一下。例如
1，2，3，6，4，5，8，6，4 劃分分區(qū)結(jié)果為
[1,2,3,6],[4,5,8],[6,4]
然后反轉(zhuǎn)反序列
[1,2,3,6],[4,5,8],[4,6]

合并

考慮一個極端的例子，比如分區(qū)的長度分別為 10000，10，1000，10，10，我們當然希望是先讓10個10合并成20， 20和1000合并成1020如此下去，如果從從左往右順序合并的話，每次都用到10000這個數(shù)組和去小的數(shù)組合并，代價太大了。所以我們可以用一個策略來優(yōu)化合并的順序。

實例

以java中的ComparableTimSort.sort()為例子，用了一個run stack來確定是否應(yīng)該合并，

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

小于MIN_MERGE（32）的排序，分區(qū)后直接用二分插入排序

int minRun = minRunLength(nRemaining);
    do {
      //找出下一個分區(qū)的起始位置，同時也對反向序列做了翻轉(zhuǎn)處理
      int runLen = countRunAndMakeAscending(a, lo, hi);

      //保證run stack中的run的都大于minRun ，如果當前分區(qū)太小，就從后面取出元素補足
      if (runLen < minRun) {
        int force = nRemaining <= minRun ? nRemaining : minRun;
        binarySort(a, lo, lo + force, lo + runLen);
        runLen = force;
      }

      //把run放入 run stack中
      ts.pushRun(lo, runLen);
      //判斷是否應(yīng)該合并，i是從棧頂開始的，知道不能合并為止
      //1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] 
      //2. runLen[i - 2] > runLen[i - 1]
      ts.mergeCollapse();


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

    // Merge all remaining runs to complete sort
    assert lo == hi;
    //合并剩下的run
    ts.mergeForceCollapse();
    assert ts.stackSize == 1;

在看里面的一個比較重要的函數(shù)

/**
* 如果后2個run的長度加起來比前面一個長，則使用中間位置的run和前后長度更短的run一個合并
* 如果后2個run的長度加起來比前面一個短，則把后面2個run合并
*/
 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
      }
    }
  }

您可能感興趣的文章: