上一篇博文，討論了合并排序的遞歸實(shí)現(xiàn)。這篇文章，說說合并排序的非遞歸實(shí)現(xiàn)。

思路描述

假設(shè)一個(gè)數(shù)組，共有11個(gè)（0到10）元素。
首先，進(jìn)行“1+1”合并：即第0個(gè)和第1個(gè)合并，第2個(gè)和第3個(gè)合并，……，第8個(gè)和第9個(gè)合并，第10個(gè)不用合并；
然后，進(jìn)行“2+2”合并：0~3合并，4~7合并，此時(shí)剩下3個(gè)，雖然不足4，但是大于2，所以做“2+1”合并，即8~10合并；
再然后，進(jìn)行“4+4”合并，即0~7合并，此時(shí)剩下3個(gè)，3小于等于4，所以不用合并；
最后，進(jìn)行“8+8”合并，因?yàn)榭倲?shù)是11，雖然不足16，但是大于8，所以做“8+3”合并.

也許上面的描述把你搞暈了，沒關(guān)系，看看示意圖，秒懂。

下圖共11個(gè)元素，實(shí)線箭頭表示合并，虛線箭頭表示不做處理。

C語言代碼

#include <stdio.h> #include <string.h> //memcpy函數(shù)用這個(gè)頭文件 #include <stdlib.h> //malloc和free函數(shù)用這個(gè)頭文件/**此函數(shù)為了測試用，功能是打印數(shù)組，不想刷屏，所以沒有加換行*a是數(shù)組首地址*len是數(shù)組長度*/ void print_array(int *a, int len) {int i=0;for(i=0; i<len; ++i)printf("%d ",a[i]); }/** 將兩個(gè)有序數(shù)組b和c合并為一個(gè)有序數(shù)組a* b是第一個(gè)非降序數(shù)組的首地址，長度是len_b* c是第二個(gè)非降序數(shù)組的首地址，長度是len_c* a指向輸出數(shù)組的首地址* 注意：a數(shù)組需要調(diào)用者分配空間,且a數(shù)組不能與b或者c重疊*/void __merge(int *a, int *b, int len_b, int *c, int len_c) {int i = 0; // b的下標(biāo)int j = 0; // c的下標(biāo)int k = 0; // a的下標(biāo)int len = len_b + len_c; //計(jì)算出a數(shù)組的長度/*循環(huán)執(zhí)行條件是 i 和 j 都沒有越界*/while(i < len_b && j < len_c) //&&的優(yōu)先級更低 {/*比較b[i]和c[j],把較小的復(fù)制到a[k],同時(shí)i(或j)和k指向下一個(gè)元素*/if(b[i] <= c[j])a[k++] = b[i++];elsea[k++] = c[j++];}if(i == len_b) //說明b已經(jīng)處理完memcpy(a+k, c+j, (len-k)*sizeof(int));else //說明c已經(jīng)處理完memcpy(a+k, b+i, (len-k)*sizeof(int)); }void __merge_two_part(int a[], int len_1, int len_2) {int *sub_1 = a;int *sub_2 = a + len_1;/* 這里可以添加調(diào)試信息，展示排序過程，比如printf("merge ");print_array(sub_1,len_1);printf(" and ");print_array(sub_2,len_2);*/int temp_len = sizeof(int) * (len_1 + len_2); //計(jì)算需要多少字節(jié)int *temp = malloc(temp_len); //分配臨時(shí)空間if(temp == NULL){printf("malloc failed\n");return;}__merge(temp,sub_1,len_1,sub_2,len_2);memcpy(a,temp,temp_len); //此時(shí)數(shù)組a已經(jīng)有序/* 這里可以添加調(diào)試信息，展示排序過程，比如printf("---> ");print_array(a,len_1 + len_2);printf("\n");*/free(temp); }void __n_and_n_merge(int a[], int a_len, int n) {int left = a_len; //left用來計(jì)數(shù)，表示還剩多少個(gè)元素沒有參與合并int join_len = n + n; // n并n,合并后的長度是2n,用join_len表示while(left >= join_len){__merge_two_part(a,n,n);a += join_len; //使a指向下一段left -= join_len;}/*當(dāng)不夠n+n合并時(shí)，如果超過n個(gè)元素，仍然進(jìn)行合并；如果剩余元素小于等于n個(gè)，則不做處理*/ if(left > n) {__merge_two_part(a,n,left-n);} }void merge_sort_down2up(int a[], int len) {int step = 1; //初始步長while(step < len){__n_and_n_merge(a,len,step); //step + step 合并step *= 2; } }//測試函數(shù) int main(void) {int a[11]={9,8,5,3,2,9,4,6,7,1,0}; //11個(gè)數(shù) merge_sort_down2up(a,11);printf("最終結(jié)果：");print_array(a,11);printf("\n");return 0; }

代碼講解

已經(jīng)在代碼中添加了詳細(xì)的注釋，這里只說要點(diǎn)。
與排序相關(guān)的函數(shù)有4個(gè)。

void __merge(int *a, int *b, int len_b, int *c, int len_c); void __merge_two_part(int a[], int len_1, int len_2); void __n_and_n_merge(int a[], int a_len, int n); void merge_sort_down2up(int a[], int len);

前三個(gè)屬于內(nèi)部函數(shù)（我以雙下劃線開頭），第四個(gè)merge_sort_down2up屬于開放給用戶的函數(shù)，調(diào)用的時(shí)候傳入整形數(shù)組名和長度即可。

void __merge(int *a, int *b, int len_b, int *c, int len_c);
這個(gè)函數(shù)在上一篇博文中出現(xiàn)過，屬于歸并過程中最基本的“磚頭”，此函數(shù)被第二個(gè)函數(shù)__merge_two_part調(diào)用。

void __merge_two_part(int a[], int len_1, int len_2);
為了增強(qiáng)整個(gè)代碼的可讀性，我專門設(shè)計(jì)了這個(gè)接口。
這個(gè)函數(shù)的目的是把一個(gè)數(shù)組的前半部分（已經(jīng)為升序）和后半部分（已經(jīng)為升序）進(jìn)行合并排序。int a[]也可以寫為int *a,用來接收數(shù)組首地址；len_1表示前半部分的長度，len_2表示后半部分的長度。
假設(shè)數(shù)組a包含7個(gè)元素，前4個(gè)和后3個(gè)元素已經(jīng)分別有序，現(xiàn)在要做4+3合并，那么應(yīng)該這樣用
__merge_two_part(a, 4, 3);

示意圖如下：

調(diào)用后，數(shù)組a為升序。

void __n_and_n_merge(int a[], int a_len, int n);
此函數(shù)對整個(gè)數(shù)組進(jìn)行n+n合并。
注意：對于剩余的元素，當(dāng)不夠n+n合并時(shí)，如果大于n個(gè)元素，則進(jìn)行n+x合并； 如果小于等于n個(gè)，則不做處理.

a_len表示數(shù)組長度，每次調(diào)用時(shí)保持不變，n表示合并的步長，取值為1,2,4,8...;
n的初始值為1，反復(fù)調(diào)用此函數(shù)，調(diào)用后n取值翻倍，直到n大于等于a_len為止。

在void __merge_two_part(int a[], int len_1, int len_2)函數(shù)中添加一些打印信息，可以看出整個(gè)排序過程。截圖如下：

【參考資料】
http://www.cnblogs.com/xing901022/p/3671771.html

總結(jié)

以上是生活随笔為你收集整理的合并排序的非递归实现（自底向上设计）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。