版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/df8a9e136295
概念
归并排序就是利用归并的思想实现的排序算法。归并排序的原理：假设初始序列含有n个记录，该序列可以看成n个有序的子序列，其中每个子序列的长度为1，然后两两归并，得到⌈n/2⌉（⌈x⌉表示不小于x的最小整数）个长度为2或者1的子序列，然后再两两归并，……，如此重复直到得到1个长度为n的有序序列为止。
递归式归并
演示
比如我们待排序的数组是 {9, 1, 5, 8, 3, 7, 4, 6, 2}，那么递归式的归并排序为流程为：
[9, 1, 5, 8, 3, 7, 4, 6, 2]
↓ ↓
[9, 1, 5, 8, 3] [7, 4, 6, 2]
↓ ↓ ↓ ↓
[9, 1, 5] [8, 3] [7, 4] [6, 2]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[9, 1] [5] [8] [3] [7] [4] [6] [2]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[9] [1] [5] [8] [3] [7] [4] [6] [2] // 上面为拆分，下面为归并(合并)
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[1, 9] [5] [8] [3] [7] [4] [6] [2]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[1, 5, 9] [3, 8] [4, 7] [2, 6]
↓ ↓ ↓ ↓
[1, 3, 5, 9, 8] [2, 4, 6, 7]
↓ ↓
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Java实现
// 定义接口
interface Sorter {
/**
* 将数组按升序排序
*/
int[] sort(int[] arr);
/**
* 交换数组arr中的第i个位置和第j个位置的关键字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 递归式归并排序
class MergeSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
int[] result = new int[arr.length];
mergeSort(arr, result, 0, arr.length - 1);
return result;
}
/**
* 将乱序的src[start...end]归并排序为有序的des[start...end]
*
* @param src
* 归并前乱序数组
* @param des
* 归并后的有序数组
* @param start
* 归并的起始位置
* @param end
* 归并的终止位置
*/
private void mergeSort(int[] src, int[] des, int start, int end) {
if (start == end) {
des[start] = src[start];
return;
}
int[] tmp = new int[src.length];
// 将src[start...end]分为src[start...mid]和src[mid+1...end]两部分
int mid = (start + end) / 2;
mergeSort(src, tmp, start, mid); // 递归，将src[start...mid]归并为有序的tmp[start...mid]
mergeSort(src, tmp, mid + 1, end); // 递归，将src[mid+1...end]归并为有序的tmp[mid+1...end]
// 将有序的tmp[start...mid]和tmp[mid+1...end]合并为des[start...end]
merge(tmp, des, start, mid, end);
}
/**
* 将有序的src[start, mid]和有序的src[mid+1, end]合并为有序的des[start,end];
* src可能为乱序数组,但是src[start, mid]和src[mid+1, end]是有序的。
*
* @param src
* 乱序的原数组
* @param des
* 有序的目标数组
* @param start
* 数组第一部分起始位置
* @param mid
* 数组第一部分结束位置（两部分的分界点）
* @param end
* 数组第二部分结束位置
*/
protected void merge(int[] src, int[] des, int start, int mid, int end) {
int i; // src数组第一部分下标
int j; // src数组第二部分下标
int k; // des数组下标
// 将较小的数依次移动到目标数组中
for (i = start, k = start, j = mid + 1; i <= mid && j <= end;) {
if (src[i] < src[j]) {
des[k] = src[i++];
} else {
des[k] = src[j++];
}
k++;
}
// 将剩余的src[i...mid]复制到des数组中
for (; i <= mid; i++) {
des[k] = src[i];
k++;
}
// 将剩余的src[j...end]复制到des数组中
for (; j <= end; j++) {
des[k] = src[j];
k++;
}
}
}
复杂度
时间复杂度：
因为归并的递归操作其实就是二叉树的结构，故而，最好情况 = 最坏情况 = 平均情况 = O(nlogn)
空间复杂度：
因为递归式归并需要(1)与原始记录相同大小的空间来存放归并的结果以及(2)深度为logn的栈空间，所以空间复杂度为O(n+logn)
非递归式归并
演示
又比如我们待排序的数组是 {9, 1, 5, 8, 3, 7, 4, 6, 2}，那么非递归式的归并排序为流程为：
[9] [1] [5] [8] [3] [7] [4] [6] [2]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[1, 9] [5, 8] [3, 7] [4, 6] [2]
↓ ↓ ↓ ↓ ↓
[1, 5, 8, 9] [3, 4, 6, 7] [2]
↓ ↓ ↓
[1, 3, 4, 5, 6, 7, 8, 9] [2]
↓ ↓
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Java实现
// 非递归式归并排序
class NonRecursiveMergeSorter extends MergeSorter {
@Override
public int[] sort(int[] arr) {
mergeSort(arr);
return arr;
}
private void mergeSort(int[] arr) {
int len = arr.length;
int result[] = new int[len];
int k = 1;
while (k < len) {
mergePass(arr, result, k); // arr归并至result,此时间隔为k
k = 2 * k; // 子序列长度加倍
mergePass(result, arr, k); // result归并至arr,此时间隔翻倍
k = 2 * k; // 子序列长度加倍
}
}
/**
* 将数组src中相邻长度为interval的子序列两两归并到des数组中
*
* @param src
* 源数组
* @param des
* 目标数组
* @param interval
* 两两合并的子序列长度
*/
private void mergePass(int[] src, int[] des, int interval) {
int i = 0;
int len = src.length;
while (i + 2 * interval - 1 < len) {
// 两两合并
merge(src, des, i, i + interval - 1, i + 2 * interval - 1);
i = i + 2 * interval;
}
if (i + interval - 1 < len - 1) {
// i+interval-1小于len-1，说明最后还剩余两个子序列，只不过最后的一个子序列长度不够interval
// 那么将剩下的两个子序列进行合并
merge(src, des, i, i + interval - 1, len - 1);
} else {
// 否则，最后只剩下单个子序列，则直接将该子序列加入到des尾部
for (; i < len; i++) {
des[i] = src[i];
}
}
}
}
复杂度
时间复杂度：
同递归式归并，最好情况 = 最坏情况 = 平均情况 = O(nlogn)
空间复杂度：
非递归式归并不需要保存方法栈信息，所以空间复杂度为O(n)
所以非递归的递归算法性能要高于递归式归并算法。
