引子
我常常会想解决算法问题的开始在哪里，难道是记下茫茫多的解决技巧，或者是熟悉于特定的编程语言，还是说题海战术？
可我们的精力能力有限，特别是平时工作并不是面向算法开发的，而在这样的背景下，如果想领悟算法本质。我觉得最讲究的，最根源的，还是如何从零开始，挖掘一个统一通用的解决技巧。
为了解决一个问题，最简单的办法，就是把其他的可变条件简单化。而我打算从最简单的归并排序开始...
经典问题
//正整数排序
arr=[2322,981,333,121,9901]
思考过程：
- 5个数排序太难了
- 4个数会不会，不会
- 3个会不会，不会
- 2个呢，会
- 1个，不用排
sort=([a,b]) => a>b ? [b,a] : [a,b]
所以其实我们如果搞定了n=1/n=2,那么我们只需要找n=3/4/5转化成n=2的方法即可
分治
最经典的分治在这里被提出了，其实也是符合最早数学家的想法的
- n=3可以化为两个数组n=2和n=1
- 将两个数组排好序的数组，然后结合起来
arr1=[2,5] arr2=[3,4]
arr3=[2,3,4,5]
- 想要结合，其实我们就很自然想到最笨的办法，一个个遍历/对比,因为数字量小，所以人类很快的能得出结果
- n=4可以化为n=2和n=2；n=5可以化为n=2和n=3
- ok，我们找到了规律
a1..n, n=1
sort(a1,...,an){ a1>a2?[a2,a1]:[a1:a2], n=2
merge(sort(a1..n/2),sort(an/2+1...n), n>=3
小结：分治法其实是早期解决问题思路的开端，人类是习惯于解决简单的问题的，找到了简单问题的解法，再把问题转化为，如何把复杂问题简单化。这也是数学思路解算法问题的入口。
算法
其实当我们推理出了公式，将它转发成伪代码甚至代码都是很简单的一件事
sort = (arr) => {
if (arr.length <= 1) return arr
// 当n=2时，也可以转化成n=3的问题解决
return merge(sort(arr.slice(0, parseInt(arr.length / 2))), sort(arr.slice(parseInt(arr.length/2))))
}
我们还有一个merge函数没有实现，这个merge就是之前说的n=2时可以手动循环遍历的过程，之前说过，循环遍历是人类的思想，所以我们尝试用人类思想描述一下merge
// 人类白话实现merge
merge = (a, b) => {
let c=[], i=0, k=0
while (i<a.length || k<b.length) {
if (k<=b.length) {c.push(a[i]); i+=1}
else if (i >=a.length){c.push(b[k]); k+=1}
else if (a[i] < b[k]) {c.push(a[i]); i+=1}
else {c.push(b[k]); k+=1}
}
return c
}
又回到人类思想的通病，白话实现起来很简单，但是似乎就是很难证明是对的，害怕自己的思想有遗漏，但谁让它更接近人类思维，更好想象。
高中时候，做数学题，证明自己的猜想时，我们一般用代入法，n=3，n=4，n=5好像都是对的，那就应该是对的。
如何实在想完全证明是对的，数学思路的数学归纳法是你的出路，我们也可以用递归写一个merge
merge = (a, b) => {
if (!a.length) return b
if (!b.length) return a
// 每次拿出a数组最左边的一个数字first
let [first, ...rest] = a
// 在b数组中找到比最左边的数字小的数集合bMove
const bMove = b.filter(v => v < first)
// 将bMove放在最左边，中间放first，右边把剩下的递归merge
return [...bMove, first, ...merge(rest, b.filter(v => v >= first))]
}
乍一看数学公式是真好理解，但其实我们用了concat（解构）/ filter等函数，这些函数其实实现是未知的
小结：这个时候，这个算法雏形已经出来了，从零开始，我们利用分治法，将问题简单到可以人类解决的时候，再用归纳法证明，最后转化成代码。而且run起来，完全是已经可以准确排序了。
优化
为什么说只是雏形呢，因为算法不仅仅是解题，考虑的还有复杂度问题
性能分析：
- 空间上：每次slice会开辟新的内存，每次filter和解构也会开辟新的内存
- 时间上：数学思路大量运用递归，每次压栈都要出栈。
性能优化：
-
如何节约内存空间？就地操作
-
如何节约时间操作？改造递归为尾递归或者循环，并尽量减少循环次数
// 改造merge，传进来一个数组，以及它排序好的左右截断的middle，而不是传两个数组
merge = (arr, start, end, middle) => {
if (end - start > 1) {
// 直接取数组第一位，没有解构开辟新数组
let pivot = arr[start]
let offset = 0
// 遍历右边一截，找到比pivot小的偏移量，因为右边已经排好序，一旦找到比pivot大的则说明已经找完，退出不必要的循环
for (let i = middle; i < end; i++) {
if (arr[i] <= pivot) {
offset += 1
} else {
break
}
}
if (offset > 0) {
//将偏移的一整坨挪动到数组的头部，完成就地变换
let move = arr.splice(middle, offset)
arr.splice(start, 0, ...move)
}
// 递归merge
start = start + offset + 1
middle = middle + offset
merge(arr, start, end, middle)
}
return arr
}
sort也要配合改一下，入出参
sort = (arr, start, end) => {
start = start || 0
end = end || arr.length
let middle = parseInt((start + end) / 2)
if (end - start > 1) {
sort(arr, start, middle)
sort(arr, middle, end)
}
return merge(arr, start, end, middle)
}
小结：到这儿这个归并排序已经十分ok了。虽然优化空间肯定是还有的。但是思考方向是一致的。
自顶向下vs自底向上
问题的解法一定不止一种，取决于你思考的方式。之前的思路是对整个数组进行逐步切分的自顶向下。但从结果看，最后我们是分治到了n=2和n=1的情况。
既然分治的结果是最简单化（这里是分割到n=2），那么，其实也可以自底向上，优先每隔两个数字化分数组，然后两两merge，再四四merge，再八八……
// 自底向上实现sort
sort = (arr) => {
for(let size = 2; size / 2 < arr.length; size *= 2) {
console.log('size=', size)
for(let i = 0; i < arr.length; i += size ) {
let middle = i + size / 2
merge(arr, i, i + size, middle)
console.log(arr)
}
}
return arr
}
区别于之前的sort，自底向上的思路更工整更好理解，原因在于我们融入了人类的思考。但是人类的思考弊端就是它是取决于个人的经验积累，好懂的好懂，难懂的也难懂。它不像数学思维，很容易证明也很难推翻它，因为它是层层推理得来，没有什么理解瓶颈
总结
并不在于怎么解决归并排序，却从头到尾分析了归并排序。
原因很简单：为了解决一个问题，最简单的办法，就是把其他的可变条件简单化。为了研究如何从零到一地思考算法，以最简单的排序问题入口，从最开始的归并问题说起。
网友评论