# 合并排序（归并排序）
将原数组拆分成若干子数组，然后合并。
- 关键问题：合并两个有序数组
- 问题抽象
function merge(A, p, q, r) {
A: 数组
p: 左半边开始位置
q: 左半边结束，右半边开始位置
r: 右半边结束
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
∞ 作为哨兵
A1 数组定义 i
A2 数组定义 j
A 数组定义 k
比较 3 和 9 3 更小，将 3 回写到 A中， k加1 往下走一步
i 加1 比较 27 和 9 ，将 9 写入 A中 j 加 1
27 和 10 比较， 将 10 写入 A j 加 1
27 和 82 比较 ，将 27 写入A i 加 1
将 38 和 82 比较， 将 38 写入A i 加 1
将 43 和 82 比较， 将 43 写入 A i 加 1
将 ∞ 哨兵和 82 比较， 将 82 写入 A j 加 1
function merge (A, p, q, r) {
let A1 = A.slice(p, q) // 存放左半边的临时空间
let A2 = A.slice(q, r) // 存放右半边的临时空间
// 追加哨兵
A1.push(Number.MAX_SAFE_INTEGER)
A2.push(Number.MAX_SAFE_INTEGER)
for (let k = p, i = 0, j = 0; k < r; k++) {
// 循环不变式
// k: 下一个写入位置
// i: A1中回写的位置
// j: A2中回写的位置
A[k] = A1[i] < A2[j] ? A1[i++] : A2[j++]
}
}
const A = [1, 3, 5, 2, 4, 6] // [1, 2, 3, 4, 5, 6]
const B = [2, 4, 6, 1, 3, 5] // [2, 1, 3, 4, 6, 5]
const C = [2, 1] // [1, 2]
merge(A, 0, 3, 6)
merge(B, 1, 3, 5)
merge(C, 0, 1, 2)
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
- 归并排序的执行过程
function merge_sort (A, p, r) {
// 左闭右开
if (r - p < 2) {
return
}
const q = Math.ceil((p + r) / 2)
// 先排左半边
merge_sort(A, p, q)
// 在排右半边
merge_sort(A, q, r)
// 两边合并
merge(A, p, q, r)
}
const A = [38, 27, 43, 3, 9, 82, 10]
merge_sort(A, 0, A.length) // [3, 9, 10, 27, 38, 43, 82]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- 附图两个网络摘录图：
