非遞歸歸并排序算法
非遞歸排序與遞歸排序相反，將一個元素與相鄰元素構(gòu)成有序數(shù)組锯仪，再與旁邊數(shù)組構(gòu)成有序數(shù)組泵督，直至整個數(shù)組有序。
代碼實(shí)現(xiàn)
// 歸并排序非遞歸版
void MergeSort2(int *arr,int length)
{
int k = 1;/*k用來表示每次k個元素歸并*/
int *temp = (int *)malloc(sizeof(int) * length);
while(k < length)
{
MergePass(arr, k, length, temp);
k *= 2;
}
free(temp);
}
void MergePass(int *arr, int k, int n, int *temp)
{
int i = 0;
//從前往后,將2個長度為k的子序列合并為1個
while(i < n - 2*k + 1)
{
merge(arr, i, i + k-1, i + 2*k - 1, temp);
i += 2*k;
}
//合并有序的左半部分以及不及一個步長的右半部分
if(i < n - k )
{
merge(arr, i, i+k-1, n-1, temp);
}
}
直接說代碼吧庶喜。MergeSort2函數(shù)就是歸并排序的非遞歸方法小腊，里面就是個while循環(huán)，單看MergeSort2方法可能不太明白久窟，我們要先明白核心方法MergePass做了什么秩冈。
while循環(huán)的解釋
MergePass里面的while循環(huán)，其實(shí)就是把將2個長度為k的子序列合并為1個(其中merge方法跟上篇文章的遞歸版歸并排序的merge是完全一樣的)斥扛。最開始我看到這個方法的時候也看不懂入问，啥i < n - 2*k + 1，為啥又是i, i + k-1, i + 2*k - 1這3個數(shù)稀颁。其實(shí)它是把a(bǔ)rr數(shù)組分為了這樣的小序列芬失。如下標(biāo)為[i,i+k-1],這是左子序列，剛好有k個元素匾灶，右子序列為[i+k,i+2k-1]棱烂，也是k個。如果數(shù)組的元素個數(shù)n剛好是2k的倍數(shù)那是最好的阶女，各個長度為k的左右子序列分別合并颊糜，沒有遺留下不能配對的元素。但是一般不會這么湊巧秃踩，一般n都不會是2k的倍數(shù)衬鱼，所以i < n - 2*k + 1等價于i + 2k -1 < n等價于i + 2k -1 <= n-1，其中i + 2k -1剛好是右子序列的右邊界憔杨，這個i + 2k -1 <= n-1保證了把數(shù)組中的可以配對的子序列全都剝離出來了馁启。舉個例子，假設(shè)k=1芍秆，某數(shù)組有7個元素，前4個元素可以完全配對翠勉。
if判斷的解釋
如果n不是2k的倍數(shù)妖啥，那么所以余下的元素個數(shù)就是在1到2k-1個之間。下面的if就是解決這部分的对碌。為什么有i < n - k這個判斷條件荆虱？其實(shí)如果余下多余的元素，也不是一定要在這次的MergePass方法中處理。只有當(dāng)余下的元素的個數(shù)多于k個時(也就是存在右半部分的子序列怀读，1=<右半部分的個數(shù)<=k-1)需要把有k個元素的左序列與不足k個元素的右序列merge诉位。假設(shè)余下的元素個數(shù)<=k個，那么在這次MergePass不用處理(會在最后一次MergePass中被merge)菜枷。左序列的右邊界是i+k-1一定要小于最后一個元素的下標(biāo)n-1苍糠，所以有i+k-1<n-1，所以有i < n - k這個條件啤誊。這個判斷條件就保證了肯定存在右子序列岳瞭。
MergeSort2方法的邊界條件的解釋
MergeSort2方法中有個while循環(huán)，它的邊界條件是k < length蚊锹。這里我們探究一下瞳筏，可以寫成k <= length嗎？其實(shí)k的最大值是可以求出來的牡昆，現(xiàn)在我們就來算k的最大值姚炕。如果數(shù)組的個數(shù)的length剛好是2n，如2丢烘，4柱宦，8，16這樣的铅协，那么最后的k就等于 length/2 捷沸。如果length不是2n這樣的數(shù)，那么最后的k就等于2n狐史，其中n=log(length)的整數(shù)部分痒给；如length=34，n=5骏全，k就等于32苍柏。k其實(shí)就是小于length的最大的2n的數(shù)。所以這里的邊界條件寫k < length是對的姜贡。
其實(shí)非遞歸歸并排序算法的代碼也不多试吁，但是比較難理解，不過我覺得我前面的解釋的很清楚了楼咳，如果暫時看不懂熄捍，多讀幾遍。還是不懂的話可以在評論中@我母怜。
