C語(yǔ)言演示對(duì)歸并排序算法的優(yōu)化實(shí)現(xiàn)

更新時(shí)間：2016年05月04日 11:16:45 作者：FanYu Kong

這篇文章主要介紹了C語(yǔ)言演示對(duì)歸并排序算法的優(yōu)化實(shí)現(xiàn),歸并排序的最差時(shí)間復(fù)雜度為(n\log n),最優(yōu)時(shí)間復(fù)雜為(n),存在可以改進(jìn)的空間,需要的朋友可以參考下

基礎(chǔ)

如果有兩個(gè)數(shù)組已經(jīng)有序，那么可以把這兩個(gè)數(shù)組歸并為更大的一個(gè)有序數(shù)組。歸并排序便是建立在這一基礎(chǔ)上。要將一個(gè)數(shù)組排序，可以將它劃分為兩個(gè)子數(shù)組分別排序，然后將結(jié)果歸并，使得整體有序。子數(shù)組的排序同樣采用這樣的方法排序，這個(gè)過(guò)程是遞歸的。

下面是示例代碼：

#include "timsort.h"
#include <stdlib.h>
#include <string.h>

// 將兩個(gè)長(zhǎng)度分別為l1, l2的已排序數(shù)組p1, p2合并為一個(gè)
// 已排序的目標(biāo)數(shù)組。
void merge(int target[], int p1[], int l1, int p2[], int l2);

void integer_timsort(int array[], int size){
  if(size <= 1) return;
 
  int partition = size/2;
  integer_timsort(array, partition);
  integer_timsort(array + partition, size - partition);
  merge(array, array, partition, array + partition, size - partition);
}

void merge(int target[], int p1[], int l1, int p2[], int l2){
  int *merge_to = malloc(sizeof(int) * (l1 + l2));

  // 當(dāng)前掃描兩數(shù)組的位置
  int i1, i2;
  i1 = i2 = 0;

  // 在合并過(guò)程中存放下一個(gè)元素的位置
  int *next_merge_element = merge_to;

  // 掃描兩數(shù)組，將較小的元素寫(xiě)入
  // merge_to. 當(dāng)兩數(shù)相等時(shí)我們選擇
  // 左邊的, 因?yàn)槲覀兿氡ＷC排序的穩(wěn)定性
  // 當(dāng)然對(duì)于integers這無(wú)關(guān)緊要，但這種想法是很重要的
  while(i1 < l1 && i2 < l2){
    if(p1[i1] <= p2[i2]){
      *next_merge_element = p1[i1];
      i1++;
    } else {
      *next_merge_element = p2[i2];
      i2++;
    }
    next_merge_element++;
  }

  // 如果有一個(gè)數(shù)組沒(méi)有掃描完，我們直接拷貝剩余的部分
  memcpy(next_merge_element, p1 + i1, sizeof(int) * (l1 - i1));
  memcpy(next_merge_element, p2 + i2, sizeof(int) * (l2 - i2));

  // 現(xiàn)在我們已經(jīng)將他們合并在了我們的額外的存儲(chǔ)空間里了
  // 是時(shí)候轉(zhuǎn)存到target了
  memcpy(target, merge_to, sizeof(int) * (l1 + l2));

  free(merge_to);
}

#include "timsort.h"
#include <stdlib.h>
#include <string.h>
 
// 將兩個(gè)長(zhǎng)度分別為l1, l2的已排序數(shù)組p1, p2合并為一個(gè)
// 已排序的目標(biāo)數(shù)組。
void merge(int target[], int p1[], int l1, int p2[], int l2);
 
void integer_timsort(int array[], int size){
  if(size <= 1) return;
 
  int partition = size/2;
  integer_timsort(array, partition);
  integer_timsort(array + partition, size - partition);
  merge(array, array, partition, array + partition, size - partition);
}
 
