一、前言
前面写过一篇快速排序，今天写一篇归并排序，其实这些高级排序都有分治算法的影子， 都是把一个大的问题拆解成不同的子问题，然后解决子问题了，大问题也就解决了， 这些高级排序算法都存在一个特别就是时间复杂度都是O(nlogn)，ok，下面让我们看看归并算法，let’s go !
二、归并排序
1.什么是归并排序呢？
wiki定义：归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法， 效率为 {\displaystyle O(n\log n)} {\displaystyle O(n\log n)}（大O符号）。1945年由约翰·冯·诺伊曼首次提出。 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行
2.归并排序算法描述
归并排序的核心思路是，把一个待排序的数组，不断地拆分成小数组，直到无法拆分， 然后再把小数组两两进行排序合并。
3.第一版归并排序算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class MergeSort {
public void sort(int[] nums) {
// 调用内部辅助函数
sort(nums, 0, nums.length - 1);
}
private void sort(int[] nums, int left, int right) {
// 当left >= right就代表已经全部划分完了，所以这是终止条件
if (left >= right) {
return;
}
// 计算 mid 的位置
int mid = (left + right) / 2;
// 左边划分
sort(nums, left, mid);
// 右边划分
sort(nums, mid + 1, right);
// 合并操作
merge(nums, left, mid, right);
}
private void merge(int[] nums, int left, int mid, int right) {
// copy 一份 空间出来用于辅助合并过程
int[] temp = Arrays.copyOfRange(nums, left, right + 1);
// i 代表的是左半部分的考察索引
int i = left;
// j 代表的是右半部分的考察索引
int j = mid + 1;
for (int k = left; k <= right; k ++) {
// 第一种情况
// 当左半部分考察的索引已经大于中间位置了，
// 那就代表，左边全部排好序了，要去考察右边部分的
if (i > mid) {
nums[k] = temp[j - left];
j ++;
} else if (j > right) { // 当 j > right,就代表右半部分全部考察完了，要考察左边部分了
nums[k] = temp[i - left];
i ++;
} else if (temp[i - left] < temp[j - left]) { // 当左边部分 < 右边部分，
// 那么就把左边考察的这个元素放回数组，然后维护左边部分的索引
nums[k] = temp[i - left];
i ++;
} else { // 否则就是右边部分 < 左边的，那么就把右边考察的这个元素放回数组，然后维护右边部分的索引
nums[k] = temp[j - left];
j ++;
}
}
}
}
这是实现的第一版归并算法，其实上面的这个实现已经满足大部分情况了，但是还是存在问题
- 如果我们待排序的数组是近乎有序的情况下，那么上面实现的算法，我们就会多了很多没必要的合并过程
- 其实大部分的高级算法，在元素达到一定的数量的时候，都可以选择插入排序，但是这里就不进行这个优化。
4.第二版归并排序(优化)
其实只要在第一版的基础上加一个判断就可以实现优化了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class MergeSort {
public void sort(int[] nums) {
// 调用内部辅助函数
sort(nums, 0, nums.length - 1);
}
private void sort(int[] nums, int left, int right) {
// 当left >= right就代表已经全部划分完了，所以这是终止条件
if (left >= right) {
return;
}
// 计算 mid 的位置
int mid = (left + right) / 2;
// 左边划分
sort(nums, left, mid);
// 右边划分
sort(nums, mid + 1, right);
// 合并操作
// 判断如果 mid 位置 小于 mid + 1这个位置，
// 也就是左边部分小于右边部分，那么是不需要做这个合并操作
if (nums[mid] > nums[mid + 1])
merge(nums, left, mid, right);
}
private void merge(int[] nums, int left, int mid, int right) {
// copy 一份 空间出来用于辅助合并过程
int[] temp = Arrays.copyOfRange(nums, left, right + 1);
// i 代表的是左半部分的考察索引
int i = left;
// j 代表的是右半部分的考察索引
int j = mid + 1;
for (int k = left; k <= right; k ++) {
// 第一种情况
// 当左半部分考察的索引已经大于中间位置了，
// 那就代表，左边全部排好序了，要去考察右边部分的
if (i > mid) {
nums[k] = temp[j - left];
j ++;
} else if (j > right) { // 当 j > right,就代表右半部分全部考察完了，要考察左边部分了
nums[k] = temp[i - left];
i ++;
} else if (temp[i - left] < temp[j - left]) { // 当左边部分 < 右边部分，
// 那么就把左边考察的这个元素放回数组，然后维护左边部分的索引
nums[k] = temp[i - left];
i ++;
} else { // 否则就是右边部分 < 左边的，那么就把右边考察的这个元素放回数组，然后维护右边部分的索引
nums[k] = temp[j - left];
j ++;
}
}
}
}
上面就是归并排序比较完整的实现了，当然还可以就是进行一个小小的优化，就是前面说的转成插入排序
三、尾语
其实归并排序就是一个分治算法的思想，只要认真的去思考，去debug，一切都很简单！数据结构和算法永远是程序的灵魂、核心。 所以，应该要掌握这些核心，才能让自己不被淘汰！加油！
