熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

排序 - 歸並排序(三)

2013-11-15 15:40:11  來源: 數據結構 

  自頂向下的方法

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

  ()分治法的三個步驟

  設歸並排序的當前區間是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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.