void merge(int target[], int p1[], int l1, int p2[], int l2){
  int *merge_to = malloc(sizeof(int) * (l1 + l2));
 
  // 當(dāng)前掃描兩數(shù)組的位置
  int i1, i2;
  i1 = i2 = 0;
 
  // 在合并過(guò)程中存放下一個(gè)元素的位置
  int *next_merge_element = merge_to;
 
  // 掃描兩數(shù)組，將較小的元素寫(xiě)入
  // merge_to. 當(dāng)兩數(shù)相等時(shí)我們選擇
  // 左邊的, 因?yàn)槲覀兿氡ＷC排序的穩(wěn)定性
  // 當(dāng)然對(duì)于integers這無(wú)關(guān)緊要，但這種想法是很重要的
  while(i1 < l1 && i2 < l2){
    if(p1[i1] <= p2[i2]){
      *next_merge_element = p1[i1];
      i1++;
    } else {
      *next_merge_element = p2[i2];
      i2++;
    }
    next_merge_element++;
  }
 
  // 如果有一個(gè)數(shù)組沒(méi)有掃描完，我們直接拷貝剩余的部分
  memcpy(next_merge_element, p1 + i1, sizeof(int) * (l1 - i1));
  memcpy(next_merge_element, p2 + i2, sizeof(int) * (l2 - i2));
 
  // 現(xiàn)在我們已經(jīng)將他們合并在了我們的額外的存儲(chǔ)空間里了
  // 是時(shí)候轉(zhuǎn)存到target了
  memcpy(target, merge_to, sizeof(int) * (l1 + l2));
 
  free(merge_to);
}

我不會(huì)總是貼出完整的代碼~

優(yōu)化
現(xiàn)在，如果你是一個(gè)C程序員，你可能已經(jīng)在吐槽了：我在每次合并過(guò)程中都申請(qǐng)并釋放了一次額外存儲(chǔ)空間（你可能也會(huì)不爽于我沒(méi)有檢查返回值是否為null,請(qǐng)無(wú)視之…如果這能讓你感覺(jué)好一點(diǎn)）

這個(gè)問(wèn)題只要一點(diǎn)點(diǎn)的改動(dòng)就可以修正：

void merge(int target[], int p1[], int l1, int p2[], int l2, int storage[]);
void integer_timsort_with_storage(int array[], int size, int storage[]);

void integer_timsort(int array[], int size){
  int *storage = malloc(sizeof(int) * size);
  integer_timsort_with_storage(array, size, storage);
  free(storage);
}

void merge(int target[], int p1[], int l1, int p2[], int l2, int storage[]);
void integer_timsort_with_storage(int array[], int size, int storage[]);
 
void integer_timsort(int array[], int size){
  int *storage = malloc(sizeof(int) * size);
  integer_timsort_with_storage(array, size, storage);
  free(storage);
}

現(xiàn)在我們有了排序函數(shù)的最頂層，做了一些內(nèi)存分配（setup）工作并將其傳入調(diào)用中。這是我們將要開(kāi)始優(yōu)化工作的模版，當(dāng)然最后實(shí)際可用的版本會(huì)更加復(fù)雜而不僅僅是優(yōu)化一塊內(nèi)存空間。

現(xiàn)在我們有了基本的歸并排序了，我們需要想想：我們能怎樣來(lái)優(yōu)化它？

一般來(lái)說(shuō)我們不能指望對(duì)于每一種情況都能達(dá)到最優(yōu)。歸并排序的性能已經(jīng)很接近比較排序的下界了。timsort的關(guān)鍵特性是極好的利用了數(shù)據(jù)中存在的規(guī)律。如果數(shù)據(jù)中存在普遍的規(guī)律，我們應(yīng)該盡可能的利用他們，如果沒(méi)有，我們的算法應(yīng)該保證不會(huì)比普通的歸并排序差太多。

如果你看過(guò)歸并排序的實(shí)現(xiàn)，你會(huì)發(fā)現(xiàn)其實(shí)所有的工作都是在合并（merge）的過(guò)程當(dāng)中完成的。所以?xún)?yōu)化的重點(diǎn)也就落在了這里。由此我們得出以下三點(diǎn)可能的優(yōu)化途徑：

1、能否使合并過(guò)程運(yùn)行的更快？
2、能否執(zhí)行更少的合并過(guò)程？
3、是否存在一些與其使用歸并排序不如使用其他排序的情況？

以上三個(gè)問(wèn)題的答案都是肯定的，并且這也是對(duì)歸并排序進(jìn)行優(yōu)化最為普遍的途徑。舉例來(lái)說(shuō)，遞歸的實(shí)現(xiàn)使得根據(jù)數(shù)組的規(guī)模使用不同的排序算法變的非常簡(jiǎn)單。歸并排序是一個(gè)很好的通用性排序算法，（具有很好的漸進(jìn)復(fù)雜度）但對(duì)小數(shù)組而言常數(shù)因子就顯得愈發(fā)重要，當(dāng)數(shù)組的大小小于某個(gè)值時(shí)（通常是7或者8左右）歸并排序的性能頻繁的低于插入排序。

