Javascript和快速排序
这里以递归为例，参考自慕课网刘波波老师的C++版本实现
普通快排
上过大学数据结构课程的人都知道，快速排序的核心就是选定一个哨兵，然后把它作为标准，对数据进行操作，把小的放前面，把大的放后面。然后执行这个过程若干次，就得到了最终的结果。
这个过程，实践了算法中的分治法，即把复杂的模块分成几个简单的模块分而治之，达到事半功倍的效果。
在这里，我推荐一个算法可视化网站：http://zh.visualgo.net/zh/sorting
很多常见的算法可以在上面快速的理解处理过程。
代码如下：
var quickSort = function (arr) {
__quickSort(arr, 0, arr.length - 1);
return arr;
}
var __quickSort = function (arr, start, end) {
if (start > end) {
return;
}
// p是哨兵排序完毕时的位置
var p = partition(arr, start, end);
__quickSort(arr, start, p - 1);
__quickSort(arr, p + 1, end);
return arr;
}
function partition(arr, start, end) {
// v是哨兵
var v = arr[start];
// j是分界线
var j = start;
//从第二个元素开始比较
for (var i = start + 1; i <= end; i++) {
if (arr[i] < v) {
//如果第i个元素比哨兵小，就和右边的大数交换，j就往右移了一位
[arr[j + 1], arr[i]] = [arr[i], arr[j + 1]];
// var tmp = arr[start];
// arr[start] = arr[j];
// arr[j] = tmp;
j++;
}
}
//把哨兵放在本应属于他的位置。
[arr[start], arr[j]] = [arr[j], arr[start]];
// var tmp = arr[start];
// arr[start] = arr[j];
// arr[j] = tmp;
return j;
}
快排性能测试
怎么知道我们算法的性能呢？我们可以新建一个模块，自动生成测试用例进行测试并且打印出耗时。
test.js
/**
*
* 自定义测试用例
* @param {any} n 元素个数
* @param {any} rangeL 范围内最小数，开区间
* @param {any} rangeH 范围内最大数，开区间
* @returns arr 数组
*/
function genTest(n, rangeL, rangeH) {
if (rangeH < rangeL) {
return;
}
var arr = [];
for (var i = 0; i < n; i++) {
arr.push(Math.floor(Math.random() * (rangeH - rangeL)) + rangeL);
}
return arr;
}
/**
*
* 耗时计算
* @param {any} func 要测试的回调函数
* @param {any} n 元素个数
* @param {any} [m=n] 最大值，默认为n
*/
function dif(func,n,m=n) {
console.time(`${func.name}算法耗时`);
func(genTest(n, 0, m));
console.timeEnd(`${func.name}算法耗时`);
}
exports.genTest = genTest;
exports.dif = dif;
这里有一个genTest函数用于产生一个数组，还有一个dif函数用于打印耗时。
然后在之前写的代码里导入,测试一个100万个数据的程序：
var test = require('./test');
...
test.dif(quickSort, 1000000)
优化快排
快排常常有两种边界情况需要被考虑：
1.如果待排序的数组是有序的，复杂度会到O(n^2)。
2.数组元素重复个数过多也会造成性能上的损耗。
所以针对这两种情况要进行优化：哨兵要随机选，针对重复的元素还要再加一个指针。
三路快排
这种快排通常被人叫做三路快排，因为它的代码中有三个指针，分别标识着小于哨兵的部分/等于哨兵的部分/大于哨兵的部分。
代码如下：
var test = require('./test');
//更加先进的：三路快排,可能是交换性能消耗大
var quickSortThreeWays = function (arr) {
var len = arr.length;
__quickSortThreeWays(arr, 0, len - 1);
return arr;
}
function __quickSortThreeWays(arr, start, end) {
if (start > end) {
return;
}
var rand = Math.round(Math.random() * (end - start));
//partition
[arr[start], arr[rand + start]] = [arr[rand + start], arr[start]];
var v = arr[start];
var lt = start; //arr[start+1...lt]<v
var gt = end + 1; //arr[gt...end]>v
var i = start + 1;
while (i < gt) {
if (arr[i] < v) {
[arr[i], arr[lt + 1]] = [arr[lt + 1], arr[i]];
lt++;
i++;
} else if (arr[i] > v) {
[arr[i], arr[gt - 1]] = [arr[gt - 1], arr[i]];
gt--;
} else { //arr[i]==v
i++;
}
}
[arr[start], arr[lt]] = [arr[lt], arr[start]];
__quickSortThreeWays(arr, start, lt - 1);
__quickSortThreeWays(arr, gt, end);
}
可以看到lt——i之间是小于哨兵的、i——gt之间是等于哨兵的，gt——end是大于哨兵的。
//测试三路快排性能
test.dif(quickSortThreeWays, 1000000)
由于我这里大量使用了解构赋值交换元素，所以也造成了性能上的损耗，再加上js本身不太适合实现底层算法，所以看上去还没有普通快排快，不过在C++写法中是绝对快出一筹的。
特殊情况
大量重复元素
我们把数组限定在0~10的整数范围内，同样生成一百万个。
test.dif(quickSort, 1000000,100)
test.dif(quickSortThreeWays, 1000000,100)
可以看出这时候三路快排已经比快排快了，而且还是没用解构赋值的快排，如果用解构赋值普通快排会溢出。
至于近乎有序的数组大家可以自己尝试写一个测试用例生成来测试~
其他写法
阮一峰前辈的博客里也有相关的实现，因为用的js原生api比较多，所以我称它为js写法，其实还有很多写法，这里就不一一列举了
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
可以看出，阮前辈使用了splice、concat等众多js本身的api，不过语义上好理解一些，那性能如何呢？我们来看看：
可以看出，这种写法的性能是比较低的。那两种特殊情况同理。
JS的sort()函数
不过实际上，JS早已帮我们内置好了排序函数，那就是sort()函数。关于sort()函数的实现，chrome是在元素大于10个时使用快排，小于10个的时候使用插入排序，其他的浏览器有用归并排序的，有用选择排序的...
那sort函数的性能如何呢？
我们来看看：
var jsSort = function (arr) {
return arr.sort((a, b) => { return a - b; });
}
test.dif(jsSort, 1000000);
这是node环境下的sort，可以看出，性能也不咋地，有兴趣的朋友可以去各个浏览器跑一下看看测试结果~~~
总之，快排虽然在jser们手下不需要手动实现，但是了解其中蕴含的算法思想是极为重要的。
