排序 - 歸並排序（二）

　　歸並排序

　　歸並排序有兩種實現方法自底向上和自頂向下

　　 自底向上的方法

　　() 自底向上的基本思想

　　自底向上的基本思想是第趟歸並排序時將待排序的文件R[n]看作是n個長度為的有序子文件將這些子文件兩兩歸並若

　　n為偶數則得到

個長度為的有序子文件;若n為奇數則最後一個子文件輪空(不

　　參與歸並)故本趟歸並完成後前

個有序子文件長度為但最

　　後一個子文件長度仍為;第趟歸並則是將第趟歸並所得到的

個有

　　序的子文件兩兩歸並如此反復直到最後得到一個長度為n的有序文件為止

　　上述的每次歸並操作均是將兩個有序的子文件合並成一個有序的子文件故稱其為二路歸並排序類似地有k(k>)路歸並排序

　　() 二路歸並排序的全過程

　　【 參見動畫演示 】

　　() 一趟歸並算法

　　分析

　　在某趟歸並中設各子文件長度為length(最後一個子文件的長度可能小於length)則歸並前R[n]中共有

個有序的

　　子文件R

　　[length]R[length+length]…

　　注意

　　調用歸並操作將相鄰的一對子文件進行歸並時必須對子文件的個數可能是奇數以及最後一個子文件的長度小於length這兩種特殊

　　情況進行特殊處理

　　① 若子文件個數為奇數則最後一個子文件無須和其它子文件歸並(即本趟輪空);

　　② 若子文件個數為偶數則要注意最後一對子文件中後一子文件的區間上界是n

　　具體算法如下

　　void MergePass(SeqList Rint length)

　　{ //對R[n]做一趟歸並排序

　　int i;

　　for(i=;i+*length<=n;i=i+*length)

　　Merge(Rii+lengthi+*length);

　　//歸並長度為length的兩個相鄰子文件

　　if(i+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

趟歸並

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

　　}

　　注意：

　　自底向上的歸並排序算法雖然效率較高，但可讀性較差。tW.WiNgWit.cOM

From:http://tw.wingwit.com/Article/program/sjjg/201311/23777.html