這并不是timsort的原理，但是我們之后會(huì)用到插入排序，所以我們先開(kāi)個(gè)小差。

最簡(jiǎn)單的：假設(shè)我們有一個(gè)具有n個(gè)元素的已排序數(shù)組，并且在尾端有第n+1個(gè)元素的位置?，F(xiàn)在我們想要向里面添加一個(gè)新的元素并保持?jǐn)?shù)組有序。我們需要為新元素找到一個(gè)合適的位置并將比它大的數(shù)向后移動(dòng)。一種顯而易見(jiàn)的做法是將新元素放到第n+1個(gè)位置上，然后從后向前兩兩交換直到到達(dá)正確的位置（對(duì)較大的數(shù)組這并不是最好的做法：你可能想要對(duì)數(shù)據(jù)進(jìn)行二分查找（binary search）然后把剩下的元素不做比較的向后移動(dòng)。但是對(duì)小數(shù)組來(lái)說(shuō)這樣的做法反而不是很好，due to cache effects）

這就是插入排序工作的方式：當(dāng)你有了k個(gè)已排序的元素，將第k+1個(gè)元素插入其中，你就有了k+1個(gè)已排序的元素。反復(fù)如此直到整個(gè)數(shù)組有序。

下面是代碼：

void insertion_sort(int xs[], int length){
  if(length <= 1) return;
  int i;
  for(i = 1; i < length; i++){
    // i之前的數(shù)組已經(jīng)有序了，現(xiàn)在將xs[i]插入到里面
    int x = xs[i];
    int j = i - 1;

    // 將j向前移動(dòng)直到數(shù)組頭或者
    // something <= x, 并且其右邊的所有的元素都已經(jīng)
    // 右移了
    while(j >= 0 && xs[j] > x){
      xs[j+1], xs[j];
       j--;
    }  
    xs[j+1] = x;
  }
}

void insertion_sort(int xs[], int length){
  if(length <= 1) return;
  int i;
  for(i = 1; i < length; i++){
    // i之前的數(shù)組已經(jīng)有序了，現(xiàn)在將xs[i]插入到里面
    int x = xs[i];
    int j = i - 1;
 
    // 將j向前移動(dòng)直到數(shù)組頭或者
    // something <= x, 并且其右邊的所有的元素都已經(jīng)
    // 右移了
    while(j >= 0 && xs[j] > x){
      xs[j+1], xs[j];
       j--;
    }  
    xs[j+1] = x;
  }
}

現(xiàn)在排序的代碼會(huì)被修改為下面這樣：

void integer_timsort_with_storage(int array[], int size, int storage[]){
  if(size <= INSERTION_SORT_SIZE){
    insertion_sort(array, size);
    return;
  }
}

void integer_timsort_with_storage(int array[], int size, int storage[]){
  if(size <= INSERTION_SORT_SIZE){
    insertion_sort(array, size);
    return;
  }
}

你可以在這里查看這個(gè)版本

好了，讓我們回歸正題：優(yōu)化歸并排序。

能否執(zhí)行更少的合并過(guò)程？

對(duì)于一般的情況，不行。但是讓我們考慮一些普遍存在的情況。

假設(shè)我們有一個(gè)已經(jīng)排好序的數(shù)組，我們需要執(zhí)行多少次合并過(guò)程？

原則上來(lái)說(shuō)1次也不需要：數(shù)組已經(jīng)排好序了，不需要做任何多余的工作。所以一個(gè)可行的選擇是增加一個(gè)初始的檢查來(lái)確定數(shù)組是否已經(jīng)排好序了并在確認(rèn)之后立刻退出。

但是那樣會(huì)給排序算法增加很多額外的計(jì)算，雖然在判斷成功的情況下帶來(lái)很大的收益（將O(nlog(n))的復(fù)雜度下降到O(n)），但是如果判斷失敗了，會(huì)造成很多無(wú)用的計(jì)算。下面讓我們看看我們?cè)撛鯓訉?shí)現(xiàn)這種檢查并且無(wú)論其失敗與否都能將檢查的結(jié)果很好的利用起來(lái)。

假設(shè)我們遇到了下面的數(shù)組：

{5, 6, 7, 8, 9, 10, 1, 2, 3}

