歸并排序算法

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

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

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