本篇介紹的“合并”算法，是為后面學(xué)習(xí)“歸并排序”的一個(gè)準(zhǔn)備。合并算法是歸并排序中的一個(gè)子算法，請注意兩者之間的關(guān)系和差異。
之所以把它獨(dú)立成一篇，一方面是一旦了解了它再理解歸并排序就會簡單很多，另一方面是其本身就具有獨(dú)立性，可以解決很多常見問題，并不非得寄宿在歸并排序里面。
合并算法，就是將兩個(gè)已經(jīng)各自排好序的序列，合并成一個(gè)排好序的大序列的方法。
經(jīng)典應(yīng)用
《算法導(dǎo)論》里面給出的例子就很好理解。還是拿撲克牌來說事：桌上有兩摞牌，面朝上，每摞都已經(jīng)按照從小到大排好序了。那么如何把它們合并成一摞并排好序呢？
日常生活中其實(shí)還有很多類似的應(yīng)用。比如校園里學(xué)生按身高由低到高排隊(duì)，偶爾會遇到兩隊(duì)合一隊(duì)的情況，要求合并后仍然按照由低到高的順序。
合并算法就是解決此類問題的最佳方法。以撲克牌為例，其基本步驟是：
- 1 比較兩堆牌最頂上的兩張牌，選最小的一張；
- 2 將其拿出來（此時(shí)該堆頂上將露出一張新牌），面朝下放到輸出堆（就是最終的那一大摞）；
- 3 重復(fù)上面兩步，直到原來兩堆其中一個(gè)為空，此時(shí)將另一堆中的所有剩余的牌，直接面朝下放到輸出堆中。
假設(shè)最壞情況是兩摞牌要比到各自最后一張，此時(shí)算法時(shí)間復(fù)雜度是T(n) = Θ(n)，這是因?yàn)檎麄€(gè)算法最多只要遍歷一遍。
偽碼
接下來，用偽碼實(shí)現(xiàn)上面的思想，但有兩個(gè)額外的變化：
- 撲克應(yīng)用中的兩摞牌已經(jīng)排好序換一種表達(dá)方式：A是一個(gè)數(shù)組，p、q和r是數(shù)組下標(biāo)，滿足p≤q＜r，假設(shè)A[p ‥ q]和A[q+1 ‥ r]都已排好序。期望的輸出是：A的子數(shù)組A[p ‥ r]是通過合并原A[p ‥ q]和A[q+1 ‥ r]形成的且已排好序的子數(shù)組。
- 為了避免每次執(zhí)行基本步驟都要檢查是否有堆為空，在每個(gè)堆的底部放置一張“哨兵”牌（哨兵通常包含一個(gè)特殊值，用于簡化代碼），值為∞。它可以保證直到兩堆牌都露出∞時(shí)，其他牌都已經(jīng)放置到輸出堆。因?yàn)槲覀兪孪戎绖偤胷 - p + 1張牌將被放置到輸出堆，所以一旦已執(zhí)行r - p + 1個(gè)基本步驟，算法就可以停止了。
定義算法的名字為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
正確性證明
證明算法的正確性中提到：只要證明在初始、保持、和終止階段循環(huán)不變式都成立，從而可以通過終止時(shí)的不變式推斷出算法是正確的。
代碼中的12~17行是唯一的循環(huán)，循環(huán)不變式是什么呢？這里我們令輸出A[p ‥ k-1]作為循環(huán)不變式，迭代的任何過程中隨k的增加該數(shù)組總是按從小到大的順序包含原A[p ‥ r]中最小的元素，有如下證明：
- 初始化：循環(huán)第一次迭代之前，k = p，所以子數(shù)組A[p ‥ k-1]為空；
- 保持：即要證明某次迭代之前不變式為真，下次迭代之前不變式仍為真；
- 假設(shè)某次迭代前，L[i] ≤ R[j]，此時(shí)L[i]是未被復(fù)制回?cái)?shù)組A的最小元素；
- 與此同時(shí)，數(shù)組A[p ‥ k-1]包含k - p個(gè)最小元素，即迭代前不變式為真；
- 第14行代碼將L[i]復(fù)制到A[k]之后，子數(shù)組A[p ‥ k]將包含k - p + 1個(gè)最小元素。增加k的值（for循環(huán)）和i的值（第15行代碼）后，即為下次迭代前重新建立了該循環(huán)不變式；
- 反之，若L[i] > R[j]，則第16~17代碼執(zhí)行適當(dāng)?shù)牟僮鱽砭S持該循環(huán)不變式。
- 終止：終止時(shí)k = r + 1。子數(shù)組A[p ‥ k-1]就是A[p ‥ r]且按從小到大的順序包含了L[1 ‥ n1+1]和R[1 ‥ n2+1]中的k - p = r - p + 1個(gè)最小元素。數(shù)組L和R一共包含n1 + n2 + 2 = r - p + 3個(gè)元素，多出的2個(gè)就是哨兵，其他所有元素都已經(jīng)被復(fù)制回?cái)?shù)組A。
時(shí)間復(fù)雜度
前面提到過MERGE的時(shí)間復(fù)雜度是Θ(n)，其中n = r - p + 1。再快速算下：
- 代碼13行和811行中的每行需要常量時(shí)間；
- 代碼4~7行的for循環(huán)需要Θ(n1+n2) = Θ(n)的時(shí)間；
- 代碼12~17行for循環(huán)有n次迭代，每次迭代需要常量時(shí)間。
Java實(shí)現(xiàn)
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++;
}
}
}
}
共享協(xié)議：署名-非商業(yè)性使用-禁止演繹（CC BY-NC-ND 3.0 CN）
轉(zhuǎn)載請注明：作者黑猿大叔（簡書）
