C語言演示對(duì)歸并排序算法的優(yōu)化實(shí)現(xiàn)
基礎(chǔ)
如果有兩個(gè)數(shù)組已經(jīng)有序，那么可以把這兩個(gè)數(shù)組歸并為更大的一個(gè)有序數(shù)組。歸并排序便是建立在這一基礎(chǔ)上。要將一個(gè)數(shù)組排序，可以將它劃分為兩個(gè)子數(shù)組分別排序，然后將結(jié)果歸并，使得整體有序。子數(shù)組的排序同樣采用這樣的方法排序，這個(gè)過程是遞歸的。
下面是示例代碼：
#include "timsort.h"
#include <stdlib.h>
#include <string.h>
// 將兩個(gè)長度分別為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;
// 在合并過程中存放下一個(gè)元素的位置
int *next_merge_element = merge_to;
// 掃描兩數(shù)組，將較小的元素寫入
// merge_to. 當(dāng)兩數(shù)相等時(shí)我們選擇
// 左邊的, 因?yàn)槲覀兿氡ＷC排序的穩(wěn)定性
// 當(dāng)然對(duì)于integers這無關(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ù)組沒有掃描完，我們直接拷貝剩余的部分
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è)長度分別為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;
// 在合并過程中存放下一個(gè)元素的位置
int *next_merge_element = merge_to;
// 掃描兩數(shù)組，將較小的元素寫入
// merge_to. 當(dāng)兩數(shù)相等時(shí)我們選擇
// 左邊的, 因?yàn)槲覀兿氡ＷC排序的穩(wěn)定性
// 當(dāng)然對(duì)于integers這無關(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ù)組沒有掃描完，我們直接拷貝剩余的部分
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)在吐槽了：我在每次合并過程中都申請并釋放了一次額外存儲(chǔ)空間（你可能也會(huì)不爽于我沒有檢查返回值是否為null,請無視之…如果這能讓你感覺好一點(diǎn)）
這個(gè)問題只要一點(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)用中。這是我們將要開始優(yōu)化工作的模版，當(dāng)然最后實(shí)際可用的版本會(huì)更加復(fù)雜而不僅僅是優(yōu)化一塊內(nèi)存空間。
現(xiàn)在我們有了基本的歸并排序了，我們需要想想：我們能怎樣來優(yōu)化它？
一般來說我們不能指望對(duì)于每一種情況都能達(dá)到最優(yōu)。歸并排序的性能已經(jīng)很接近比較排序的下界了。timsort的關(guān)鍵特性是極好的利用了數(shù)據(jù)中存在的規(guī)律。如果數(shù)據(jù)中存在普遍的規(guī)律，我們應(yīng)該盡可能的利用他們，如果沒有，我們的算法應(yīng)該保證不會(huì)比普通的歸并排序差太多。
如果你看過歸并排序的實(shí)現(xiàn)，你會(huì)發(fā)現(xiàn)其實(shí)所有的工作都是在合并（merge）的過程當(dāng)中完成的。所以優(yōu)化的重點(diǎn)也就落在了這里。由此我們得出以下三點(diǎn)可能的優(yōu)化途徑：
1、能否使合并過程運(yùn)行的更快？
2、能否執(zhí)行更少的合并過程？
3、是否存在一些與其使用歸并排序不如使用其他排序的情況？
以上三個(gè)問題的答案都是肯定的，并且這也是對(duì)歸并排序進(jìn)行優(yōu)化最為普遍的途徑。舉例來說，遞歸的實(shí)現(xiàn)使得根據(jù)數(shù)組的規(guī)模使用不同的排序算法變的非常簡單。歸并排序是一個(gè)很好的通用性排序算法，（具有很好的漸進(jìn)復(fù)雜度）但對(duì)小數(shù)組而言常數(shù)因子就顯得愈發(fā)重要，當(dāng)數(shù)組的大小小于某個(gè)值時(shí)（通常是7或者8左右）歸并排序的性能頻繁的低于插入排序。
這并不是timsort的原理，但是我們之后會(huì)用到插入排序，所以我們先開個(gè)小差。
最簡單的：假設(shè)我們有一個(gè)具有n個(gè)元素的已排序數(shù)組，并且在尾端有第n+1個(gè)元素的位置?，F(xiàn)在我們想要向里面添加一個(gè)新的元素并保持?jǐn)?shù)組有序。我們需要為新元素找到一個(gè)合適的位置并將比它大的數(shù)向后移動(dòng)。一種顯而易見的做法是將新元素放到第n+1個(gè)位置上，然后從后向前兩兩交換直到到達(dá)正確的位置（對(duì)較大的數(shù)組這并不是最好的做法：你可能想要對(duì)數(shù)據(jù)進(jìn)行二分查找（binary search）然后把剩下的元素不做比較的向后移動(dòng)。但是對(duì)小數(shù)組來說這樣的做法反而不是很好，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í)行更少的合并過程？
對(duì)于一般的情況，不行。但是讓我們考慮一些普遍存在的情況。
假設(shè)我們有一個(gè)已經(jīng)排好序的數(shù)組，我們需要執(zhí)行多少次合并過程？
原則上來說1次也不需要：數(shù)組已經(jīng)排好序了，不需要做任何多余的工作。所以一個(gè)可行的選擇是增加一個(gè)初始的檢查來確定數(shù)組是否已經(jīng)排好序了并在確認(rèn)之后立刻退出。
但是那樣會(huì)給排序算法增加很多額外的計(jì)算，雖然在判斷成功的情況下帶來很大的收益（將O(nlog(n))的復(fù)雜度下降到O(n)），但是如果判斷失敗了，會(huì)造成很多無用的計(jì)算。下面讓我們看看我們該怎樣實(shí)現(xiàn)這種檢查并且無論其失敗與否都能將檢查的結(jié)果很好的利用起來。
假設(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，如果選擇這兩段作為分段必然可以獲得很好的效果。
接下來提出一種片面的方法：
找出初始狀態(tài)下最長的上升序列作為第一個(gè)分段（partition）,剩余部分作為第二個(gè)分段。
當(dāng)數(shù)據(jù)是由不多的幾個(gè)已排序的數(shù)組組成的情況下，這種方法表現(xiàn)的很好，但是這種方法存在十分糟糕的最差情況?？紤]一個(gè)完全逆序的數(shù)組，每次分段的第一段都只有一個(gè)數(shù)，所以在每次遞歸中第一段只有一個(gè)數(shù)，而要對(duì)第二段的n-1個(gè)元素進(jìn)行遞歸的歸并排序。這造成了明顯不令人滿意的O(n^2)的性能表現(xiàn)。
我們也可以人工的將過短的分段修改為總長度一半的元素以避免這個(gè)問題，但是這同樣也是不令人滿意的：我們額外的檢查工作基本沒有什么收益。
但是，基本的思路已經(jīng)明確了：利用已經(jīng)有序的子序列作為分段的單位。
困難的是第二段的選擇，為了避免出現(xiàn)糟糕的最差情況，我們需要保證我們的分段是盡可能的平衡的。
讓我們退一步看看是否有辦法改正它?？紤]下面這種有些奇怪的對(duì)普通歸并排序工作過程的逆向思考：
將整個(gè)數(shù)組切分成很多長度為1的分區(qū)。
當(dāng)存在多個(gè)分區(qū)時(shí)，奇偶交替的兩兩合并這些分區(qū)（alternating even/odd）并用合并后的分區(qū)替代原先的兩個(gè)分區(qū)。
舉例來說，如果我們有數(shù)組｛1, 2, 3, 4｝那么我們會(huì)這么做：
{{1}, {2}, {3}, {4}}
{{1, 2}, {3, 4}}
{{1, 2, 3, 4}}
很容易觀察到這和普通歸并排序的做法是相同的：我們只是將遞歸的過程變的明確并且用額外的存儲(chǔ)空間取代了棧。但是，這樣的方法更直觀的展現(xiàn)了我們應(yīng)該如何使用存在的已排序子序列：在第一步中，我們不將數(shù)組分割為長度為1的分段，而是將其分割成很多已排序的分段。然后對(duì)這些分段以相同的方法執(zhí)行合并操作。
現(xiàn)在這個(gè)方法只有一個(gè)小問題了：我們使用了一些并不需要使用的額外空間。普通的歸并排序使用了O(log(n))的?？臻g。這個(gè)版本使用了O(n)的空間來存儲(chǔ)初始的分段情況。
那么為什么我們“等價(jià)的”算法卻有極為不同的空間消耗？
答案是我在他們的“等價(jià)”上面撒謊了。這種方法與普通的歸并排序最大的不同在于：普通歸并排序在分段操作上是“惰性”的，只有在需要生成下一級(jí)時(shí)才會(huì)生成足夠的分段并且在生成了下一級(jí)之后就會(huì)立刻的丟棄這些分段。
換句話說，我們其實(shí)是在歸并的過程中邊合并邊生成分段而不是事先就生成了所有的分段。
現(xiàn)在，讓我們看看能否將這種想法轉(zhuǎn)換成算法。
在每一步中，生成一個(gè)新的最低級(jí)的分段（在普通歸并排序中這是一個(gè)單獨(dú)的元素，在我們的上面敘述的版本中這是一個(gè)已排序的子序列）。把它加入到一個(gè)存儲(chǔ)分段的棧中，并且不時(shí)的合并棧頂?shù)膬蓚€(gè)分段以減小棧的大小。不停的重復(fù)這樣的動(dòng)作直到?jīng)]有新的分段可以生成。然后將整個(gè)堆棧中的分段合并。
上面的算法還有一個(gè)地方?jīng)]有具體說明：我們完全沒有說明何時(shí)來執(zhí)行合并操作。
到此為止已經(jīng)有太多的文字而代碼太少了，所以我打算給出一個(gè)暫時(shí)的答案：隨便什么時(shí)候（好坑爹）。
現(xiàn)在，我們先寫一些代碼。
// 我們使用固定的棧大小，這個(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)分段到哪里里，這樣我們可以知道在哪里開始下一次的分段
// 數(shù)組中index < partioned_up_to 是已經(jīng)分段并存儲(chǔ)在棧上的, 而index >= partioned_up_to
// 的元素是還沒有存儲(chǔ)到棧上的. 當(dāng)partitioned_up_to == 數(shù)組長度的時(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)分段到哪里里，這樣我們可以知道在哪里開始下一次的分段
// 數(shù)組中index < partioned_up_to 是已經(jīng)分段并存儲(chǔ)在棧上的, 而index >= partioned_up_to
// 的元素是還沒有存儲(chǔ)到棧上的. 當(dāng)partitioned_up_to == 數(shù)組長度的時(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è)很好的捷徑。如果沒有，我們的算法依然有（期望）O(nlog(n))的時(shí)間效率。
這個(gè)“期望”的效率有點(diǎn)不靠譜，在隨機(jī)的情況下我們需要一個(gè)好的策略來控制合并的過程。
我們來想一想是否有更好的限制條件。一個(gè)自然的想法來實(shí)現(xiàn)這個(gè)事情是在棧上維持一個(gè)不變式，不斷的執(zhí)行合并直到不變式滿足為止。
更進(jìn)一步，我們想要這個(gè)不變式來維持這個(gè)棧中最多只能有l(wèi)og(n)個(gè)元素
我們來考慮下面這個(gè)不變式：每個(gè)棧上的元素的長度必須>=兩倍于其之下的元素長度，所以棧頂元素是最小的，第二小的是棧頂元素的下一個(gè)元素，并且至少是棧頂元素的兩倍長度。
這個(gè)不變式確實(shí)保證了棧中l(wèi)og(n)個(gè)元素的要求，但是卻造成了將每次棧的壓縮變得很復(fù)雜的趨勢，考慮棧中元素長度如下的情況：
64, 32, 16, 8, 4, 2, 1
假設(shè)我們將一個(gè)長度為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ì)合并過程做了更多的優(yōu)化后，這種情況會(huì)顯得愈發(fā)糟糕（basically because it stomps on certain structure that might be present in the array）。但是現(xiàn)在我們的合并過程還是很簡單的，所以我們沒有必要擔(dān)心它，先暫時(shí)這樣做就可以了。
有一件值得注意的事情：我們現(xiàn)在可以確定我們棧的大小了。假設(shè)棧頂元素的長度為1，第二個(gè)元素長度必然>=2，之后的必然>=4…所以棧中元素的總長度是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è)元素長度>=2 * 棧頂元素長度，因?yàn)槲覀冊谌霔＿^程中總是保持這個(gè)不變式的，并且合并過程只會(huì)影響到棧頂兩個(gè)元素。
為了滿足不變式，我們現(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)性歸并排序完成了，贊！
回過頭看之前出過問題的一個(gè)例子現(xiàn)在會(huì)如何。
考慮下面的逆序數(shù)組：
5, 4, 3, 2, 1
當(dāng)使用我們的適應(yīng)性歸并排序會(huì)發(fā)生什么？
棧的運(yùn)行過程如下：
{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è)更好的辦法來對(duì)逆序的數(shù)組進(jìn)行排序：直接將其原地反轉(zhuǎn)。
可以很簡單的修改我們的算法來利用到這一點(diǎn)，我們已經(jīng)尋找了遞增的子序列，當(dāng)找不遞增的子序列的時(shí)候可以很簡單的尋找一個(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í)行排序過程如下：
{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)性版本中沒有這樣的設(shè)置，這意味著如果在沒有很多特殊結(jié)構(gòu)可利用的數(shù)組中我們的性能可能要低于普通的歸并排序。
回頭想想之前那個(gè)反轉(zhuǎn)的歸并排序的過程，將小數(shù)組改用插入排序的做法可以這樣理解：比起從1的長度開始劃分，我們從 INSERTION_SORT_SIZE開始劃分，并使用插入排序來確保這一段是有序的。
這提示了我們一個(gè)自然的思路來改進(jìn)我們的適應(yīng)性版本：當(dāng)我們發(fā)現(xiàn)一個(gè)分段要小于一個(gè)設(shè)定值時(shí)，可以使用插入排序來將它增長到設(shè)定長度。
這使得我們更改了 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)具有競爭力的程度。
到這里我們終于得到了一個(gè)適應(yīng)性歸并排序，一定程度上可以說是timsort的核心部分。
相關(guān)文章
這篇文章主要介紹了C語言實(shí)現(xiàn)文件讀寫，文件是一段數(shù)據(jù)的集合，這些數(shù)據(jù)可以是有規(guī)則的，也可以是無序的集合。在stdio.h有一個(gè)非常重要的東西，文件指針，每個(gè)文件都會(huì)在內(nèi)存中開辟一塊空間，用于存放文件的相關(guān)信息2022-12-12
VC創(chuàng)建圓角dialog的實(shí)現(xiàn)方法
這篇文章主要介紹了VC創(chuàng)建圓角dialog的實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了圓角dialog對(duì)話框的創(chuàng)建步驟與相關(guān)操作技巧,需要的朋友可以參考下2016-08-08
這篇文章主要介紹了c語言鏈表操作示例，代碼中有注釋,需要的朋友可以參考下2014-03-03
這一篇介紹一下 C++ 編程中與面向?qū)ο蟛⒘械牧硪淮蠓种А盒途幊蹋@一篇主要介紹函數(shù)模板、類模板和成員模板三大部分,需要的朋友可以參考下2021-08-08
對(duì)C++ 了解的人都應(yīng)該知道虛函數(shù)（Virtual Function）是通過一張?zhí)摵瘮?shù)表（Virtual Table）和一個(gè)指向虛函數(shù)表的指針（vptr）來實(shí)現(xiàn)的2013-09-09
C++實(shí)現(xiàn)LeetCode(131.拆分回文串)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(131.拆分回文串),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++11中的智能指針shared_ptr、weak_ptr源碼解析
本文是基于gcc-4.9.0的源代碼進(jìn)行分析，shared_ptr和weak_ptr是C++11才加入標(biāo)準(zhǔn)的,僅對(duì)C++智能指針shared_ptr、weak_ptr源碼進(jìn)行解析，需要讀者有一定的C++基礎(chǔ)并且對(duì)智能指針有所了解2021-09-09
今天小編就為大家分享一篇關(guān)于判斷兩顆二叉樹是否相似的兩種方法，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-03-03
C++實(shí)現(xiàn)LeetCode(154.尋找旋轉(zhuǎn)有序數(shù)組的最小值之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(154.尋找旋轉(zhuǎn)有序數(shù)組的最小值之二),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
下面小編就為大家?guī)硪黄狢基礎(chǔ) redis緩存訪問詳解。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-06-06