生命是一種過程

歸并排序

歸并排序

???? 歸并排序有兩種實現方法：自底向上和自頂向下。

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

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

后一個子文件長度仍為1；第2趟歸并則是將第1趟歸并所得到的個有

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

（2） 二路歸并排序的全過程
? 【 參見動畫演示 】

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

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

?具體算法如下：
??? void MergePass(SeqList R，int length)
???? { //對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)；
?????????? //歸并長度為length的兩個相鄰子文件
????? if(i+length-1<n) //尚有兩個子文件，其中后一個長度小于length
???????? Merge(R，i，i+length-1，n)； //歸并最后兩個子文件
????? //注意：若i≤n且i+length-1≥n時，則剩余一個子文件輪空，無須歸并
???? } //MergePass

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

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

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

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

3、時間復雜度
??? 　對長度為n的文件，需進行趟二路歸并，每趟歸并的時間為O(n)，故其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。

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