（現(xiàn)在暫且忽略我們會(huì)對(duì)小于n的數(shù)組使用不同的排序方法）

為了得到最好的合并策略，我們應(yīng)該在哪里進(jìn)行分段呢？

顯然在這里有兩個(gè)已經(jīng)排好序的子數(shù)組：5到10和1到3，如果選擇這兩段作為分段必然可以獲得很好的效果。

接下來(lái)提出一種片面的方法：

找出初始狀態(tài)下最長(zhǎng)的上升序列作為第一個(gè)分段（partition）,剩余部分作為第二個(gè)分段。

當(dāng)數(shù)據(jù)是由不多的幾個(gè)已排序的數(shù)組組成的情況下，這種方法表現(xiàn)的很好，但是這種方法存在十分糟糕的最差情況?？紤]一個(gè)完全逆序的數(shù)組，每次分段的第一段都只有一個(gè)數(shù)，所以在每次遞歸中第一段只有一個(gè)數(shù)，而要對(duì)第二段的n-1個(gè)元素進(jìn)行遞歸的歸并排序。這造成了明顯不令人滿(mǎn)意的O(n^2)的性能表現(xiàn)。

我們也可以人工的將過(guò)短的分段修改為總長(zhǎng)度一半的元素以避免這個(gè)問(wèn)題，但是這同樣也是不令人滿(mǎn)意的：我們額外的檢查工作基本沒(méi)有什么收益。

但是，基本的思路已經(jīng)明確了：利用已經(jīng)有序的子序列作為分段的單位。

困難的是第二段的選擇，為了避免出現(xiàn)糟糕的最差情況，我們需要保證我們的分段是盡可能的平衡的。

讓我們退一步看看是否有辦法改正它?？紤]下面這種有些奇怪的對(duì)普通歸并排序工作過(guò)程的逆向思考：

將整個(gè)數(shù)組切分成很多長(zhǎng)度為1的分區(qū)。

當(dāng)存在多個(gè)分區(qū)時(shí)，奇偶交替的兩兩合并這些分區(qū)（alternating even/odd）并用合并后的分區(qū)替代原先的兩個(gè)分區(qū)。

舉例來(lái)說(shuō)，如果我們有數(shù)組｛1, 2, 3, 4｝那么我們會(huì)這么做：

{{1}, {2}, {3}, {4}}
{{1, 2}, {3, 4}}
{{1, 2, 3, 4}}

很容易觀察到這和普通歸并排序的做法是相同的：我們只是將遞歸的過(guò)程變的明確并且用額外的存儲(chǔ)空間取代了棧。但是，這樣的方法更直觀的展現(xiàn)了我們應(yīng)該如何使用存在的已排序子序列：在第一步中，我們不將數(shù)組分割為長(zhǎng)度為1的分段，而是將其分割成很多已排序的分段。然后對(duì)這些分段以相同的方法執(zhí)行合并操作。

現(xiàn)在這個(gè)方法只有一個(gè)小問(wèn)題了：我們使用了一些并不需要使用的額外空間。普通的歸并排序使用了O(log(n))的棧空間。這個(gè)版本使用了O(n)的空間來(lái)存儲(chǔ)初始的分段情況。

那么為什么我們“等價(jià)的”算法卻有極為不同的空間消耗？

答案是我在他們的“等價(jià)”上面撒謊了。這種方法與普通的歸并排序最大的不同在于：普通歸并排序在分段操作上是“惰性”的，只有在需要生成下一級(jí)時(shí)才會(huì)生成足夠的分段并且在生成了下一級(jí)之后就會(huì)立刻的丟棄這些分段。

換句話(huà)說(shuō)，我們其實(shí)是在歸并的過(guò)程中邊合并邊生成分段而不是事先就生成了所有的分段。
現(xiàn)在，讓我們看看能否將這種想法轉(zhuǎn)換成算法。

在每一步中，生成一個(gè)新的最低級(jí)的分段（在普通歸并排序中這是一個(gè)單獨(dú)的元素，在我們的上面敘述的版本中這是一個(gè)已排序的子序列）。把它加入到一個(gè)存儲(chǔ)分段的棧中，并且不時(shí)的合并棧頂?shù)膬蓚€(gè)分段以減小棧的大小。不停的重復(fù)這樣的動(dòng)作直到?jīng)]有新的分段可以生成。然后將整個(gè)堆棧中的分段合并。

