概览：
1）左部分排好序、右部分排好序、利用merge过程让左右整体有序
2）merge过程：谁小拷贝谁，直到左右两部分所有的数字耗尽，拷贝回原数组
3）递归实现和非递归实现
4）时间复杂度O(n∗logn)
5）需要辅助数组，所以额外空间复杂度O(n)
6）归并排序为什么比O(n2)的排序快？因为比较行为没有浪费！
7）利用归并排序的便利性可以解决很多问题 - 归并分治 - 下节课
注意：
有些资料说可以用原地归并排序，把额外空间复杂度变成O(1)，不要浪费时间去学
因为原地归并排序确实可以省空间，但是会让复杂度变成O(n2)
有关排序更多的概念、注意点、闭坑指南，将在后续课程继续
1 代码：归并排序递归版
(填函数风格)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void mergeSort1(int[] arr, int l, int r) {
if (l == r) return;
int m = l + ((r - l) >> 1);
mergeSort1(arr, l, m);
mergeSort1(arr, m + 1, r);
merge(arr, l, m, r);
}
public void merge(int[] arr, int l, int m, int r) {
int a = l, b = m + 1, i = l;
int[] help = new int[arr.length];
while (a <= m && b <= r) {
help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
}
while (a <= m) {
help[i++] = arr[a++];
}
while (b <= r) {
help[i++] = arr[b++];
}
for (int j = l; j <= r; j++) {
arr[j] = help[j];
}
}
注：
1.应该在merge方法中动态分配 help数组。如果是ACM风格的笔试算法，应该用静态的help数组和arr数组。
2.merge方法不涉及递归，其时间复杂度是O(n)
3.递归版的归并排序时间复杂度是O(n∗logn)
2 代码：归并排序非递归版
通过步长step控制。
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
import org.junit.Test;
public class MergeTest2 {
public void mergesSort2(int[] arr) {
int n = arr.length;
for (int l, m, r, step = 1; step < n; step <<= 1) {
l = 0;
while (l < n) {
m = l + step - 1;
if (m + 1 >= n) break;
r = Math.min(n - 1, l + (step << 1) - 1);
merge(arr, l, m, r);
l = r + 1;
}
}
}
public void merge(int[] arr, int l, int m, int r) {
int[] help = new int[arr.length];
int a = l, b = m + 1, i = l;
while (a <= m && b <= r) {
help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
}
while (a <= m) {
help[i++] = arr[a++];
}
while (b <= r) {
help[i++] = arr[b++];
}
for (int j = l; j <= r; j++) {
arr[j] = help[j];
}
}
@Test
public void test12() {
int[] arr = {89, 67, 0, -2, 67, 90, 34, 8, 2};
mergesSort2(arr);
for (int n : arr){
System.out.print(n + " ");
}
System.out.println();
}
}
从非递归版的归并排序可以很显然的看出时间复杂度是O(n∗logn)
外层的for循环根据步长step调整，就是logn，内层的while 循环每次都是要遍历的（不回退），就是n
所以时间复杂度是O(n∗logn)
如果是ACM风格的，需要辅助数组help，所以额外空间复杂度O(n)
有些资料说可以用原地归并排序，把额外空间复杂度变成O(1)，不要浪费时间去学
因为原地归并排序确实可以省空间，但是会让复杂度变成O(n2)
3 归并排序为什么比O(n2)的排序快？
很显然每次merge之后的一部分对下一次merge是有帮助的，也就是说每次每个部分的排序是不浪费的（在 merge 阶段，归并排序将两个已经有序的子数组合并成一个更大的有序数组）。不像选择排序（在0～n范围寻找最大值，将其放到0位置；在1~n范围寻找最大值，将其放到1位置……）每次挑选出最大值对于下一轮是没有用的，好像每次循环都是独立的，前一次循环和后一次循环没有什么关系（前一次循环对于后一次循环没有任何帮助）。
4 力扣-912. 排序数组
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
1
2
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
1
2
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
注
这道题一定要创建静态的help数组，否则会跑的“超出时间限制”。
解法1：归并排序递归版
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
class Solution {
public static int[] help = new int[50000];
public int[] sortArray(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return nums;
}
public void mergeSort(int[] arr, int l, int r) {
if (l == r) return;
int m = l + ((r - l) >> 1);
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
public void merge(int[] arr, int l, int m, int r) {
int a = l, b = m + 1, i = l;
while (a <= m && b <= r) {
help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
}
while (a <= m) {
help[i++] = arr[a++];
}
while (b <= r) {
help[i++] = arr[b++];
}
for (int j = l; j <= r; j++) {
arr[j] = help[j];
}
}
}
解法2：归并排序非递归版
还是要准备一个静态的help数组。
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
class Solution {
public static int[] help = new int[50001];
public int[] sortArray(int[] nums) {
int n = nums.length;
for (int l, m, r, step = 1; step < n; step <<= 1) {
l = 0;
while (l < n) {
m = l + step - 1;
if (m + 1 >= n) break;
r = Math.min(l + (step << 1) - 1, n - 1);
merge(nums, l, m, r);
l = r + 1;
}
}
return nums;
}
public void merge(int[] arr, int l, int m, int r) {
int a = l, b = m + 1, i = l;
while (a <= m && b <= r) {
help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
}
while(a <= m){
help[i++] = arr[a++];
}
while(b <= r){
help[i++] = arr[b++];
}
for (int j = l;j <= r;j++){
arr[j] = help[j];
}
}
}
