歸并排序算法

1、歸并排序算法佚名 合并排序（MERGE SORT）是又一類不同的排序方法，合并的含義就是將兩個或兩個以上的有序數(shù)據(jù)序列合并成一個新的有序數(shù)據(jù)序列，因此它又叫歸并算法。它的基本思想就是假設(shè)數(shù)組A有N個元素，那么可以看成數(shù)組A是又N個有序的子序列組成，每個子序列的長度為1，然后再兩兩合并，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合并，如此重復(fù)，值得得到一個長度為N的有序數(shù)據(jù)序列為止，這種排序方法稱為2路合并排序。 例如數(shù)組A有7個數(shù)據(jù)，分別是： 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 歸并排序算法過程圖 合并算法的核心操作就是將一維數(shù)組中前后相鄰的兩個兩個有序序列合并成一個有序序列。合并算法也可以采用遞歸算法來實現(xiàn)，形式上較為簡單,但實用性很差。 合并算法的合并次數(shù)是一個非常重要的量,根據(jù)計算當(dāng)數(shù)組中有3到4個元素時,合并次數(shù) 是2次,當(dāng)有5到8個元素時,合并次數(shù)是3次,當(dāng)有9到16個元素時,合并次

3、數(shù)是4次，按照這一 X 規(guī)律,當(dāng)有N個子序列時可以推斷出合并的次數(shù)是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(