上面的算法還有一個(gè)地方?jīng)]有具體說(shuō)明：我們完全沒(méi)有說(shuō)明何時(shí)來(lái)執(zhí)行合并操作。

到此為止已經(jīng)有太多的文字而代碼太少了，所以我打算給出一個(gè)暫時(shí)的答案：隨便什么時(shí)候（好坑爹）。

現(xiàn)在，我們先寫(xiě)一些代碼。

// 我們使用固定的棧大小，這個(gè)大小要遠(yuǎn)遠(yuǎn)大于任何合理的棧高度
// 當(dāng)然，我們?nèi)匀恍枰獙?duì)溢出進(jìn)行檢查
#define STACK_SIZE 1024

typedef struct {
  int *index;
  int length;
} run;

typedef struct {
  int *storage;
  // 存儲(chǔ)已經(jīng)得到的分段(runs,原文作者將得到分段叫做run)
  run runs[STACK_SIZE];
  // 棧頂指針，指向下一個(gè)待插入的位置
  int stack_height;

  // 保持記錄我們已經(jīng)分段到哪里里，這樣我們可以知道在哪里開(kāi)始下一次的分段
  // 數(shù)組中index < partioned_up_to 是已經(jīng)分段并存儲(chǔ)在棧上的, 而index >= partioned_up_to
  // 的元素是還沒(méi)有存儲(chǔ)到棧上的. 當(dāng)partitioned_up_to == 數(shù)組長(zhǎng)度的時(shí)候所有的元素都在棧上了
  int *partitioned_up_to;

  int *array;
  int length;

} sort_state_struct;

typedef sort_state_struct *sort_state;

// 我們使用固定的棧大小，這個(gè)大小要遠(yuǎn)遠(yuǎn)大于任何合理的棧高度
// 當(dāng)然，我們?nèi)匀恍枰獙?duì)溢出進(jìn)行檢查
#define STACK_SIZE 1024
 
typedef struct {
  int *index;
  int length;
} run;
 
typedef struct {
  int *storage;
  // 存儲(chǔ)已經(jīng)得到的分段(runs,原文作者將得到分段叫做run)
  run runs[STACK_SIZE];
  // 棧頂指針，指向下一個(gè)待插入的位置
  int stack_height;
 
  // 保持記錄我們已經(jīng)分段到哪里里，這樣我們可以知道在哪里開(kāi)始下一次的分段
  // 數(shù)組中index < partioned_up_to 是已經(jīng)分段并存儲(chǔ)在棧上的, 而index >= partioned_up_to
  // 的元素是還沒(méi)有存儲(chǔ)到棧上的. 當(dāng)partitioned_up_to == 數(shù)組長(zhǎng)度的時(shí)候所有的元素都在棧上了
  int *partitioned_up_to;
 
  int *array;
  int length;
 
} sort_state_struct;
 
typedef sort_state_struct *sort_state;

我們將會(huì)給需要的所有函數(shù)傳入 sort_state的指針

這個(gè)排序的基礎(chǔ)邏輯代碼如下：

while(next_partition(&state)){
  while(should_collapse(&state)) merge_collapse(&state);
}
while(state.stack_height > 1) merge_collapse(&state);

while(next_partition(&state)){
  while(should_collapse(&state)) merge_collapse(&state);
}
while(state.stack_height > 1) merge_collapse(&state);

next_partition函數(shù)如果還有未入棧的元素則將一個(gè)新的分段壓入棧中并返回1，否則返回0。然后適當(dāng)?shù)膲嚎s棧。最后當(dāng)全部數(shù)組都分段完畢后將整個(gè)棧壓縮。

現(xiàn)在我們有了第一個(gè)適應(yīng)性版本的歸并排序：如果數(shù)組中有很多有序的子序列，我們就可以走一個(gè)很好的捷徑。如果沒(méi)有，我們的算法依然有（期望）O(nlog(n))的時(shí)間效率。

這個(gè)“期望”的效率有點(diǎn)不靠譜，在隨機(jī)的情況下我們需要一個(gè)好的策略來(lái)控制合并的過(guò)程。

我們來(lái)想一想是否有更好的限制條件。一個(gè)自然的想法來(lái)實(shí)現(xiàn)這個(gè)事情是在棧上維持一個(gè)不變式，不斷的執(zhí)行合并直到不變式滿(mǎn)足為止。

