本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。
之所以把它独立成一篇,一方面是一旦了解了它再理解归并排序就会简单很多,另一方面是其本身就具有独立性,可以解决很多常见问题,并不非得寄宿在归并排序里面。
合并算法,就是将两个已经各自排好序的序列,合并成一个排好序的大序列的方法。
两摞扑克牌
《算法导论》里面给出的例子就很好理解。还是拿扑克牌来说事:桌上有两摞牌,面朝上,每摞都已经按照从小到大排好序了。那么如何把它们合并成一摞并排好序呢?
日常生活中其实还有很多类似的应用。比如校园里学生按身高由低到高排队,偶尔会遇到两队合一队的情况,要求合并后仍然按照由低到高的顺序。
合并算法就是解决此类问题的最佳方法。以扑克牌为例,其基本步骤是:
假设最坏情况是两摞牌要比到各自最后一张,此时算法时间复杂度是T(n) = Θ(n),这是因为整个算法最多只要遍历一遍。
接下来,用伪码实现上面的思想,但有两个额外的变化:
定义算法的名字为MERGE,伪码如下:
MERGE(A, p, q, r)
1 n1 = q - p + 1
2 n2 = r - q
3 let L[1 ‥ n1+1] and R[1 ‥ n2+1] be new arrays
4 for i = 1 to n1
5 L[i] = A[p+i-1]
6 for j = 1 to n2
7 R[j] = A[q+j]
8 L[n1+1] = ∞
9 R[n2+1] = ∞
10 i = 1
11 j = 1
12 for k = p to r
13 if L[i] ≤ R[j]
14 A[k] = L[i]
15 i = i + 1
16 else A[k] = R[j]
17 j = j + 1
证明算法的正确性中提到:只要证明在初始、保持、和终止阶段循环不变式都成立,从而可以通过终止时的不变式推断出算法是正确的。
代码中的12~17行是唯一的循环,循环不变式是什么呢?这里我们令输出A[p ‥ k-1]作为循环不变式,迭代的任何过程中随k的增加该数组总是按从小到大的顺序包含原A[p ‥ r]中最小的元素,有如下证明:
前面提到过MERGE的时间复杂度是Θ(n),其中n = r - p + 1。再快速算下:
public class MergeSort {
public static void mergeInASC(int[] numbers, int p, int q, int r) throws Exception {
if(numbers.length < 2 || p > q || q >= r)
throw new Exception("Para error.");
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1 + 1];
int[] R = new int[n2 + 1];
for(int i = 0; i < n1; i++){
L[i] = numbers[p + i];
}
for(int j = 0; j < n2; j++){
R[j] = numbers[q + 1 + j];
}
L[n1] = Integer.MAX_VALUE;
R[n2] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for(int k = p; k <= r; k++){
if(L[i] > R[j]){
numbers[k] = R[j];
j++;
}
else{
numbers[k] = L[i];
i++;
}
}
}
}
MergeSort.java下载