概述
上一篇我们说了一个非常简单的排序算法——选择排序。其复杂程序完全是冒泡级的，甚至比冒泡还要简单。今天要说的是一个相对比较复杂的排序算法——归并排序。复杂的原因不仅在于归并排序分成了两个部分进行解决问题，而是在于，你需要一些算法的思想支撑。
归并排序和之前我写的一篇博客《》有很多相似的地方，如果你感兴趣，也可以去看看那一篇博客。版权说明
著作权归作者所有。 商业转载请联系作者获得授权，非商业转载请注明出处。 本文作者： 发表日期： 2016年5月27日 本文链接： 来源：CSDN 更多内容：
目录
弱分治归并
归并的核心算法就是上面提到过的两个过程。分别是分治与合并。合并都好理解，那么什么是分治呢？下面就来逐一说明一下。
算法原理
弱分治归并排序算法中，我们主要说的是合并，因为这里的分治更像是分组。
背景
假设我们有序列 T0 = [ 4, 3, 6, 5, 9, 0, 8, 1, 7, 2 ]
那么，在一开始，我们的序列就被分成了 10 组，每一组的元素个数为 1。合并
先说合并吧，因为它简单一些。在合并模块中，需要传入两个序列参数，并保证待合并的两个序列本身已经有序。现在我们假设待合并的两个有序序列分别为：
t0 = [ 0, 9 ] t1 = [ 1, 8 ] 看到这两个序列让人很自然地想到，只要依次取 t0 和 t1 中的最小的元素即可。并且最小的元素就是第一个元素。当我们取完 t0 中的 0 之后，t0 中就不再有 0 了，这一点很重要。表现在代码上就是下标的移动了。第二次取到的是 t1 中的 1。重复这个过程，就可以获得合并后的有序序列 tm = [ 0, 1, 8, 9, ]。 合并过程图解
下面是合并的核心代码
// 合并的核心模块 private void merge(int[] array, int low, int mid, int hight) { if (low >= hight) { return; } int[] auxArray = new int[hight - low + 1]; int index1 = low; int index2 = mid + 1; int i = 0; while(index1 <= mid && index2 <= hight) { if (array[index1] <= array[index2]) { auxArray[i] = array[index1]; index1++; i++; } else { auxArray[i] = array[index2]; index2++; i++; } } // 继续合并前半段数组中未被合并的部分 while (index1 <= mid) { auxArray[i] = array[index1]; index1++; i++; } // 继续合并后半段数组中未被合并的部分 while (index2 <= hight) { auxArray[i] = array[index2]; index2++; i++; } // 将合并好的序列写回到数组中 for (int j = 0; j < auxArray.length; j++) { array[low + j] = auxArray[j]; } } 分治
我想大部分人应该不会被合并逻辑给难住吧。只是分治的逻辑会有一些麻烦，麻烦不是在于分治思想的麻烦，而是分治过程的逻辑代码不好编写。正因为如此，所以我们在前面先讲解弱分治归并，这样在下面看到强分治归并的分治逻辑时，你才不会毫无头绪。在上面也说了，弱分治并归更像是一个分组合并的过程。也就是一开始就有很多组，然后慢慢合并，在合并的过程中分组减少了，合并后的有序数组变大了，直至只有一个数组为止。
在合并中最容易想到的是两两合并。所以在分组后，就两两进行合并。只要我们能准确地取到相邻的两个序列就可以进行合并了。 下面是代码实现// 对数组进行分组的核心模块 private void sortCore(int[] array) { int length = array.length; int groupSize = 1; while(groupSize < length) { for (int i = 0; i < length; i += (groupSize * 2)) { int low = i; int hight = Math.min(i + groupSize * 2 - 1, length - 1); int middle = low + groupSize - 1; merge(array, low, middle >= hight ? (low + hight) / 2 : middle, hight); } groupSize *= 2; } // 对分组中的奇数情况进行另外处理 if (groupSize / 2 < length) { int low = 0; int hight = length - 1; merge(array, low, groupSize / 2 - 1, hight); } } 在上面的代码中，可以看到最后有一个奇数分组的逻辑处理。这是怎么回事呢？很好理解，假设，现在给你 (2n + 1) 个分组的有序序列，按照前面讲的两两合并，那么只能合并前面的 2n 个序列，第 (2n + 1) 个序列找到可合并的对象。处理的方式就是把它保留到最后与迭代后的有序序列进行合并即可。这一点从下面的图解中也可以获知。
排序过程图解
算法实现
/** ** 归并排序算法 *
* 2016年1月20日 * * @author Q-WHai * @see http://blog.csdn.net/lemon_tree12138 * @version 0.1.1 */public class MergeSort implements Sortable { @Override public int[] sort(int[] array) { if (array == null) { return null; } sortCore(array); return array; } // 对数组进行分组的核心模块 private void sortCore(int[] array) { ( ... 此处省略上面分治的逻辑 ... ) } // 合并的核心模块 private void merge(int[] array, int low, int mid, int hight) { ( ... 此处省略上面合并的逻辑 ... ) }}
强分治归并
算法原理
强分治归并相比弱分治归并的不同点在于，强分治归并有没在一开始就对数组 T0 进行分组，而是通过程序来对 T0 进行分组，现在可以看一张强分治归并排序算法的过程图感受一下。
合并
不管弱分治归并还是强分治归并，其合并的逻辑都是一样的。大家可以自行参考上面的逻辑，这里就不废话了。
分治
从上面的排序过程图中也可以发现，强分治归并需要将原数组先划分成小数组。首先将一个大数组分割成两个小数组，再将两个小数组分割成四个小数组，如此往复。字里行间都表明了，这里需要进行递归操作。
强分治归并算法的分治部分逻辑代码：/** * 对数组进行分组的核心模块 * * @param array * 待排序数组 * @param start * 开始位置 * @param end * 结束位置(end 为 数组可达下标) */ private void sortCore(int[] array, int start, int end) { if (start == end) { return; } else { int middle = (start + end) / 2; sortCore(array, start, middle); sortCore(array, middle + 1, end); merge(array, start, middle, end); } } 总结
算法复杂度
| 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均情况 | 最坏情况 | 最好情况 | ||||
| 归并排序 | O(n∗log n) | O(n∗log n) | O(n∗log n) | O(n+log n) | 稳定 | 较复杂 |
强弱分治归并的比较
需要比较的主是代码逻辑复杂度和运行效率
这里我们用了一个数组为： int[] array = { 4, 3, 6, 5, 9, 0, 8, 1, 7, 2 }; 循环运行 1000000 次后得到如下结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]MergeSort 用时：509 ms-------------------------------------[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]MergeImproveSort 用时：374 ms
| 算法名称 | 代码逻辑复杂度 | 运行效率 | bigger 值 |
|---|---|---|---|
| 弱分治归并 | 简单 | 低 | 低 |
| 强分治归并 | 复杂 | 高 | 高 |
所以，如果想要运行效率高一些或是刷刷 bigger 值，那么请使用强分治归并排序算法。
Ref
- 《大话数据结构》