亲爱的观众老婆们大家好，欢迎大家欢迎来到一可的昆特牌馆小白的地盘（看在我为你宣传的份上，跪求别告我侵权台词啊T.T）。相信大家都直面过被人要求手写排序算法的恐惧，尤其对于转行的小前端来说，简直就是噩梦。网上其实有蛮多资料的，虽然为了面试背下来也未尝不可，但作为志愿刷遍LeetCode Easy难度的男人而言，知其然不知其所以然是绝对不行，接下来，我会用最小白的方式解释快速排序算法到底是怎么一回事。
注意：以下教程全是小白的，老鸟基本可以跳过，但如果你愿意鞭笞我，那也是极好的（手动滑稽）。
快速排序
先贴纯代码：
function quickSort(arr) {
if (arr.length < 2) {
return arr;
}
const firstItem = arr[0];
const lessThanNum = [];
const moreThanNum = [];
for (let i = 1, len = arr.length; i < len; i++) {
let item = arr[i];
if (item < firstItem) {
lessThanNum.push(item);
} else {
moreThanNum.push(item);
}
}
return [...quickSort(lessThanNum), num, ...quickSort(moreThanNum)];
}
quickSort([5, 4, 3, 21,]) //[1,2,3,4,5]
这是我自己实现的快速排序，接下来，我将具体拆解每一步，希望能让观众老爷看懂其中的原理。
首先请看这：
const firstItem = arr[0];
const lessThanNum = [];
const moreThanNum = [];
在函数内，创建了三个新的变量，首先获取传入数组首项的值（其实其他项都可以，只是我为了循环方便所以用首项）。另外两个两个变量是一个空数组，估计看名字就大概猜出有什么用。
断点此处，此时执行完时firstItem的值为5，lessThanNum与moreThanNum暂时还是空数据。
之后循环：
for (let i = 1, len = arr.length; i < len; i++) {
const item = arr[i];
if (item < num) {
lessThanNum.push(item);
} else {
moreThanNum.push(item);
}
}
这个估计不用我多做解释了，就是循环传入数组除首项外的每一项，小于首项的塞进去lessThanNum，反之塞进去moreThanNum。也是蛮好懂的对吧？那么想一下，执行完之后，lessThanNum与moreThanNum数组是什么呢？
此时lessThanNum为[4, 3, 2, 1],moreThanNum为[]。
在之后，就是最后一步，也可能是第一次接触递归的同学最懵的一步：
return [...quickSort(lessThanNum), num, ...quickSort(moreThanNum)];
估计有同学会感觉，每个字母我都看得懂，语法我也认识，但为啥就能排序啊？没关系，我们慢慢看一下到底是个什么鬼。
首先我们先转个弯，假设最后一步是：
return [...lessThanNum.sort((a, b) => a - b), num, ...moreThanNum.sort((a, b) => a - b)]
这样，是不是很好理解？num就是中间的数嘛，小于它的数的集合被排序了，大于它的数的集合也被排序了，它们再整成个数组，不就是得到一个完全排好序的集合了么？
OK，那我们想下，两个不同其实就在于快速排序里，调用的是quickSort()而不是sort((a, b) => a - b)，只要我们确认quickSort()是可以得到排序后的数组，就可以了。
那么，我们脑补一下吧，我们最后一步执行的是什么呢？其实就是return [...quickSort([4, 3, 2, 1]), 5, ...quickSort([])];。空数组暂时忽略，先研究quickSort([4, 3, 2, 1])，聪明的你估计能想得到，执行完之后会得到return [...quickSort([3, 2, 1]), 4, ...quickSort([])];。如此类推，我们聚焦到最后执行quickSort([2, 1])的时候。
此时，我们知道最后的结果肯定是return [...quickSort([1]), 2, ...quickSort([])];，那么我们执行quickSort([1])。如果quickSort内判断，当数组长度小于等于1时，返回数组本身，那么你肯定能推出return [...quickSort([1]), 2, ...quickSort([])];其实就是return [...[1], 2, ...[]];。这就是个数组解构嘛，也就是rturn [1, 2]。啦啦啦，得到排序好的数组啦。
那么，此时你可以记下quickSort([2, 1])的值为[1, 2].那么quickSort([3, 2, 1])的值为[...quickSort([2, 1]), 3, ...quickSort([])];。也就是[...[1, 2], 3, ...[]];，是不是感觉到有点打开了新世界的大门了？其实也就是说，quickSort(arr)是会返回排序后的数组的，稍微抽象一下，不就是return [...quickSort(lessThanNum), num, ...quickSort(moreThanNum)];，现在再看这句话：num就是中间的数嘛，小于它的数的集合被排序了，大于它的数的集合也被排序了，它们再整成个数组，不就是得到一个完全排好序的集合了么？ 是不是很好理解了？
小结
so，返回去看看我刚开始的代码，是不是有点感觉了？有没有感觉其实就是绕圈圈？之后，请尝试理解这句充满恶意的话：
要理解递归,你先要理解递归。
这句话其实就是递归的，只是它差了个边界，也就是快速排序代码里面的：
if (arr.length < 2) {
return arr;
}
那么，如果这句话是这样呢：要理解递归,你先要理解递归，直至看到小白的教程就能理解递归。我知道这比较无耻，但其实递归就是这样的。理解了那句充满恶意的话，你对递归，已经有一定的掌握了，也就不用去背算法，只要知道原理，自己实现即可。
文章到此为止，感谢阅读，希望没有浪费你的时间，也对你有点帮助，谢谢！
（最后的最后，其实本来打算把归并也写了的，后面吃了个饭就懒了。有兴趣的话可以告诉我一下，我会用差不多逗比的文风写归并排序。）