排序 - 歸並排序（三）

　　自頂向下的方法

　　采用分治法進行自頂向下的算法設計形式更為簡潔

　　()分治法的三個步驟

　　設歸並排序的當前區間是R[lowhigh]分治法的三個步驟是

　　①分解將當前區間一分為二即求分裂點

　　

　　②求解遞歸地對兩個子區間R[lowmid]和R[mid+high]進行歸並排序;

　　③組合將已排序的兩個子區間R[lowmid]和R[mid+high]歸並為一個有序的區間R[lowhigh]

　　遞歸的終結條件子區間長度為(一個記錄自然有序)

　　()具體算法

　　void MergeSortDC(SeqList Rint lowint high)

　　{//用分治法對R[lowhigh]進行二路歸並排序

　　int mid;

　　if(low

　　mid=(low+high)/2; //分解

　　MergeSortDC(R，low，mid); //遞歸地對R[low..mid]排序

　　MergeSortDC(R，mid+1，high); //遞歸地對R[mid+1..high]排序

　　Merge(R，low，mid，high); //組合，將兩個有序區歸並為一個有序區

　　}

　　}//MergeSortDC

　　(3)算法MergeSortDC的執行過程

　　算法MergeSortDC的執行過程如下圖所示的遞歸樹。Tw.WInGwiT.CoM

　　

　　二、算法分析

　　1、穩定性

　　歸並排序是一種穩定的排序。

　　2、存儲結構要求

　　可用順序存儲結構。也易於在鏈表上實現。

　　3、時間復雜度

　　對長度為n的文件，需進行

趟二路歸並，每趟歸並的時間為O(n)，故其時間復雜度無論是在最好情況下還是在最壞情況下均

　　是O(nlgn)。

　　4、空間復雜度

　　需要一個輔助向量來暫存兩有序子文件歸並的結果，故其輔助空間復雜度為O(n)，顯然它不是就地排序。

　　注意：

　　若用單鏈表做存儲結構，很容易給出就地的歸並排序。具體【參見練習】。

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