更進(jìn)一步，我們想要這個(gè)不變式來(lái)維持這個(gè)棧中最多只能有l(wèi)og(n)個(gè)元素

我們來(lái)考慮下面這個(gè)不變式：每個(gè)棧上的元素的長(zhǎng)度必須>=兩倍于其之下的元素長(zhǎng)度，所以棧頂元素是最小的，第二小的是棧頂元素的下一個(gè)元素，并且至少是棧頂元素的兩倍長(zhǎng)度。

這個(gè)不變式確實(shí)保證了棧中l(wèi)og(n)個(gè)元素的要求，但是卻造成了將每次棧的壓縮變得很復(fù)雜的趨勢(shì)，考慮棧中元素長(zhǎng)度如下的情況：

64, 32, 16, 8, 4, 2, 1

假設(shè)我們將一個(gè)長(zhǎng)度為1的分段放到棧上，就會(huì)產(chǎn)生如下的合并：

64, 32, 16, 8, 4, 2, 1, 1
64, 32, 16, 8, 4, 2, 2
64, 32, 16, 8, 4, 4
64, 32, 16, 8, 8
64, 32, 16, 16
64, 32, 32
64, 64
128

在之后對(duì)合并過(guò)程做了更多的優(yōu)化后，這種情況會(huì)顯得愈發(fā)糟糕（basically because it stomps on certain structure that might be present in the array）。但是現(xiàn)在我們的合并過(guò)程還是很簡(jiǎn)單的，所以我們沒(méi)有必要擔(dān)心它，先暫時(shí)這樣做就可以了。

有一件值得注意的事情：我們現(xiàn)在可以確定我們棧的大小了。假設(shè)棧頂元素的長(zhǎng)度為1，第二個(gè)元素長(zhǎng)度必然>=2，之后的必然>=4…所以棧中元素的總長(zhǎng)度是2^n-1, 因?yàn)樵?4位機(jī)器中在數(shù)組中最多只會(huì)有2^64個(gè)元素（這是一個(gè)相當(dāng)驚人的數(shù)組），所以我們的棧只需要最多65個(gè)元素，另外留出一個(gè)位置給新進(jìn)棧的元素，則我們需要分配66的空間給棧以保證永遠(yuǎn)不會(huì)出現(xiàn)overflow的情況。

另外還有一點(diǎn)值得注意，我們只需要檢查棧頂下面的一個(gè)元素長(zhǎng)度>=2 * 棧頂元素長(zhǎng)度，因?yàn)槲覀冊(cè)谌霔＿^(guò)程中總是保持這個(gè)不變式的，并且合并過(guò)程只會(huì)影響到棧頂兩個(gè)元素。

為了滿(mǎn)足不變式，我們現(xiàn)在將 should_collapse函數(shù)修改如下：

int should_collapse(sort_state state){
  if (state->stack_height <= 2) return 0;
 
  int h = state->stack_height - 1;

  int head_length = state->runs[h].length;
  int next_length = state->runs[h-1].length;

  return 2 * head_length > next_length;
}

int should_collapse(sort_state state){
  if (state->stack_height <= 2) return 0;
 
  int h = state->stack_height - 1;
 
  int head_length = state->runs[h].length;
  int next_length = state->runs[h-1].length;
 
  return 2 * head_length > next_length;
}

現(xiàn)在，我們的適應(yīng)性歸并排序完成了，贊！

回過(guò)頭看之前出過(guò)問(wèn)題的一個(gè)例子現(xiàn)在會(huì)如何。

考慮下面的逆序數(shù)組：

5, 4, 3, 2, 1

當(dāng)使用我們的適應(yīng)性歸并排序會(huì)發(fā)生什么？

棧的運(yùn)行過(guò)程如下：

{5}
{5}, {4}
{4, 5}
{4, 5}, {3}
{4, 5}, {3}, {2}
{4, 5}, {2, 3}
{2, 3, 4, 5}
{2, 3, 4, 5}, {1}
{1, 2, 3, 4, 5}

這是一個(gè)足夠清晰的合并策略了。

但是還有一個(gè)更好的辦法來(lái)對(duì)逆序的數(shù)組進(jìn)行排序：直接將其原地反轉(zhuǎn)。

可以很簡(jiǎn)單的修改我們的算法來(lái)利用到這一點(diǎn)，我們已經(jīng)尋找了遞增的子序列，當(dāng)找不遞增的子序列的時(shí)候可以很簡(jiǎn)單的尋找一個(gè)遞減的子序列，然后將其反轉(zhuǎn)為一個(gè)遞增的序列加入棧中。

