js快速排序

快速排序的基本思想是:

1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数

概括起来就是”挖坑填数,分二治之”。

因为网上具体讲解快速排序的思路的博客很多,这里直接上代码。
读了《算法图解》,发现以前自己写的快排真是的太扯淡了,一坨屎啊,下面这个优雅得不行~~~哈哈哈

1
2
3
4
5
6
7
8
function quickSort(arr){
if(arr.length<2) return arr;
var baseValue = arr[0];
let less = arr.slice(1).filter(d=>d<=baseValue);
let greater = arr.slice(1).filter(d=>d>baseValue);

return [].concat(quickSort(less),baseValue,quickSort(greater));
}