9.8.1 歸并排序算法（1）

歸并”一詞的中文含義就是合并,、并入的意思，而在數(shù)據(jù)結(jié)構(gòu)中的定義是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表,。

歸并排序（Merging Sort）就是利用歸并的思想實(shí)現(xiàn)的排序方法,。它的原理是假設(shè)初始序列含有n個(gè)記錄，則可以看成是n個(gè)有序的子序列,，每個(gè)子序列的長(zhǎng)度為1,，然后兩兩歸并，得到.n/2.（.x.表示不小于x的最小整數(shù)）個(gè)長(zhǎng)度為2或1的有序子序列,；再兩兩歸并,，……，如此重復(fù),，直至得到一個(gè)長(zhǎng)度為n的有序序列為止,，這種排序方法稱為2路歸并排序。7

注：7本書只介紹2路歸并排序,。

好了,，有了對(duì)歸并排序的初步認(rèn)識(shí)后，我們來看代碼,。

/* 對(duì)順序表L作歸并排序 */  
void MergeSort（SqList *L）  
{  
MSort（L->r,L->r,1,L->length）;  
} 

一句代碼,，別奇怪，它只是調(diào)用了另一個(gè)函數(shù)而已,。為了與前面的排序算法統(tǒng)一,，我們用了同樣的參數(shù)定義SqList *L，由于我們要講解的歸并排序?qū)崿F(xiàn)需要用到遞歸調(diào)用8,，因此我們外封裝了一個(gè)函數(shù),。假設(shè)現(xiàn)在要對(duì)數(shù)組{50,10,90,30,70,40,80,60,20}進(jìn)行排序，L.length=9,，我現(xiàn)來看看MSort的實(shí)現(xiàn),。

/* 將SR[s..t]歸并排序?yàn)門R1[s..t] */  
1 void MSort（int SR[],int TR1[],int s, int t）  
2 {  
3 int m;  
4 int TR2[MAXSIZE+1];  
5 if（s==t）  
6 TR1[s]=SR[s];  
7 else  
8 {  
9 m=（s+t）/2; /* 將SR[s..t]平分為SR[s..m]和SR[m+1..t] */  
10 MSort(SR,TR2,s,m);/*遞歸將SR[s..m]歸并為有序的TR2[s..m]*/  
11 MSort(SR,TR2,m+1,t);/*遞歸將SR[m+1..t]歸并為有序TR2[m+1..t]*/  
12 Merge(TR2,TR1,s,m,t);/*將TR2[s..m]和TR2[m+1..t]*/  
/*歸并到TR1[s..t]*/  
13 }  
14 } 

1．MSort被調(diào)用時(shí)，SR與TR1都是{50,10,90,30,70,40,80,60,20},，s=1，t=9,，最終我們的目的就是要將R1中的數(shù)組排好順序,。

2．第5行，顯然s不等于t,，執(zhí)行第8～13行語句塊,。

3．第9行，m=（1+9）/2=5,。m就是序列的正中間下標(biāo),。

4．此時(shí)第10行，調(diào)用“MSort（SR,TR2,1,5）;”的目標(biāo)就是將數(shù)組SR中的第1～5的關(guān)鍵字歸并到有序的TR2（調(diào)用前TR2為空數(shù)組）,，第11行,，調(diào)用“MSort（SR,TR2,6,9）;”的目標(biāo)就是將數(shù)組SR中的第6～9的關(guān)鍵字歸并到有序的TR2,。也就是說，在調(diào)用這兩句代碼之前,，代碼已經(jīng)準(zhǔn)備將數(shù)組分成了兩組了,，如圖9‐8‐2所示。

注：8也可以不用遞歸實(shí)現(xiàn),，后面有提及,。

圖9-8-2

5．第12行，函數(shù)Merge的代碼細(xì)節(jié)一會(huì)再講,，調(diào)用“Merge（TR2,TR1,1,5, 9）;”的目標(biāo)其實(shí)就是將第10和11行代碼獲得的數(shù)組TR2（注意它是下標(biāo)為1～5和6～9的關(guān)鍵字分別有序）歸并為TR1,，此時(shí)相當(dāng)于整個(gè)排序就已經(jīng)完成了，如圖9‐8‐3所示,。

（點(diǎn)擊查看大圖）圖9-8-3

6．再來看第10行遞歸調(diào)用進(jìn)去后,，s=1，t=5,，m=（1+5）/2=3,。此時(shí)相當(dāng)于將5個(gè)記錄拆分為三個(gè)和兩個(gè)。繼續(xù)遞歸進(jìn)去,，直到細(xì)分為一個(gè)記錄填入TR2,，此時(shí)s與t相等，遞歸返回,，如圖9‐8‐4的左圖所示,。每次遞歸返回后都會(huì)執(zhí)行當(dāng)前遞歸函數(shù)的第12行，將TR2歸并到TR1中,，如圖9‐8‐4的右圖所示,，最終使得當(dāng)前序列有序。