閱讀134 返回首頁    go 阿裏雲 go 技術社區[雲棲]

排序算法係列之合並排序

 

     歸並排序（Merge sort，合並排序）是建立在歸並操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

一 歸並操作

基本思想

    歸並操作(merge)，指的是將兩個已經排序的序列合並成一個序列的操作，歸並排序算法依賴歸並操作。

歸並操作的過程如下：

  1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
  2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
  3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
  4. 重複步驟3直到某一指針達到序列尾
  5. 將另一序列剩下的所有元素直接複製到合並序列尾

歸並操作算法實現（c/c++）

void Merge(SeqList R，int low，int m，int high)
{//將兩個有序的子文件R[low..m)和R[m+1..high]歸並成一個有序的子文件R[low..high]
     int i=low，j=m+1，p=0； //置初始值
     RecType *R1； //R1是局部向量，若p定義為此類型指針速度更快
     R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))；
     if(! R1) //申請空間失敗
       Error("Insufficient memory available!")；
     while(i<=m&&j<=high) //兩子文件非空時取其小者輸出到R1[p]上
       R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；
     while(i<=m) //若第1個子文件非空，則複製剩餘記錄到R1中
       R1[p++]=R[i++]；
     while(j<=high) //若第2個子文件非空，則複製剩餘記錄到R1中
       R1[p++]=R[j++]；
     for(p=0，i=low；i<=high；p++，i++)
       R[i]=R1[p]；//歸並完成後將結果複製回R[low..high]
} //Merge

二 歸並排序

   歸並排序是基於歸並操作的排序算法，有多路歸並排序、兩路歸並排序 , 可用於內排序，也可以用於外排序

兩路歸並排序

基本思路

    設兩個有序的子文件(相當於輸入堆)放在同一向量中相鄰的位置上：R[low..m]，R[m+1..high]，先將它們合並到一個局部的暫存向量R1(相當於輸出堆)中，待合並完成後將R1複製回R[low..high]中。
（1）合並過程
    　合並過程中，設置i，j和p三個指針，其初值分別指向這三個記錄區的起始位置。合並時依次比較R[i]和R[j]的關鍵字，取關鍵字較小的記錄複製到R1[p]中，然後將被複製記錄的指針i或j加1，以及指向複製位置的指針p加1。
    　重複這一過程直至兩個輸入的子文件有一個已全部複製完畢(不妨稱其為空)，此時將另一非空的子文件中剩餘記錄依次複製到R1中即可。
（2）動態申請R1
    　實現時，R1是動態申請的，因為申請的空間可能很大，故須加入申請空間是否成功的處理。

算法實現

自底向上的方法

（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]，[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時終止
}

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

自頂向下的方法

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

（1）分治法的三個步驟
     設歸並排序的當前區間是R[low..high]，分治法的三個步驟是：
①分解：將當前區間一分為二，即求分裂點
                
②求解：遞歸地對兩個子區間R[low..mid]和R[mid+1..high]進行歸並排序；
③組合：將已排序的兩個子區間R[low..mid]和R[mid+1..high]歸並為一個有序的區間R[low..high]。
  遞歸的終結條件：子區間長度為1（一個記錄自然有序）。

（2）具體算法

void MergeSortDC(SeqList R，int low，int high)
{//用分治法對R[low..high]進行二路歸並排序
   int mid；
   if(low<high){//區間長度大於1
      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的執行過程如下圖所示的遞歸樹。

                    歸並排序示例： 自頂向下的二路歸並的執行過程

三 算法整體過程演示

    一個歸並排序的例子:對一個隨機點的鏈表進行排序：

    Merge sort animation2.gif

四 算法性能分析

1、穩定性
     　歸並排序是一種穩定的排序。
2、存儲結構要求
    　可用順序存儲結構。也易於在鏈表上實現。
3、時間複雜度
    　對長度為n的文件，需進行 趟二路歸並，每趟歸並的時間為O(n)，故其時間複雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。
4、空間複雜度
   　 需要一個輔助向量來暫存兩有序子文件歸並的結果，故其輔助空間複雜度為O(n)，顯然它不是就地排序。

五 參考文獻

1. 兩路歸並：https://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.5.1.3.htm；

2. 維基百科：https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F；

3. 算法導論

最後更新：2017-04-03 18:51:47

  上一篇：go Android自定義屬性時TypedArray的使用方法
  下一篇：go RTF文件格式