快速排序 JavaScript 实现
作为算法目录下的第一篇博文，快速排序那是再合适不过了。作为最基本最经典的算法之一，我觉得每个程序员都应该熟悉并且掌握它，而不是只会调用库函数，知其然而不知其所以然。
排序算法有10种左右（或许更多），耳熟能详的冒泡排序、选择排序都属于复杂度O(n^2)的“慢”排，而快排的复杂度达到了O(nlongn），快排是怎么做到的呢？跟着楼主一步步探索快排的奥秘吧。
注：如没有特殊说明，本文的快速排序都是针对数组，且排序结果从小到大。
快速排序其实就三步：
- 在需要排序的数组中，任选一个元素作为“基准”
- 将小于“基准”和大于“基准”的元素分别放到两个新的数组中，等于“基准”的元素可以放在任一数组
- 对于两个新的数组不断重复第一步第二步，直到数组只剩下一个元素，这时step2的两个数组已经有序，排序结果也很容易得到了（leftArray+基准元素+rightArray）
以数组[1, 2, 5, 4, 3]举例，第一次排序，找个基准，基准可以是数组的任意元素，为了方便说明，可以选择第一个元素，这里我以中间元素举例。于是找到5为基准，小于5和大于5的分别放到两个新的数组中，等于5的可以放到任意一边，第一次排序后，得到结果：
[1, 2, 4, 3] 5 []然后两个新的数组再次进行如上排序（例子中一个数组是空的，so只需进行一个数组的排序），我们可以很高兴地发现，如果左右两个数组分别排序完后，三个数组按顺序concat后就是我们要的结果了。
再看数组[1, 2, 4, 3]，选取中间元素4作为基准，排序后得到：
[1, 2, 3] 4 [] .. 5 []对于长度大于1的数组继续进行操作：
[1] 2 [3] 4 [] 5 []great！排序完毕！
接着我们用代码实现过程。
首先定义一个名为quickSort的函数，参数是一个需要排序的数组：
function quickSort(a) { }如果数组长度小于1，那么就不用进行排序了，直接返回数组：
function quickSort(a) { if (a.length <= 1) return a;}否则，我们取数组的中间元素，将数组中小于等于中间元素的元素放到left数组，大于中间元素的元素放到right数组：
function quickSort(a) { if (a.length <= 1) return a; var mid = ~~(a.length / 2) , midItem = a.splice(mid, 1)[0] , left = [] , right = []; a.forEach(function(item) { if (item <= midItem) left.push(item); else right.push(item); });}我们知道，如果left数组和right数组都已经排序完毕了，那么直接返回left+midItem+right组成的数组就大功告成了。但是left和right数组是无序的，怎么办？我们定义的quickSort()函数就是用来排序的，递归调用即可:
function quickSort(a) { if (a.length <= 1) return a; var mid = ~~(a.length / 2) , midItem = a.splice(mid, 1)[0] , left = [] , right = []; a.forEach(function(item) { if (item <= midItem) left.push(item); else right.push(item); }); var _left = quickSort(left) , _right = quickSort(right); return _left.concat(midItem, _right);}这样才真正的大功告成了，快速排序算法是不是也不那么难？
参考：阮一峰老师的快速排序（Quicksort）的Javascript实现
2016-10-13 补：
如果需要排序的数组有大量重复元素，可以用基于三向切分的快速排序大幅度提高效率。
基础的快排，每一次递归，我们将数组拆分为两个，递归出口是数组长度为 <=1。思考这样一个场景，递归过程中某个数组为 [1, 1, 1, 1, 1, 1, 1, 1]，如果是原始的快排，还需要继续递归下去，实际上已经不需要。所以我们可以用三向切分，简单地说就是将数组切分为三部分，大于基准元素，等于基准元素，小于基准元素。
我们可以设置一个 mid 数组用来保存等于基准元素的元素集合，以前取的基准元素是数组中间位置的元素，其实任意一个即可，这里选了最后一个，比较方便。
function quickSort(a) { if (a.length <= 1) return a; var last = a.pop() , left = [] , right = []; a.forEach(function(item) { if (item <= last) left.push(item); else right.push(item); }); var _left = quickSort(left) , _right = quickSort(right); return _left.concat(last, _right);}function quickSort3Way(a) { if (a.length <= 1) return a; var last = a.pop() , left = [] , right = [] , mid = [last]; a.forEach(function(item) { if (item < last) left.push(item); else if (item > last) right.push(item); else mid.push(item); }); var _left = quickSort3Way(left) , _right = quickSort3Way(right); return _left.concat(mid, _right);}// test cases // 最好 shuffle 下var arr = [];for (var i = 0; i < 1000; i++) for (var j = 0; j < 10; j++) // 包含大量重复元素 arr.push(i);console.log(console.time('quickSort'));quickSort(arr.concat()); // quickSort: 3407.842msconsole.log(console.timeEnd('quickSort'));console.log(console.time('quickSort3Way'));quickSort3Way(arr.concat()); // quickSort3Way: 215.705msconsole.log(console.timeEnd('quickSort3Way'));console.log(console.time('v8 sort'));arr.concat().sort(function(a, b) { return a - b;}); // v8 sort: 10.126msconsole.log(console.timeEnd('v8 sort'));测试中的这个 case，经过三向切分的快排的效率甚至比 v8 的 （代码写错了，囧）Array.prototype.sort() 还快了一点。
2017-03-21: 几天前的面试，面试官问我能不能用一行代码写快排，我回忆了下，感觉不行，面试官提示了用 filter 方法，今天试了下，还真是可以 ...
function quickSort(a) { return a.length <= 1 ? a : quickSort(a.slice(1).filter(item => item <= a[0])).concat(a[0], quickSort(a.slice(1).filter(item => item > a[0])));}
