讨厌算法的程序员 6 - 归并排序

分而治之

分而治之

从算法设计的分类上来说，插入排序属于增量方法。在排序好子数组A[1 ‥ j-1]后，再将单个元素A[j]插入子数组的适当位置，产生排序好的子数组A[1 ‥ j]。整个算法就是不断以此方法增量插入，直到子数组包含了所有数组元素。

本篇将要介绍的归并排序，是用另一种思想来解决排序问题的，在算法设计分类上属于分治法。

分治法思想是，将原问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后在合并这些子问题的解，最终建立原问题的解。

这里提到一个词递归，其解释是：为了解决一个给定问题，算法一次或多次的调用其自身以解决紧密相关的子问题。递归是分治思想的一个具体实现。

分治模式在每层递归时都有三个步骤：

• 分解：将原问题分解为若干子问题，这些子问题是原问题的规模较小的实例；
• 解决：递归的求解各子问题；
• 合并：合并子问题的解，得到原问题的解。

看到这里，“直觉”上可能会产生一个极大的疑问：最底层的子问题是在哪里解决的？产生这个疑问是正常的，因为第二步“解决”也仅仅是调用自身，其实就是重新进入了下一层的分解、解决和合并，而没有看到“如何解决”。

答案是：无需解决。换句话说，层层分解到子问题的规模足够小时，解就自己出现了。后面还会再提到这一点。

归并排序伪码

归并排序按照分治法的三个步骤如下：

• 分解：分解待排序的n个元素的序列，变成各具n/2个元素的两个子序列；
• 解决：递归的调用自身排序两个子序列；
• 合并：合并两个已排序的子序列以产生最终排序的序列。

上一篇合并算法中已经解决了合并算法MERGE，归并排序就剩下如何进行分解，和递归调用了。

看代码的确就这三步：

MERGE-SORT(A, p, r)
1 if p < r
2   q = (p + r) / 2
3   MERGE-SORT(A, p, q)
4   MERGE-SORT(A, q+1, r)
5   MERGE(A, p, q, r)

注：(p + r) / 2如果不是整除，则取小于它的最大整数。

p < r时，表明数组有继续拆分的可能。当p ≥ r时，则表示该子数组最多有一个元素，所以无需排序就已经是排好序了，这就是分解到足够小会导致的自动解决。换句话说，我们一直把数组分解下去，直到分成每个子数组只包含1个元素时，即第3行中p = q，第4行中q+1 = r，那么第3和第4行的MERGE-SORT会立即返回，并执行MERGE，然后返回上一层MERGE-SORT，直到最上层。

一个例子

一个有8个元素的数组A[5, 2, 4, 7, 1, 3, 2, 6]，采用归并排序的图示如下图。图中的下方蓝区部分是上面白区的数组不同时刻的镜像。白区主要在做“分解”，蓝区主要在做“合并”。

归并排序

归并排序Java代码

public static void mergeSortInASC(int [] numbers, int p, int r) throws Exception {
    if(p < r){
        int q = (int)Math.floor((p + r) / 2);
        mergeSortInASC(numbers, p, q);
        mergeSortInASC(numbers, q + 1, r);
        mergeInASC(numbers, p, q, r);
    }
}

MergeSort.java下载。