C語(yǔ)言演示對(duì)歸并排序算法的優(yōu)化實(shí)現(xià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的核心部分。
相關(guān)文章
數(shù)組指針、指針數(shù)組以及二位數(shù)組的深入解析
下面來(lái)講講多維數(shù)組與指針的關(guān)系。與普通數(shù)組一樣，使用多維數(shù)組時(shí)，實(shí)際上將其自動(dòng)轉(zhuǎn)換為指向該數(shù)組第一個(gè)元素的指針2013-09-09
C語(yǔ)言的可變參數(shù)函數(shù)實(shí)現(xiàn)詳解
某些情況下我們希望函數(shù)的參數(shù)個(gè)數(shù)可以根據(jù)需要確定，因此c語(yǔ)言引入可變參數(shù)函數(shù)。典型的可變參數(shù)函數(shù)的例子有printf()、scanf()等,下面我就開(kāi)始講解2021-08-08
使用mmap實(shí)現(xiàn)多進(jìn)程對(duì)大文件拷貝
這篇文章主要介紹了使用mmap實(shí)現(xiàn)多進(jìn)程對(duì)大文件拷貝，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
C語(yǔ)言實(shí)現(xiàn)時(shí)間處理工具的示例代碼
這篇文章主要為大家詳細(xì)介紹了利用C語(yǔ)言實(shí)現(xiàn)時(shí)間處理工具的相關(guān)資料，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，需要的可以參考一下2022-09-09
這篇文章主要介紹了C++之重載 重定義與重寫(xiě)用法詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
C++實(shí)現(xiàn)圖書(shū)管理系統(tǒng)課程設(shè)計(jì)(面向?qū)ο?
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)圖書(shū)管理系統(tǒng)課程設(shè)計(jì)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
C語(yǔ)言多功能動(dòng)態(tài)通訊錄實(shí)現(xiàn)示例
這篇文章主要為大家介紹了C語(yǔ)言多功能動(dòng)態(tài)通訊錄實(shí)現(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-01-01
C語(yǔ)言實(shí)現(xiàn)撲克牌計(jì)算24點(diǎn)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言如何實(shí)現(xiàn)撲克牌計(jì)算24點(diǎn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
C++實(shí)現(xiàn)LeetCode(23.合并k個(gè)有序鏈表)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(23.合并k個(gè)有序鏈表),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++生成dll和調(diào)用dll的方法實(shí)例
C++生成dll和調(diào)用dll的方法實(shí)例，需要的朋友可以參考一下2013-03-03