C說話演示對合並排序算法的優化完成。本站提示廣大學習愛好者：（C說話演示對合並排序算法的優化完成）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話演示對合並排序算法的優化完成正文
基本
假如有兩個數組曾經有序，那末可以把這兩個數組合並為更年夜的一個有序數組。合並排序就是樹立在這一基本上。要將一個數組排序，可以將它劃分為兩個子數組分離排序，然後將成果合並，使得全體有序。子數組的排序異樣采取如許的辦法排序，這個進程是遞歸的。
上面是示例代碼：
#include "timsort.h"
#include <stdlib.h>
#include <string.h>
// 將兩個長度分離為l1, l2的已排序數組p1, p2歸並為一個
// 已排序的目的數組。
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));
// 以後掃描兩數組的地位
int i1, i2;
i1 = i2 = 0;
// 在歸並進程中寄存下一個元素的地位
int *next_merge_element = merge_to;
// 掃描兩數組，將較小的元素寫入
// merge_to. 當兩數相等時我們選擇
// 右邊的, 由於我們想包管排序的穩固性
// 固然關於integers這可有可無，但這類設法主意是很主要的
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++;
}
// 假如有一個數組沒有掃描完，我們直接拷貝殘剩的部門
memcpy(next_merge_element, p1 + i1, sizeof(int) * (l1 - i1));
memcpy(next_merge_element, p2 + i2, sizeof(int) * (l2 - i2));
// 如今我們曾經將他們歸並在了我們的額定的存儲空間裡了
// 是時刻轉存到target了
memcpy(target, merge_to, sizeof(int) * (l1 + l2));
free(merge_to);
}
#include "timsort.h"
#include <stdlib.h>
#include <string.h>
// 將兩個長度分離為l1, l2的已排序數組p1, p2歸並為一個
// 已排序的目的數組。
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));
// 以後掃描兩數組的地位
int i1, i2;
i1 = i2 = 0;
// 在歸並進程中寄存下一個元素的地位
int *next_merge_element = merge_to;
// 掃描兩數組，將較小的元素寫入
// merge_to. 當兩數相等時我們選擇
// 右邊的, 由於我們想包管排序的穩固性
// 固然關於integers這可有可無，但這類設法主意是很主要的
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++;
}
// 假如有一個數組沒有掃描完，我們直接拷貝殘剩的部門
memcpy(next_merge_element, p1 + i1, sizeof(int) * (l1 - i1));
memcpy(next_merge_element, p2 + i2, sizeof(int) * (l2 - i2));
// 如今我們曾經將他們歸並在了我們的額定的存儲空間裡了
// 是時刻轉存到target了
memcpy(target, merge_to, sizeof(int) * (l1 + l2));
free(merge_to);
}
我不會老是貼出完全的代碼~
優化
如今，假如你是一個C法式員，你能夠曾經在吐槽了：我在每次歸並進程中都請求並釋放了一次額定存儲空間（你能夠也會不爽於我沒有檢討前往值能否為null,請疏忽之…假如這能讓你感到好一點）
這個成績只需一點點的修改便可以修改：
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);
}
如今我們有了排序函數的最頂層，做了一些內存分派（setup）任務並將其傳入挪用中。這是我們將要開端優化任務的模版，固然最初現實可用的版本會加倍龐雜而不只僅是優化一塊內存空間。
如今我們有了根本的合並排序了，我們須要想一想：我們能如何來優化它？
普通來講我們不克不及期望關於每種情形都能到達最優。合並排序的機能曾經很接近比擬排序的下界了。timsort的症結特征是極好的應用了數據中存在的紀律。假如數據中存在廣泛的紀律，我們應當盡量的應用他們，假如沒有，我們的算法應當包管不會比通俗的合並排序差太多。
假如你看過合並排序的完成，你會發明其實一切的任務都是在歸並（merge）的進程傍邊完成的。所以優化的重點也就落在了這裡。由此我們得出以下三點能夠的優化門路：
1、可否使歸並進程運轉的更快？
2、可否履行更少的歸並進程？
3、能否存在一些與其應用合並排序不如應用其他排序的情形？
以上三個成績的謎底都是確定的，而且這也是對合並排序停止優化最為廣泛的門路。舉例來講，遞歸的完成使得依據數組的范圍應用分歧的排序算法變的異常簡略。合並排序是一個很好的通用性排序算法，（具有很好的漸進龐雜度）但對小數組而言常數因子就顯得愈發主要，當數組的年夜小小於某個值時（平日是7或許8閣下）合並排序的機能頻仍的低於拔出排序。
這其實不是timsort的道理，然則我們以後會用到拔出排序，所以我們先開個小差。
最簡略的：假定我們有一個具有n個元素的已排序數組，而且在尾端有第n+1個元素的地位。如今我們想要向外面添加一個新的元素並堅持數組有序。我們須要為新元素找到一個適合的地位並將比它年夜的數向後挪動。一種不言而喻的做法是將新元素放到第n+1個地位上，然後從後向前兩兩交流直到達到准確的地位（對較年夜的數組這其實不是最好的做法：你能夠想要對數據停止二分查找（binary search）然後把剩下的元素不做比擬的向後挪動。然則對小數組來講如許的做法反而不是很好，due to cache effects）
這就是拔出排序任務的方法：當你有了k個已排序的元素，將第k+1個元素拔出個中，你就有了k+1個已排序的元素。重復如斯直到全部數組有序。
上面是代碼：
void insertion_sort(int xs[], int length){
if(length <= 1) return;
int i;
for(i = 1; i < length; i++){
// i之前的數組曾經有序了，如今將xs[i]拔出到外面
int x = xs[i];
int j = i - 1;
// 將j向前挪動直到數組頭或許
// something <= x, 而且其左邊的一切的元素都曾經
// 右移了
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之前的數組曾經有序了，如今將xs[i]拔出到外面
int x = xs[i];
int j = i - 1;
// 將j向前挪動直到數組頭或許
// something <= x, 而且其左邊的一切的元素都曾經
// 右移了
while(j >= 0 && xs[j] > x){
xs[j+1], xs[j];
j--;
}
xs[j+1] = x;
}
}
如今排序的代碼會被修正為上面如許：
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;
}
}
你可以在這裡檢查這個版本
好了，讓我們回歸正題：優化合並排序。
可否履行更少的歸並進程？
關於普通的情形，不可。然則讓我們斟酌一些廣泛存在的情形。
假定我們有一個曾經排好序的數組，我們須要履行若干次歸並進程？
准繩下去說1次也不須要：數組曾經排好序了，不須要做任何過剩的任務。所以一個可行的選擇是增長一個初始的檢討來肯定數組能否曾經排好序了並在確認以後連忙加入。
然則那樣會給排序算法增長許多額定的盤算，固然在斷定勝利的情形下帶來很年夜的收益（將O(nlog(n))的龐雜度降低到O(n)），然則假如斷定掉敗了，會形成許多無用的盤算。上面讓我們看看我們該如何完成這類檢討而且不管其掉敗與否都能將檢討的成果很好的應用起來。
假定我們碰到了上面的數組：
{5, 6, 7, 8, 9, 10, 1, 2, 3}
（如今暫且疏忽我們會對小於n的數組應用分歧的排序辦法）
為了獲得最好的歸並戰略，我們應當在哪裡停止分段呢？
明顯在這裡有兩個曾經排好序的子數組：5到10和1到3，假如選擇這兩段作為分段必定可以取得很好的後果。
接上去提出一種單方面的辦法：
找出初始狀況下最長的上升序列作為第一個分段（partition）,殘剩部門作為第二個分段。
當數據是由不多的幾個已排序的數組構成的情形下，這類辦法表示的很好，然則這類辦法存在非常蹩腳的最差情形。斟酌一個完整逆序的數組，每次分段的第一段都只要一個數，所以在每次遞歸中第一段只要一個數，而要對第二段的n-1個元素停止遞歸的合並排序。這形成了顯著不使人滿足的O(n^2)的機能表示。
我們也能夠人工的將太短的分段修正為總長度一半的元素以免這個成績，然則這異樣也是不使人滿足的：我們額定的檢討任務根本沒有甚麼收益。
然則，根本的思緒曾經明白了：應用曾經有序的子序列作為分段的單元。
艱苦的是第二段的選擇，為了不湧現蹩腳的最差情形，我們須要包管我們的分段是盡量的均衡的。
讓我們退一步看看能否有方法糾正它。斟酌上面這類有些奇異的對通俗合並排序任務進程的逆向思慮：
將全部數組切分紅許多長度為1的分區。
當存在多個分區時，奇偶瓜代的兩兩歸並這些分區（alternating even/odd）並用歸並後的分區替換本來的兩個分區。
舉例來講，假如我們稀有組｛1, 2, 3, 4｝那末我們會這麼做：
{{1}, {2}, {3}, {4}}
{{1, 2}, {3, 4}}
{{1, 2, 3, 4}}
很輕易不雅察到這和通俗合並排序的做法是雷同的：我們只是將遞歸的進程變的明白而且用額定的存儲空間代替了棧。然則，如許的辦法更直不雅的展示了我們應當若何應用存在的已排序子序列：在第一步中，我們不將數組朋分為長度為1的分段，而是將其朋分成許多已排序的分段。然後對這些分段以雷同的辦法履行歸並操作。
如今這個辦法只要一個小成績了：我們應用了一些其實不須要應用的額定空間。通俗的合並排序應用了O(log(n))的棧空間。這個版本應用了O(n)的空間來存儲初始的分段情形。
那末為何我們“等價的”算法卻有極其分歧的空間消費？
謎底是我在他們的“等價”下面說謊了。這類辦法與通俗的合並排序最年夜的分歧在於：通俗合並排序在分段操作上是“惰性”的，只要在須要生成下一級時才會生成足夠的分段而且在生成了下一級以後就會連忙的拋棄這些分段。
換句話說，我們實際上是在合並的進程中邊歸並邊生成份段而不是事前就生成了一切的分段。
如今，讓我們看看可否將這類設法主意轉換成算法。
在每步中，生成一個新的最初級的分段（在通俗合並排序中這是一個零丁的元素，在我們的下面論述的版本中這是一個已排序的子序列）。把它參加到一個存儲分段的棧中，而且不時的歸並棧頂的兩個分段以減小棧的年夜小。一直的反復如許的舉措直到沒有新的分段可以生成。然後將全部客棧中的分段歸並。
下面的算法還有一個處所沒有詳細解釋：我們完整沒有解釋什麼時候來履行歸並操作。
到此為止曾經有太多的文字而代碼太少了，所以我盤算給出一個臨時的謎底：隨意甚麼時刻（好坑爹）。
如今，我們先寫一些代碼。
// 我們應用固定的棧年夜小，這個年夜小要遠弘遠於任何公道的棧高度
// 固然，我們依然須要對溢出停止檢討
#define STACK_SIZE 1024
typedef struct {
int *index;
int length;
} run;
typedef struct {
int *storage;
// 存儲曾經獲得的分段(runs,原文作者將獲得分段叫做run)
run runs[STACK_SIZE];
// 棧頂指針，指向下一個待拔出的地位
int stack_height;
// 堅持記載我們曾經分段到哪裡裡，如許我們可以曉得在哪裡開端下一次的分段
// 數組中index < partioned_up_to 是曾經分段並存儲在棧上的, 而index >= partioned_up_to
// 的元素是還沒有存儲到棧上的. 當partitioned_up_to == 數組長度的時刻一切的元素都在棧上了
int *partitioned_up_to;
int *array;
int length;
} sort_state_struct;
typedef sort_state_struct *sort_state;
// 我們應用固定的棧年夜小，這個年夜小要遠弘遠於任何公道的棧高度
// 固然，我們依然須要對溢出停止檢討
#define STACK_SIZE 1024
typedef struct {
int *index;
int length;
} run;
typedef struct {
int *storage;
// 存儲曾經獲得的分段(runs,原文作者將獲得分段叫做run)
run runs[STACK_SIZE];
// 棧頂指針，指向下一個待拔出的地位
int stack_height;
// 堅持記載我們曾經分段到哪裡裡，如許我們可以曉得在哪裡開端下一次的分段
// 數組中index < partioned_up_to 是曾經分段並存儲在棧上的, 而index >= partioned_up_to
// 的元素是還沒有存儲到棧上的. 當partitioned_up_to == 數組長度的時刻一切的元素都在棧上了
int *partitioned_up_to;
int *array;
int length;
} sort_state_struct;
typedef sort_state_struct *sort_state;
我們將會給須要的一切函數傳入 sort_state的指針
這個排序的基本邏輯代碼以下：
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函數假如還有未入棧的元素則將一個新的分段壓入棧中並前往1，不然前往0。然後恰當的緊縮棧。最初當全體數組都分段終了後將全部棧緊縮。
如今我們有了第一個順應性版本的合並排序：假如數組中有許多有序的子序列，我們便可以走一個很好的捷徑。假如沒有，我們的算法仍然有（希冀）O(nlog(n))的時光效力。
這個“希冀”的效力有點不靠譜，在隨機的情形下我們須要一個好的戰略來掌握歸並的進程。
我們來想想能否有更好的限制前提。一個天然的設法主意來完成這個工作是在棧上保持一個不變式，赓續的履行歸並直到不變式知足為止。
更進一步，我們想要這個不變式來保持這個棧中最多只能有log(n)個元素
我們來斟酌上面這個不變式：每一個棧上的元素的長度必需>=兩倍於其之下的元素長度，所以棧頂元素是最小的，第二小的是棧頂元素的下一個元素，而且至多是棧頂元素的兩倍長度。
這個不變式確切包管了棧中log(n)個元素的請求，然則卻形成了將每次棧的緊縮變得很龐雜的趨向，斟酌棧中元素長度以下的情形：
64, 32, 16, 8, 4, 2, 1
假定我們將一個長度為1的分段放到棧上，就會發生以下的歸並：
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
在以後對歸並進程做了更多的優化後，這類情形會顯得愈發蹩腳（basically because it stomps on certain structure that might be present in the array）。然則如今我們的歸並進程照樣很簡略的，所以我們沒有需要擔憂它，先臨時如許做便可以了。
有一件值得留意的工作：我們如今可以肯定我們棧的年夜小了。假定棧頂元素的長度為1，第二個元素長度必定>=2，以後的必定>=4…所以棧中元素的總長度是2^n-1, 由於在64位機械中在數組中最多只會有2^64個元素（這是一個相當驚人的數組），所以我們的棧只須要最多65個元素，別的留出一個地位給新進棧的元素，則我們須要分派66的空間給棧以包管永久不會湧現overflow的情形。
別的還有一點值得留意，我們只須要檢討棧頂上面的一個元素長度>=2 * 棧頂元素長度，由於我們在入棧進程中老是堅持這個不變式的，而且歸並進程只會影響到棧頂兩個元素。
為了知足不變式，我們如今將 should_collapse函數修正以下：
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;
}
如今，我們的順應性合並排序完成了，贊！
回過火看之前出干預干與題的一個例子如今會若何。
斟酌上面的逆序數組：
5, 4, 3, 2, 1
當應用我們的順應性合並排序會產生甚麼？
棧的運轉進程以下：
{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}
這是一個足夠清楚的歸並戰略了。
然則還有一個更好的方法來對逆序的數組停止排序：直接將其原地反轉。
可以很簡略的修正我們的算法來應用到這一點，我們曾經尋覓了遞增的子序列，當找不遞增的子序列的時刻可以很簡略的尋覓一個遞加的子序列，然後將其反轉為一個遞增的序列參加棧中。
依據下面的戰略我們修正找序列的代碼以下：
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;
}
}
}
和根本的逆序序列雷同，我們的排序如今也能夠很好的處置混雜的情形了。好比上面這類數組：
{1, 2, 3, 4, 5, 4, 3, 2, 1}
履行排序進程以下：
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}, {1, 2, 3, 4}
{1, 1, 2, 2, 3, 3, 4, 4, 5}
如許的情形比我們之前的完成又要好上許多！
最初我們還要給算法加上一點優化：
在我們之前的合並排序中有存在一個臨界點以便關於小數組轉換為拔出排序，但在今朝我們的順應性版本中沒有如許的設置，這意味著假如在沒有許多特別構造可應用的數組中我們的機能能夠要低於通俗的合並排序。
回頭想一想之前誰人反轉的合並排序的進程，將小數組改用拔出排序的做法可以如許懂得：比起從1的長度開端劃分，我們從 INSERTION_SORT_SIZE開端劃分，並應用拔出排序來確保這一段是有序的。
這提醒了我們一個天然的思緒來改良我們的順應性版本：當我們發明一個分段要小於一個設定值時，可使用拔出排序來將它增加到設定長度。
這使得我們更改了 next_partition函數的最初面的代碼以下：
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函數以下：
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;
}
這將算法運用在隨機數據上時的機能表示進步到了一個和通俗合並排序比擬相當具有競爭力的水平。
到這裡我們終究獲得了一個順應性合並排序，必定水平上可以說是timsort的焦點部門。
