阅读经典——《算法导论》02
不同算法中往往蕴含着通用的思想，分治法就是最常用的一种。
分治法使用递归的方式，将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解从而得到原问题的解。
仍然考虑排序问题，本文将要介绍的归并排序就是使用分治法的典型案例。
思路：
把待排序数组从中间分割为两个子数组，这两个子数组分别排序，排完序后再把它们合并起来。该思路的关键在于子数组如何排序，以及如何把排完序的两个子数组合并起来。
第一个问题，分治法的精髓就在于把大问题分解为小问题，因此子数组仍然要使用归并排序，这是一个递归的过程。递归结束的条件是问题不能进一步分解，即数组只有一个元素。
第二个问题，排完序的两个子数组只需要同时遍历一遍就可以合并起来，这不是什么困难的事情。
整个算法从细分到合并的详细过程如下图所示。
归并排序分解步骤
归并排序的动画演示如下图：
归并排序
算法：
/**
* 归并排序，排序结果仍保存于arr数组中。
* @param arr 需要排序的数组
*/
public void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1);
}
/**
* 归并排序，排序arr数组中[p..r]的子数组，排序结果仍保存于arr数组中。
* @param arr 需要排序的数组
* @param p 待排序数组的起始下标
* @param r 待排序数组的终止下标
*/
public void mergeSort(int[] arr, int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSort(arr, p, q);
mergeSort(arr, q + 1, r);
merge(arr, p, q, r);
}
}
/**
* 归并已排序的两个子序列。
* @param arr 待归并的序列
* @param p 第一个子序列的起始下标
* @param q 第一个子序列的结束下标
* @param r 第二个子序列的结束下标
*/
public void merge(int[] arr, int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int[] arrL = new int[n1 + 1];
int[] arrR = new int[n2 + 1];
for (int i=0; i<n1; i++) {
arrL[i] = arr[p + i];
}
for (int i=0; i<n2; i++) {
arrR[i] = arr[q + 1 + i];
}
arrL[n1] = Integer.MAX_VALUE;
arrR[n2] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for (int k = p; k <= r; k++) {
if (arrL[i] <= arrR[j]) {
arr[k] = arrL[i];
i++;
}
else {
arr[k] = arrR[j];
j++;
}
}
}
mergeSort是用于递归调用的归并排序函数，merge是用于合并已排序序列的函数。它们的详细用法在代码注释里已经写得很清楚，此处不再赘述。
完整代码请参考MergeSort.java。
分析：
最后分析一下该算法的时间复杂度。归并排序采用了二等分的分治策略，因此每一级分治使问题规模减小一半，所以直到问题规模减小到1时应该经历了lgn级分治。每一级的归并操作需要Θ(n)的执行时间，因此总执行时间为Θ(nlgn)。
与上一篇文章提到的插入排序相比，归并排序的时间复杂度已经降低了很多，在输入规模n很大的情况下，两者的耗时差距非常大。
获取文集中的全套源码请访问GitHub代码仓库Algorithm。
