对于经典算法，你是否也遇到这样的情形：学时觉得很清楚，可过阵子就忘了？
本系列文章就尝试解决这个问题。
研读那些排序算法，细品它们的名字，其实都很贴切。
比如归并排序，“归并”二字就是“递归”加“合并”。它是典型的分而治之算法。
image.png
上图中，先把数组一分为二，然后递归地排序好每部分，最后合并。
其中，分和归相对容易些（后面会说），该算法的核心是：如何合并两个已经排好序的数组？
解决办法很容易想到，两权相较取其轻。
image.png
如上图所示，每次比较取出一个相对小的元素放入结果数组中。
翻译成代码：
let left = [2, 4, 6], i = 0
let right = [1, 3, 5], 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, 5 ]
代码中，i和j分别是两个数组的下标。遍历结束后，某个数组可能会有剩余，全部追加到结果数组中就可以了：
if (i < left.length) {
result.push(...left.slice(i))
}
if (j < right.length){
result.push(...right.slice(j))
}
说明：为了清晰表达二者谁都可能剩余，这里没有直接使用if...else。事实上不会出现二者都有剩余情况的（while循环保证的）。另外，这里使用了数组相关API（concat也可以），也可以直接使用循环来做。
并，这个核心问题解决了，接下来我们来看看分和归。
关于分，只要把数组从中间劈成两半就行：
let m = Math.floor(array.length / 2)
let left = array.slice(0, m)
let right = array.slice(m)
至于递归，虽然它不符合线性思维，但其实也没啥难的。
只要有递归步骤（递归公式），很容翻译成代码的。
我们再回忆一下归并算法的步骤：
- 数组分成两半，left和right
- 递归处理left
- 递归处理right
- 合并二者结果
轻松翻译成代码：
function mergeSort(array) {
let m = Math.floor(array.length / 2)
let left = mergeSort(array.slice(0, m))
let right = mergeSort(array.slice(m))
return merge(left, right)
}
递归是自身调用自身，不能无限次的调用下去，因此需要有递归出口（初始条件）。
它的递归出口是，当数组元素个数为小于2时，就是已经是排好序的，不需要再递归调用了。
因此需要在前面加入代码：
if (array.length < 2) {
return array
}
完整代码如下
const utils = {
randomNum() {
return Math.floor(Math.random() * 100)
},
randomArray() {
return Array.from(Array(this.randomNum()), _ => this.randomNum())
}
}
function merge(left, right) {
let result = []
let i = 0, j = 0
while(i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++])
} else {
result.push(right[j++])
}
}
if (i < left.length) {
result.push(...left.slice(i))
} else {
result.push(...right.slice(j))
}
return result
}
function mergeSort(array) {
if (array.length < 2) {
return array
}
let m = Math.floor(array.length / 2)
let left = mergeSort(array.slice(0, m))
let right = mergeSort(array.slice(m))
return merge(left, right)
}
let array = utils.randomArray()
console.log(mergeSort(array))
至此，归并排序原理和实现已经说完了。
这里总结一下，归并排序需要额外空间，空间复杂度为O(n)，不是本地排序，相等元素是不会交换前后顺序，因而是稳定排序。时间复杂度为O(nlogn)，是比较优秀的算法，在面试题中出现的概率也很高。
归并排序和下一篇要讲的快速排序，都是分而治之算法，都需要分、归、并。前者重头戏在于如何去并，而后者重头戏在于如何去分。
网友评论