gogoend
commented
4 years ago 尝试手写快排代码
（想不到都有一个月没动过这篇文章了，真是罪过。不过正好可以考一下自己还能不能记清快排的原理）
let arrToSort = [ 17, 7, 12, 32, 27, 6, 14, 22, 9, 3, 21 ];
function qSort(arr){
if(!arr.length) return arr
let [pivot,...rest] = arr
let smaller = [],bigger = [];
rest.forEach(item =>{
item>pivot ?bigger.push(item):smaller.push(item)
})
return [...qSort(smaller),pivot,...qSort(bigger)]
}
qSort(arrToSort)果然我还是忘了。。。又看了一遍上一节中提及的参考链接。
这个函数中巧妙使用了数组解构以及展开，简化了数组分割与合并的操作。
在使用快排时：
首先在传入数组中找到一个基准值pivot，用于和数组里其他元素做对比；此处用的pivot取的是数组里第一个元素，剩下的元素将放入到rest数组中。接下来将rest里的各个元素和基准值pivot进行对比，分别将较大值和较小值放入两数组，在基准值pivot两侧。
然后对基准值两侧的数组按照此处方法进行重复操作，进行递归。在递归过程中如果遇到空数组，则表示无元素可排序，直接返回空数组即可。当递归结束后，最终返回的、展开的数组将变得有序。
背景
今天在写对象深拷贝的时候，脑袋一片混乱 —— 因为它用到了递归。 当然，对象实质上是一种树状结构，每个分叉节点对象结构都十分类似。 emmmmm，于是我突然想起了之前困扰我多年的，传说中的快速排序，貌似也是一种用递归写比较方便的算法（虽然我也很懵）。。。So，这种排序的姿势到底是什么呢？
为什么快？
因为它用到了二分法。二分法嘛，我感觉应该就是把一个大问题拆分为两个小问题，两个小问题再拆分成四个更小的问题，直到不能再拆，问题应该也就解决了（个人愚见）。
试着解析原理
emmmm，比如随便来一个数组。
我们选择任意一个数字，作为排序基准
pivot。就选第一个吧，17。我们看看比17小的数和大的数都有哪些
得到
[ 7, 12, 6, 14, 9, 3 ] 17 [ 32, 27, 22, 21 ]接下来我们对两边集合中的内容，继续按照这种方式来排序。同样基准找第一个数。
得到
[ [ 6, 3 ] 7 [ 12, 14, 9 ] ] 17 [ [ 27, 22, 21 ] 32 [ ] ]再继续看各个基准数两边集合中的数
得到
[[[ 3 ] 6 [ ] ] 7 [[ 9 ] 12 [ 14 ]]] 17 [[ [22,21] 27 [] ] 32 [ ]]再继续
得到
[[[ 3 ] 6 [ ] ] 7 [[ 9 ] 12 [ 14 ]]] 17 [[ [ [ 21 ] 22 [] ] 27 [] ] 32 [ ]]终于排完了。。。
我们把最后这一步的排序结果集合格式化一下，你可以发现，它看起来像一棵树：
树的深度表示排序次数。
因此我认为，快速排序应该就是： 不断地依据基准值，拆分数组中的内容，比基准值小数放一堆，比基准值大的数值放另一堆，继续在这两堆中选一个基准值执行相关操作，直到最后每一堆里只剩下一个数值，此时数组排序完成。
一个实例代码
还不懂递归？读完这篇文章保证你会懂_javascript技巧_脚本之家
参考资料
快速排序 - 如果天空不死 - 博客园