歸并排序算法_第1頁
歸并排序算法_第2頁
歸并排序算法_第3頁
歸并排序算法_第4頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、歸并排序算法佚名 合并排序（MERGE SORT）是又一類不同的排序方法，合并的含義就是將兩個或兩個以上的有序數據序列合并成一個新的有序數據序列，因此它又叫歸并算法。它的基本思想就是假設數組A有N個元素，那么可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然后再兩兩合并，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合并，如此重復，值得得到一個長度為N的有序數據序列為止，這種排序方法稱為2路合并排序。 例如數組A有7個數據，分別是： 49 38 65 97 76 13 27，那么采用歸并排序算法的操作過程如圖7所示： 初始值 49 38 65 97 76 13 27 看成

2、由長度為1的7個子序列組成 第一次合并之后 38 49 65 97 13 76 27 看成由長度為1或2的4個子序列組成 第二次合并之后 38 49 65 97 13 27 76 看成由長度為4或3的2個子序列組成 第三次合并之后 13 27 38 49 65 76 97 圖6 歸并排序算法過程圖 合并算法的核心操作就是將一維數組中前后相鄰的兩個兩個有序序列合并成一個有序序列。合并算法也可以采用遞歸算法來實現，形式上較為簡單,但實用性很差。 合并算法的合并次數是一個非常重要的量,根據計算當數組中有3到4個元素時,合并次數 是2次,當有5到8個元素時,合并次數是3次,當有9到16個元素時,合并次

3、數是4次，按照這一 X 規律,當有N個子序列時可以推斷出合并的次數是X(2 =N,符合此條件的最小那個X)。 源程序：program hebing;const n=10;var a:array1.n of integer; i:integer;procedure init; var i:integer; begin for i:=1 to n do read(ai); readln; end;procedure merge(low,mid,high:integer); var h,i,j,k:integer; b:array1.n of integer; begin h:=low; i:=lo

4、w; j:=mid+1; while (h=mid) and (j=high) do begin if (ahmid then for k:=j to high do begin bi:=ak; i:=i+1; end else for k:=h to mid do begin bi:=ak; i:=i+1; end; for k:=low to high do ak:=bk; end;procedure mergesort(low,high:integer); var mid:integer; begin if lowhigh then begin mid:=(low+high) div 2; mergesort(

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論