讨厌算法的程序员 5 - 合并算法
2017-05-26 本文已影响70人
袁承兴
本篇介绍的“合并”算法，是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法，请注意两者之间的关系和差异。
之所以把它独立成一篇，一方面是一旦了解了它再理解归并排序就会简单很多，另一方面是其本身就具有独立性，可以解决很多常见问题，并不非得寄宿在归并排序里面。
合并算法，就是将两个已经各自排好序的序列，合并成一个排好序的大序列的方法。
经典应用
两摞扑克牌
《算法导论》里面给出的例子就很好理解。还是拿扑克牌来说事：桌上有两摞牌，面朝上，每摞都已经按照从小到大排好序了。那么如何把它们合并成一摞并排好序呢？
日常生活中其实还有很多类似的应用。比如校园里学生按身高由低到高排队，偶尔会遇到两队合一队的情况，要求合并后仍然按照由低到高的顺序。
合并算法就是解决此类问题的最佳方法。以扑克牌为例，其基本步骤是：
- 1 比较两堆牌最顶上的两张牌，选最小的一张；
- 2 将其拿出来（此时该堆顶上将露出一张新牌），面朝下放到输出堆（就是最终的那一大摞）；
- 3 重复上面两步，直到原来两堆其中一个为空，此时将另一堆中的所有剩余的牌，直接面朝下放到输出堆中。
假设最坏情况是两摞牌要比到各自最后一张，此时算法时间复杂度是T(n) = Θ(n)，这是因为整个算法最多只要遍历一遍。
伪码
接下来，用伪码实现上面的思想，但有两个额外的变化：
- 扑克应用中的两摞牌已经排好序换一种表达方式：A是一个数组，p、q和r是数组下标，满足p≤q＜r，假设A[p ‥ q]和A[q+1 ‥ r]都已排好序。期望的输出是：A的子数组A[p ‥ r]是通过合并原A[p ‥ q]和A[q+1 ‥ r]形成的且已排好序的子数组。
- 为了避免每次执行基本步骤都要检查是否有堆为空，在每个堆的底部放置一张“哨兵”牌（哨兵通常包含一个特殊值，用于简化代码），值为∞。它可以保证直到两堆牌都露出∞时，其他牌都已经放置到输出堆。因为我们事先知道刚好r - p + 1张牌将被放置到输出堆，所以一旦已执行r - p + 1个基本步骤，算法就可以停止了。
定义算法的名字为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]中最小的元素，有如下证明：
- 初始化：循环第一次迭代之前，k = p，所以子数组A[p ‥ k-1]为空；
- 保持：即要证明某次迭代之前不变式为真，下次迭代之前不变式仍为真；
- 假设某次迭代前，L[i] ≤ R[j]，此时L[i]是未被复制回数组A的最小元素；
- 与此同时，数组A[p ‥ k-1]包含k - p个最小元素，即迭代前不变式为真；
- 第14行代码将L[i]复制到A[k]之后，子数组A[p ‥ k]将包含k - p + 1个最小元素。增加k的值（for循环）和i的值（第15行代码）后，即为下次迭代前重新建立了该循环不变式；
- 反之，若L[i] > R[j]，则第16~17代码执行适当的操作来维持该循环不变式。
- 终止：终止时k = r + 1。子数组A[p ‥ k-1]就是A[p ‥ r]且按从小到大的顺序包含了L[1 ‥ n1+1]和R[1 ‥ n2+1]中的k - p = r - p + 1个最小元素。数组L和R一共包含n1 + n2 + 2 = r - p + 3个元素，多出的2个就是哨兵，其他所有元素都已经被复制回数组A。
时间复杂度
前面提到过MERGE的时间复杂度是Θ(n)，其中n = r - p + 1。再快速算下：
- 代码13行和811行中的每行需要常量时间；
- 代码4~7行的for循环需要Θ(n1+n2) = Θ(n)的时间；
- 代码12~17行for循环有n次迭代，每次迭代需要常量时间。
Java实现
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++;
}
}
}
}
共享协议：署名-非商业性使用-禁止演绎（CC BY-NC-ND 3.0 CN）
转载请注明：作者黑猿大叔（简书）