根據(jù)上面的策略我們修改找序列的代碼如下：

if(next_start_index < state->array + state->length){
  if(*next_start_index < *start_index){
    // We have a decreasing sequence starting here.
    while(next_start_index < state->array + state->length){
      if(*next_start_index < *(next_start_index - 1)) next_start_index++;
      else break;
    }
    // Now reverse it in place.
    reverse(start_index, next_start_index - start_index);
  } else {
  // We have an increasing sequence starting here.
    while(next_start_index < state->array + state->length){
      if(*next_start_index >= *(next_start_index - 1)) next_start_index++;
      else break;
    }
  }
}

if(next_start_index < state->array + state->length){
  if(*next_start_index < *start_index){
    // We have a decreasing sequence starting here.
    while(next_start_index < state->array + state->length){
      if(*next_start_index < *(next_start_index - 1)) next_start_index++;
      else break;
    }
    // Now reverse it in place.
    reverse(start_index, next_start_index - start_index);
  } else {
  // We have an increasing sequence starting here.
    while(next_start_index < state->array + state->length){
      if(*next_start_index >= *(next_start_index - 1)) next_start_index++;
      else break;
    }
  }
}

和基本的逆序序列相同，我們的排序現(xiàn)在也可以很好的處理混合的情況了。比如下面這種數(shù)組：

{1, 2, 3, 4, 5, 4, 3, 2, 1}

執(zhí)行排序過(guò)程如下：

{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}, {1, 2, 3, 4}
{1, 1, 2, 2, 3, 3, 4, 4, 5}

這樣的情況比我們之前的實(shí)現(xiàn)又要好上很多！

最后我們還要給算法加上一點(diǎn)優(yōu)化：

在我們之前的歸并排序中有存在一個(gè)臨界點(diǎn)以便對(duì)于小數(shù)組轉(zhuǎn)換為插入排序，但在目前我們的適應(yīng)性版本中沒(méi)有這樣的設(shè)置，這意味著如果在沒(méi)有很多特殊結(jié)構(gòu)可利用的數(shù)組中我們的性能可能要低于普通的歸并排序。

回頭想想之前那個(gè)反轉(zhuǎn)的歸并排序的過(guò)程，將小數(shù)組改用插入排序的做法可以這樣理解：比起從1的長(zhǎng)度開(kāi)始劃分，我們從 INSERTION_SORT_SIZE開(kāi)始劃分，并使用插入排序來(lái)確保這一段是有序的。

這提示了我們一個(gè)自然的思路來(lái)改進(jìn)我們的適應(yīng)性版本：當(dāng)我們發(fā)現(xiàn)一個(gè)分段要小于一個(gè)設(shè)定值時(shí)，可以使用插入排序來(lái)將它增長(zhǎng)到設(shè)定長(zhǎng)度。

這使得我們更改了 next_partition函數(shù)的最后面的代碼如下：

if(run_to_add.length < MIN_RUN_SIZE){
  boost_run_length(state, &run_to_add);
}
state->partitioned_up_to = start_index + run_to_add.length;

if(run_to_add.length < MIN_RUN_SIZE){
  boost_run_length(state, &run_to_add);
}
state->partitioned_up_to = start_index + run_to_add.length;
boot_run_length函數(shù)如下：


void boost_run_length(sort_state state, run *run){
  // Need to make sure we don't overshoot the end of the array
  int length = state->length - (run->index - state->array);
  if(length > MIN_RUN_SIZE) length = MIN_RUN_SIZE;

  insertion_sort(run->index, length);
  run->length = length;
}

void boost_run_length(sort_state state, run *run){
  // Need to make sure we don't overshoot the end of the array
  int length = state->length - (run->index - state->array);
  if(length > MIN_RUN_SIZE) length = MIN_RUN_SIZE;
 
  insertion_sort(run->index, length);
  run->length = length;
}

這將算法應(yīng)用在隨機(jī)數(shù)據(jù)上時(shí)的性能表現(xiàn)提高到了一個(gè)和普通歸并排序相比相當(dāng)具有競(jìng)爭(zhēng)力的程度。

到這里我們終于得到了一個(gè)適應(yīng)性歸并排序，一定程度上可以說(shuō)是timsort的核心部分。

您可能感興趣的文章: