数据结构与算法--归并排序
归并排序
归并排序基于一种称为“归并”的简单操作。比如考试可能会分年级排名和班级排名，那么这个年级排名可能是合并了各个班级的排名后对其再排名得到——每个班级会上报本班学生成绩排名情况，上面的人根据各班提交的排名情况汇总成一个总排名。这就是归并在生活中的例子。那么归并排序，说得抽象些，其实就是将两个已经有序的数组归并成一个更大的有序数组，这里注意要求在归并之前两个子数组已经有序。于是，对整个大数组排序，可以先（递归地）将其分成两半分别排序，然后将结果归并起来。
实现归并排序的一种简单方法是：将两个不同的有序数组归并到第三个数组中去，因此该方法实现的归并排序需要额外空间，且所需空间的大小和待排序数组的长度N成正比。下面来看，通过怎样的比较才能将两个数组的元素有序地归并到一个数组中。
private static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int high) {
int i = low; // 左半数组的指针 [0, mid]
int j = mid + 1; // 右半数组的指针 [mid +1, high]
// 将待归并的数组元素全归并到一个新数组中
for (int k = low; k <= high; k++) {
aux[k] = a[k];
}
for (int k = low; k <= high; k++) {
// 左半数组指针超出，被取完。于是取右半数组中的元素
if (i > mid) {
a[k] = aux[j++];
// 右半数组被取完，取左半数组中的元素
} else if (j > high) {
a[k] = aux[i++];
// 已满足i <= mid && j <= high
// 右半数组的元素小，就取右半数组中元素
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
// 已满足i <= mid && j <= high
// 左半数组元素小或者相等，取左半数组中的元素，相等时取左边保证了排序稳定性
} else {
a[k] = aux[i++];
}
}
}
该方法将数组区间[low, high]之间的所有元素都复制到了一个新的数组aux中，然后在归并回原数组a中。为此进行了4个判断：
- 左半数组被取尽 --> 取右半数组中的元素；
- 右半数组被取尽 --> 取左半数组中的元素；
- 左半数组的当前元素小于右半数组的当前元素 --> 取左半数组的元素；
- 左半数组的当前元素不小于右半数组中的元素 --> 取右半数组中的元素，因此当左右数组中当前元素等值时会去右半数组中的元素。
注意条件1、2和条件3、4的顺序不可颠倒，因为如果条件1、2不通过，执行条件3、4时候就保证了i <= mid && j <= mid，使得左右半数组的访问都不会出现下标越界。如果条件3、4放在前面判断，随着j的自增，可能就下标越界了。
如下图演示了归并的过程，依据上面的条件，不断从右边的aux[]中取处元素顺序放回原数组a中，达到将两个数组归并（由原数组分割成的左右数组），从而实现了排序。
自顶向下的归并排序
为了将小数组归并成大数组，需要保证小数组是有序的。于是我们可以利用的递归的方法，将数组分成左右两半分别排序，左右数组有序后就能将结果归并到一起了。根据描述，可写出如下代码。
package Chap9;
public class MergeSort {
/* private static void merge...
merge方法见上面
*/
private static void sort(Comparable[] a, Comparable[] aux, int low, int high) {
// high = low说明数组被划分到只有一个元素，无需排序和归并直接返回
if (high <= low) {
return;
}
int mid = low + (high - low) / 2;
sort(a, aux, low, mid);
sort(a, aux, mid + 1, high);
merge(a, aux, low, mid, high);
}
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static boolean isSorted(Comparable[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (less(a[i + 1], a[i])) {
return false;
}
}
return true;
}
public static String toString(Comparable[] a) {
if (a.length == 0) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < a.length; i++) {
sb.append(a[i]);
if (i == a.length - 1) {
return sb.append("]").toString();
} else {
sb.append(", ");
}
}
return sb.toString();
}
public static void main(String[] args) {
Integer[] a = {9, 1, 5, 8, 3, 7, 4, 6, 2};
MergeSort.sort(a);
System.out.println(MergeSort.toString(a));
System.out.println(MergeSort.isSorted(a));
}
}
辅助数组aux是sort方法的局部变量，这表明每对一个序列调用sort方法都会生成一个aux数组。不能将aux设置成 类静态成员static Comparable[] aux，因为如果有多个程序用这个类进行排序，它们就共享了该辅助数组aux，在多线程中很容易出问题。将aux定义在merge方法里也不合适，这意味着每次归并都会生成一个数组，无疑是浪费。
下图显示了归并过程
第一次归并是a[0]和a[1]，第二次归并是a[2]和a[3]，第三次归并是a[0..3]，然后是a[4]和a[5]...以此类推。你可能诧异为什么是这样的归并顺序，看下图递归方法调用的顺序就清楚了。
我们还可以将这种“先对左半数组进行排序，再将右半数组进行排序”的归并方法用树来表示，如下
该树的高度为lg N，设lg N = n，对于[0, n]中任意k，自顶向下的第k层有2^k个子数组，每个数组的长度为2^(n-k)，归并最多需要2^(n-k)次比较，所以第k层需要2^k * 2^(n-k) = 2^n次比较，总共n层需要n * 2^n即Nlg N次比较。故时间复杂度为O(Nlg N)
归并排序可以处理大规模的数组，但是主要缺点是引入的辅助数组所需的额外空间与数组大小N成正比。
改进
对小规模数组换用插入排序
用不同的算法处理小规模问题能改进大多数递归算法的性能，因为递归会使得小规模问题的方法调用过于频繁。对排序来说，我们知道插入排序非常简单而且适合小规模数组，因此在归并排序中如果需要处理的数组比较小，比如数组长度小只有十几，就可以用插入排序代替归并过程。
测试数组是否有序
我们知道在归并之前，左半数组和右半数组已经分别有序，如果左半数组的最后一个元素（下标为mid）比右半数组的小于等于第一个数组（下标为mid + 1），说明该数组本身就有序，无需再调用merge方法。
基于以上两点，对自顶而下的归并排序优化如下
private static void sort(Comparable[] a, Comparable[] aux, int low, int high) {
// high <= low + 15说明当数组很小时直接换用插入排序，当数组长度不超过16时都使用插入排序
if (high <= low + 15) {
InsertSort.sort(a);
return;
}
int mid = low + (high - low) / 2;
sort(a, aux, low, mid);
sort(a, aux, mid + 1, high);
// a[mid] <= a[mid + 1]已经有序，跳过归并操作
if (a[mid].compareTo(a[mid + 1]) > 0) {
merge(a, aux, low, mid, high);
}
}
在原来的基础上只是加了简单几行，就可以稍微提升一点性能！归并排序的可视化过程见下图
自底向上的归并排序
递归实现的归并是算法设计中分治思想体现，我们将一个大问题分割成小问题分别解决，然后用所有的小问题的答案解决整个大问题。实现归并排序的另一种思路是直接从小数组开始归并（因此无需使用递归的方法将大数组分成左右子数组），然后再成对归并得到的子数组，如此这般，直到将整个数组归并到一起。
首先我们进行两两归并，然后四四归并、八八归并，一直下去。最后一次归并的第二个子数组可能比第一个子数组要 小，即便如此merge方法也能很好地处理，因此不用在意。
public class MergeBU {
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
// sz = 1, 2, 4, 8...
for (int sz = 1; sz < a.length; sz = sz + sz) {
// sz = 1: low= 0, 2, 4, 6, 8, 10...
// sz = 2: low= 0, 4, 8, 12, 16...
// sz = 4: low= 0, 8, 16, 24...
for (int low = 0; low < a.length-sz; low += (sz + sz)) {
// sz = 1: 归并子数组 (0,0,1) (2,2,3) (4,4,5)...
// sz = 2: 归并子数组 (0,1,3) (4,5,7) (8,9,11)...
// sz = 4: 归并子数组 (0,3,7) (8,11,15) (16,19,23)...
// 可由归纳法得到mid = low + sz -1; high = low + 2sz -1
// 最后一个子数组可能比sz小，所以通过low + 2sz -1计算high可能比原数组还要大，因此和a.length - 1取最小
merge(a, aux, low, low + sz - 1, Math.min(low + sz + sz - 1, a.length - 1));
}
}
}
}
merge方法直接使用自顶向下的归并排序中的改进的merge方法。注释中写出了sz和low的递增过程，外循环中sz=1表示两两归并，sz=2表示四四归并，以此类推，每次都成倍增长...内循环中low每次增长sz + sz，实际上是直接跳到了下一个子数组，边界条件low < a.length - sz比较难懂，如果是low < a.length就比较好理解，表示的是最后一个子数组的开始下标，后者当然能得出正确结果，但是相比前者在处理最后一个子数组时可能有多余的归并操作。
low < a.length - sz终止条件，说明顶多最后一个sz长度的子数组没有进行归并操作就跳出循环了，这种情况发生在倒数第二个子数组的low刚好等于a.length - 3sz时，该子数组的范围是[a.length - 3sz, a.length - sz -1]，下一次low自增low += (sz + sz)得到low = a.length - sz刚好不满足条件，于是后面长度为sz的子数组没有归并。如下图所示。
其他情况下，没有被归并的子数组长度都比上述情况要小。如下两幅图所示，
再来看，最后一个长度为小于等于sz的数组没有被归并影响结果吗？由外层for循环的sz = sz + sz可知，sz正好是上一轮中被归并的子数组长度（现在的sz是上一轮中sz的两倍，而被归并的子数组长度2sz），因此本轮中最后这长度为sz的子数组，在上一轮中就已经归并过了，条件low < a.length - sz正好规避了多余的归并操作。
至于merge方法中，mid = low + sz -1，以及high = low + sz + sz -1都可以通过数学归纳法得到，有时候最后一个子数组可能比sz小，所以通过low + sz + sz -1计算high可能超出原数组长度，因此和a.length - 1取最小以防止下标越界。
下面是自底向上的归并排序轨迹图以及可视化过程。
和自顶而下的归并排序相比，可以发现他们的归并顺序并不一样。
归并排序在最坏情况下需要比较~Nlg N次，这已经是所有基于比较的排序算法中最好的效率了，但是归并排序需要额外空间，这不是最优的。
归并排序中先对子数组两两归并，由于merge方法代码中else分支包含了左半数组元素和右半数组元素相等的情况，此时取的是左半数组的元素，这保证了等值元素的相对位置不会发生改变，随着归并数组的增大，这种关系依然成立。所以归并排序是稳定的排序算法。
by @sunhaiyu
2017.10.29
