生命是一種過(guò)程

歸并排序

歸并排序

???? 歸并排序有兩種實(shí)現(xiàn)方法：自底向上和自頂向下。

1、 自底向上的方法
（1） 自底向上的基本思想
???? 自底向上的基本思想是：第1趟歸并排序時(shí)，將待排序的文件R[1..n]看作是n個(gè)長(zhǎng)度為1的有序子文件，將這些子文件兩兩歸并，若n為偶數(shù)，則得到個(gè)長(zhǎng)度為2的有序子文件；若n為奇數(shù)，則最后一個(gè)子文件輪空(不

參與歸并)。故本趟歸并完成后，前個(gè)有序子文件長(zhǎng)度為2，但最

后一個(gè)子文件長(zhǎng)度仍為1；第2趟歸并則是將第1趟歸并所得到的個(gè)有

序的子文件兩兩歸并，如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序文件為止。
???? 上述的每次歸并操作，均是將兩個(gè)有序的子文件合并成一個(gè)有序的子文件，故稱其為"二路歸并排序"。類似地有k(k>2)路歸并排序。

（2） 二路歸并排序的全過(guò)程
? 【 參見動(dòng)畫演示 】

（3） 一趟歸并算法
?分析：
????? 在某趟歸并中，設(shè)各子文件長(zhǎng)度為length(最后一個(gè)子文件的長(zhǎng)度可能小于length)，則歸并前R[1..n]中共有個(gè)有序的子文件：R

[1..length]，R[length+1..2length]，…，。
注意：
???? 調(diào)用歸并操作將相鄰的一對(duì)子文件進(jìn)行歸并時(shí)，必須對(duì)子文件的個(gè)數(shù)可能是奇數(shù)、以及最后一個(gè)子文件的長(zhǎng)度小于length這兩種特殊情況進(jìn)行特殊處理：
　　① 若子文件個(gè)數(shù)為奇數(shù)，則最后一個(gè)子文件無(wú)須和其它子文件歸并(即本趟輪空)；
　　② 若子文件個(gè)數(shù)為偶數(shù)，則要注意最后一對(duì)子文件中后一子文件的區(qū)間上界是n。

?具體算法如下：
??? void MergePass(SeqList R，int length)
???? { //對(duì)R[1..n]做一趟歸并排序
????? int i；
????? for(i=1;i+2*length-1<=n;i=i+2*length)
????? Merge(R，i，i+length-1，i+2*length-1)；
?????????? //歸并長(zhǎng)度為length的兩個(gè)相鄰子文件
????? if(i+length-1<n) //尚有兩個(gè)子文件，其中后一個(gè)長(zhǎng)度小于length
???????? Merge(R，i，i+length-1，n)； //歸并最后兩個(gè)子文件
????? //注意：若i≤n且i+length-1≥n時(shí)，則剩余一個(gè)子文件輪空，無(wú)須歸并
???? } //MergePass

（4）二路歸并排序算法
? void MergeSort(SeqList R)
?? {//采用自底向上的方法，對(duì)R[1..n]進(jìn)行二路歸并排序
???? int length；
???? for(1ength=1；length<n；length*=2) //做趟歸并

??????? MergePass(R，length)； //有序段長(zhǎng)度≥n時(shí)終止
?? }

注意：
???? 自底向上的歸并排序算法雖然效率較高，但可讀性較差。

????????????????

3、時(shí)間復(fù)雜度
??? 　對(duì)長(zhǎng)度為n的文件，需進(jìn)行趟二路歸并，每趟歸并的時(shí)間為O(n)，故其時(shí)間復(fù)雜度無(wú)論是在最好情況下還是在最壞情況下均是O(nlgn)。

posted on 2006-07-20 15:47 xnlijun 閱讀(979) 評(píng)論(2)  編輯  收藏