深刻探討TimSort對合並排序算法的優化及Java完成

深刻探討TimSort對合並排序算法的優化及Java完成。本站提示廣大學習愛好者：（深刻探討TimSort對合並排序算法的優化及Java完成）文章只能為提供參考，不一定能成為您想要的結果。以下是深刻探討TimSort對合並排序算法的優化及Java完成正文

簡介
MergeSort對曾經反向排好序的輸出時龐雜度為O(n^2)，而timsort就是針對這類情形，對MergeSort停止優化而發生的，均勻龐雜度為n*O(log n),最好的情形為O(n)，最壞情形n*O(log n)。而且TimSort是一種穩固性排序。思惟是先看待排序列停止分區，然後再對分區停止歸並，看起來和MergeSort步調一樣，然則個中有一些針對反向和年夜范圍數據的優化處置。

合並排序的優化思惟
合並排序有以下幾點優化辦法：

和疾速排序一樣，關於小數組可使用拔出排序或許選擇排序，防止遞歸挪用。
在merge()挪用之前，可以斷定一下a[mid]能否小於等於a[mid+1]。假如是的話那末就不消合並了，數組曾經是有序的。緣由很簡略，既然兩個子數組曾經有序了，那末a[mid]是第一個子數組的最年夜值，a[mid+1]是第二個子數組的最小值。當a[mid]<=a[mid+1]時，數組全體有序。
為了節儉將元素復制到幫助數組感化的時光，可以在遞歸挪用的每一個條理交流原始數組與幫助數組的腳色。
在merge()辦法中的合並進程須要斷定i和j能否曾經越界，即某半邊曾經用盡。可以用另外一種方法，去失落檢測能否某半邊曾經用盡的代碼。詳細步調是將數組a[]的後半部門以降序的方法復制到aux[]，然後從兩頭合並。關於數組{1,2,3}和{2,3,5},第一個子數組照舊復制，第二個則從後往前復制，終究aux[]中的元素為{1,2,3,5,3,2}。這類辦法的缺陷是使得合並排序變成不穩固排序。代碼完成以下：

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的步調

分區

分區的思惟是掃描一次數組，把持續正序列（假如是升序排序，那末正序列就是升序序列），或許【嚴厲】（包管排序算法的穩固性）的反序列做為一個分區（run），假如是反序列，把分區裡的元素反轉一下。 例如
1，2，3，6，4，5，8，6，4 劃分分區成果為
[1,2,3,6],[4,5,8],[6,4]
然後反轉反序列
[1,2,3,6],[4,5,8],[4,6]

歸並

斟酌一個極真個例子，好比分區的長度分離為 10000，10，1000，10，10，我們固然願望是先讓10個10歸並成20， 20和1000歸並成1020如斯下去， 假如從從左往右次序歸並的話，每次都用到10000這個數組和去小的數組歸並，價值太年夜了。所以我們可以用一個戰略來優化歸並的次序。

實例

以java中的ComparableTimSort.sort()為例子， 用了一個run stack來肯定能否應當歸並，

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

小於MIN_MERGE（32）的排序，分區後直接用二分拔出排序

int minRun = minRunLength(nRemaining);
    do {
      //找出下一個分區的肇端地位，同時也對反向序列做了翻轉處置
      int runLen = countRunAndMakeAscending(a, lo, hi);

      //包管run stack中的run的都年夜於minRun ，假如以後分區太小，就從前面掏出元素補足
      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);
      //斷定能否應當歸並，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;

在看外面的一個比擬主要的函數

/**
* 假如後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
      }
    }
  }