归并排序示意图
Mergesort(1,9)
递归分治
Mergesort(1,3)
Mergesort(1,5)
Mergesort(6,9)
Mergesort(4,5)
Mergesort(6,7)
Mergesort(8,9)
Mergesort(1,2)
Mergesort(3,3)
Mergesort(4,4)
Mergesort(5,5)
Mergesort(6,6)
Mergesort(7,7)
Mergesort(8,8)
Mergesort(9,9)
Mergesort(1,1)
Mergesort(2,2)
Merge(1,1,2)
合并子序列
Merge(1,2,3) Merge(4,4,5) Merge(6,6,7) Merge(8,8,9)
78 55 30 27 25 23 16 12
归并排序
归并排序是将两个（或两个以上） 归并排序是将两个（或两个以上）有序 表合并成一个新的有序表， 表合并成一个新的有序表，即把待排序 序列分为若干个子序列， 序列分为若干个子序列，每个子序列是 有序的。 有序的。然后再把有序子序列合并为整 体有序序列。 体有序序列。
归并排序(分治法)
//将两个有序子序列合并成一个 procedure merge(left,p,right:longint); var i,j,k:longint; begin i:=left; j:=p+1; k:=left; while (i<=p) and (j<=right) do begin if a[i] >a[j] then begin tmp[k]:=a[i]; inc(i); end else begin tmp[k]:=a[j]; inc(j); end; inc(k); end; while i<=p do begin tmp[k]:=a[i];inc(i);inc(k); end; while j<=right do begin tmp[k]:=a[j];inc(j);inc(k); end; for i:=left to right do a[i]:=tmp[i]; end; //归并排序过程：递归分治 procedure mergesort(left,right:longint); var mid:longint; begin if left<right then begin mid:=(left+right) div 2; mergesort(left,mid); mergesort(mid+1,right); merge(left,mid,right); end; end;
Merge(1,3,5)
Merge(6,7,9)
Merge(1, 5，9）
递归分治
12 23 78
6
25 16 27 55 30
12 23 78
6
25
16 27 55 30
12 23 78 12 23
6 25
16 27
55 30
12
23
78
6
பைடு நூலகம்25
16
27
55
30
23 12 78 23 12 78 25 23 12 合并子序列 25 6 6 27 16 55 30 27 16 6 55 30