我想知道这是为什么 –费曼
《归并》指的是递归+合并，是典型的分而治之算法
把一个数组一分为二，递归地排序好每一部分，最后合并
并
这个算法的核心点是如何合并两个各自已经排好序的数组，所以先从合并开始
两权相较取其轻
数组 A 有一个指针 i
数组 B 有一个指针 j
将他们从头一个个比较，较小的就放到结果数组里，然后对应的指针++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
let left = [2, 4, 6, 9],
i = 0
let right = [1, 3, 6, 10, 11],
j = 0
let result = []
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i])
i++
} else {
result.push(right[j])
j++
}
}
console.log(result) //1,2,3,4,6,6,9
|
仔细看 result 里还漏了 right 里的 10 和 11，因为 left 的数字都已经放到 result 里了，i==left.length，循环就跳出了
所有还需要处理这种情况
1
2
3
4
5
6
|
if (i < left.length) {
result.push(...left.slice(i))
}
if (j < right.length) {
result.push(...right.slice(j))
}
|
为了清晰表达二者谁都可能剩余，这里没有直接使用 if…else。事实上不会出现二者都有剩余情况的（while 循环保证的）。另外，这里使用了数组相关 API（concat 也可以），也可以直接使用循环来做。
分
把一个数组一分为二
1
2
3
|
let middlePoint = Math.floor(array.length / 2) //length可能为奇数，向下取整
let left = array.slice(0, middlePoint)
let right = array.slice(middlePoint)
|
递归
递归的步骤： 1.数组分成两半 2.递归处理左边的部分 3.递归处理右边的部分 4.合并二者的结果
1
2
3
4
5
6
|
function mergeSort(array) {
let middlePoint = Math.floor(array.length / 2)
let left = merageSort(array.slice(0, middle))
let right = mergeSort(array.slice(middle))
return merge(left, right)
}
|
这里递归的出口是
当数组元素个数小于 2 时，就已经是排好序的不用再分了
1
2
3
|
if (array.length < 2) {
return array
}
|
下面是完整代码：
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
|
function merge(left, right) {
let i = 0
let j = 0
let result = []
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i])
i++
} else {
result.push(right[j])
j++
}
}
if (i < left.length) {
result.push(...left.slice(i))
}
if (j < right.length) {
result.push(...right.slice(j))
}
return result
}
function mergeSort(array) {
if (array.length < 2) {
return array
}
let middlePoint = Math.floor(array.length / 2)
let left = mergeSort(array.slice(0, middlePoint))
let right = mergeSort(array.slice(middlePoint))
return merge(left, right)
}
|
复杂度
归并排序需要额外空间，空间复杂度为 O(n)，不是本地排序，相等元素是不会交换前后顺序，因而是稳定排序。
时间复杂度为 O(nlogn)，是比较优秀的算法
我创建了一个集合 jest 可以测试算法的靶场项目：
https://github.com/Llane00/algorithm-range-tests
将同步文章中的代码到这个项目下
使用 vscode 的读者可以安装拓展插件 jest，这个插件可以自动检测 test 文件自动运行，非常方便。
感谢老姚的文章 手写算法并记住它：归并排序
