归并排序
一、算法描述
1.1 核心思想
- 二分，将数据二等均分，然后分别排序，再合并2个排好序的数据
- 递归，一直二等均分数据，直到无法分割后，才开始递归合并返回
- 整个二分和合并的过程类似于一棵二叉树，从下往上合并数据，先对子树排序，再合并成根节点
1.2 细节解释
比如说，数组 [5, 7, 2, 4, 3, 6, 1]。
首先是一直二等均分数据，直到无法分割为止：
1
2
| ___ ___ ___ ___ ___ ___ ___
| 5 | | 7 | | 2 | | 4 | | 3 | | 6 | | 1 |
|
然后从下往上开始合并排序返回：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| ___ ___ ___ ___ ___ ___ ___
| 5 | | 7 | | 2 | | 4 | | 3 | | 6 | | 1 | -- 原始数组
| | | | | | |
|_______| |_______| |_______| |
| | | |
V V V V
___ ___ ___ ___ ___ ___ ___
| 5 | 7 | | 2 | 4 | | 3 | 6 | | 1 | -- 第一层合并
| | | |
|_______________| |___________|
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 4 | 5 | 7 | | 1 | 3 | 6 | -- 第二层合并
| |
|_____________________________|
|
V
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | -- 第三层合并
|
归并排序采用的是分治思想，将小的有序数据逐渐合并成大的有序数据。
将 2 个有序数组合并成 1 个数组时，一般采用双指针，类似这样：
1
2
3
4
5
6
7
8
9
| lp rp
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 4 | 5 | 7 | | 1 | 3 | 6 | -- 当前数组
___ ___ ___ ___ ___ ___ ___
| | | | | | | | -- 额外空间
|
判断双指针指向元素的大小，小的放到额外空间中，然后移动指针：
1
2
3
4
5
6
7
8
9
| lp rp
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 4 | 5 | 7 | | 1 | 3 | 6 | -- 当前数组
___ ___ ___ ___ ___ ___ ___
| 1 | | | | | | | -- 额外空间
|
通过不断判断和移动双指针，最终可以完成对 2 个有序数组的合并：
1
2
3
4
5
6
7
8
9
| lp rp
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 4 | 5 | 7 | | 1 | 3 | 6 | -- 当前数组
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | | | | | | -- 额外空间
|
1
2
3
4
5
6
7
8
9
| lp rp
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 4 | 5 | 7 | | 1 | 3 | 6 | -- 当前数组
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | | | | | -- 额外空间
|
1
2
3
4
5
6
7
8
9
| lp rp
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 4 | 5 | 7 | | 1 | 3 | 6 | -- 当前数组
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | | | | -- 额外空间
|
1
2
3
4
5
6
7
8
9
| lp rp
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 4 | 5 | 7 | | 1 | 3 | 6 | -- 当前数组
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | | | -- 额外空间
|
1
2
3
4
5
6
7
8
9
| lp rp
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 4 | 5 | 7 | | 1 | 3 | 6 | -- 当前数组
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | 6 | | -- 额外空间
|
1
2
3
4
5
6
7
8
9
| lp rp
| |
V V
___ ___ ___ ___ ___ ___ ___
| 2 | 4 | 5 | 7 | | 1 | 3 | 6 | -- 当前数组
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | -- 额外空间
|
利用额外空间合并完成之后，再把排好序的数据回写到原数组即可。
二、算法实现
二分排序代码，将数据分割成2部分，分别排序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| sort(int[] arr, int start, int end) {
if (start + 1 >= end) {
return;
}
int mid = start + (end - start) / 2;
sort(arr, start, mid);
sort(arr, mid, end);
merge(arr, start, mid, end);
}
|
合并排好序的数据：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| merge(int[] arr, int start, int mid, int end) {
int n = end - start;
int[] tempArr = new int[n];
int i = start, j = mid, k = 0;
while (i < mid && j < end) {
if (arr[i] <= arr[j]) {
tempArr[k++] = arr[i++];
} else {
tempArr[k++] = arr[j++];
}
}
while (i < mid) {
tempArr[k++] = arr[i++];
}
while (j < end) {
tempArr[k++] = arr[j++];
}
System.arraycopy(tempArr, 0, arr, start, n);
}
|
三、算法分析
3.1 时间复杂度
- 最好时间复杂度：O(nlogn)
- 最坏时间复杂度：O(nlogn)
- 平均时间复杂度：O(nlogn)
3.2 空间复杂度
3.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
public class MergeSort implements Sort {
@Override
public void sort(int[] arr) {
sort(arr, 0, arr.length);
}
private void sort(int[] arr, int start, int end) {
if (start + 1 >= end) {
return;
}
int mid = start + (end - start) / 2;
sort(arr, start, mid);
sort(arr, mid, end);
merge(arr, start, mid, end);
}
private void merge(int[] arr, int start, int mid, int end) {
int n = end - start;
int[] mergeArr = new int[n];
int i = start, j = mid, k = 0;
while (i < mid && j < end) {
if (arr[i] <= arr[j]) {
mergeArr[k++] = arr[i++];
} else {
mergeArr[k++] = arr[j++];
}
}
while (i < mid) {
mergeArr[k++] = arr[i++];
}
while (j < end) {
mergeArr[k++] = arr[j++];
}
System.arraycopy(mergeArr, 0, arr, start, n);
}
}
|