首页 > 代码库 > 归并排序

归并排序

 

归并排序是分治思想的一个很典型的应用,它将待排序数组A[0...n-1]划分为A[0...m]和A[m+1...n]两个部分(其中m=(n-1)/2),然后对两个子数组分别排序,并以较小的时间代价将合并

 

一.算法

1.归并排序算法

ALGORITHM Mergesort(A[0..n-1],B[0..n-1],left,right)
//Input:待排序数组A[0...n-1],辅助数组B[0..n-1]
//Output:递增排好序的数组A
//递归终止条件,当每个子数组中只有一个元素

if(left>=right)       
  return; 
m
= (left+right)/2;

//分别对两个子数组排序
Mergesort(A,B,left,m); 
Mergesort(A,B,m
+1,right);

//合并排好序的两个子数组
Merge(A,B,left,m,right);

 

2.合并排好序的子数组

 1 ALGORITHM Merge(A[0..n-1],B[0..n-1],left,mid,right)
 2 //Input:排好序的子数组A[left..mid]和A[mid+1,right]
 3 //Output:排好序的数组A[left..right]
 4 
 5 for i←left to right
 6   B[i] = A[i];
 7 
 8 i ← left; j ← mid+1; k ← left;
 9 
10 while i<=mid and j<=right 
11   if(B[i]<=B[j]) 
12     A[k++] = B[i++];
13   else  
14     A[k++] = B[j++];
15 
16 while(i<=mid)  A[k++] = B[i++];
17 while(j<=right)  A[k++] = B[j++];

 

二.归并排序算法的效率(假设n是2的冥)

设C(n)是对输入规模为n的数组进行归并排序的代价,Cmerge(n)表示对排好序的子数组进行合并的代价,于是有下列递推关系式

 C(n) = C(n/2) + Cmerge(n)

这个递归式的终止条件是Cworst(1) = 0,因为一个元素不需要再进行排序,代价为0.

在最坏情况和平均情况下,它的解都是C(n) = O(nlogn)

 

三.归并排序的正确性证明--循环不变式

Merge的工作是对排好序的子数组进行合并,A[left..right]划分成A[left..mid]和A[mid+1,right]两个子数组,假设A[left..mid]和A[mid+1,right]都是已经排好序的,Merge过程将它们合并成A[left..mid]这个更大的有序数组

进行Merge的详细过程如下:

  将左右部分已分别排序的数组A[left..right]复制到辅助数组B[left..right]中,每次从两个子数组取出第一个元素进行比较,取较小的复制回原数组。算法10-17行在执行过程中,维持以下循环不变式:

  在while循环每迭代一次时,子数组A[left..k-1]按从小到大的顺序包含数组B[left..mid]和B[mid+1,right]中的k-left个最小元素。进而,B[i]和B[j]是各自所在子数组中未被复制回数组A的最小元素。

 

对循环不变式的证明有三个步骤:

(1)初始化时为真

(2)每次循环开始前为真,该次循环结束时仍为真

(3)循环结束时为真

 

初始化:循环第一次迭代以前,有k=left,所以子数组A[left..k-1]为空,这个空的子数组包含两个已排序子数组B[left..mid]和B[mid+1,right]的k-left = 0个最小元素。又因为i和j分别为left和mid+1,所以B[i]和B[j]分别是各自所在子数组中未被复制回原数组的最小值

 

保持:当两个子数组中都还剩余元素时,首先假设B[i]≤B[j],那么B[i]是未复制回数组A的最小元素。因为A[left..k-1]包含k-left个最小元素。所以在B[i]复制回A以后,A[left..k]将包含k-left+1个最小元素,增加k的值和i的值后,为下次循环重新建立了新的循环不变式。若B[i]>B[j]也是同样的分析。

     当B[left..mid]和B[mid+1,right]中有一个子数组元素已经用完时,假设前一个已经用完,即i>mid,算法将不会执行16行的while循环。而去执行17行的while循环,此时后一个子数组中肯定还有至少一个元素,每执行一次while循环,将B[j..right]中的最小元素复制回数组A。同样保持上述循环不变式。此时i>mid,可以将A[i]看成无穷大,它同样是前一个子数组未复制回数组A的最小元素(实际情况是已经没有元素,加上它是为了便于循环不变式的分析)

 

终止:终止时k=right。根据循环不变式,子数组A[left...k-1]就是A[left...right]且按从小到大顺序包含B[left..mid]和B[mid+1,right]中的k-left = right-left+1个最小元素。

 

通过以上三个步骤,证明了循环不变式在该算法中是成立的,也就证明了归并排序算法的有效性。

 

四.从归并排序算法理解分治思想

  归并排序算法是分治算法的典型应用。可以把归并排序当成分治算法的算法框架,在此基础上来解决更多的分治问题,例如对数组中逆序对的统计等

 

归并排序