快速排序是一个最差时间复杂度为O(n²)的排序算法，这种情况通常出现在选择的轴值(pivot)不能将数组划分为两个长度相等的子数组的时候，比如数组逆序排列的时候，如果选择第一个数作为轴值，划分的子数组的大小分别为0和n-1，此时算法的性能最差。
一个较好的办法是“三数取中”，查看当前数组的第一个、中间一个和最后一个位置的数组，取其中位数，以此来降低轴值选择得不好的可能性。
JavaScript实现代码如下：
//作为对比，这里先给出未使用三数取中的情况
Array.prototype.swap = function (i, j) {
var t = this[i];
this[i] = this[j];
this[j] = t;
};
Array.prototype.quickSortHelper = function(start,end){
if(start>=end){
return;
}
var pivotIdx = start;
var pivot = this[pivotIdx];
var i = start+1;
var n = end;
while(i<=n){
if(this[i]<pivot){
//比轴值小则交换
this.swap(pivotIdx,i);
i++;
pivotIdx = i;
}else{
this.swap(n,i);
n--;
}
}
//递归地对子数组进行排序
this.quickSortHelper(start,pivotIdx-1);
this.quickSortHelper(pivotIdx+1,end);
}
Array.prototype.quickSort = function () {
this.quickSortHelper(0, this.length-1);
};
测试一下算法的性能：
function test () {
var arr = [];
for (var i = 0; i < 20000; i++) {
arr.push(Math.round(Math.random(i) * 100));
}
//为了测试，这里故意将数组按照逆序排序
arr.sort(function(x,y){
return y-x;
});
doTest(arr, 1);
}
function doTest(arr, n) {
var tStart = (new Date()).getTime();
var re = arr.quickSort(0,arr.length-1);
var tEnd = (new Date()).getTime();
console.log('快速排序使用时间是:' + (tEnd - tStart) + 'ms');
return re;
}
test();//输出：快速排序使用时间是:168ms
排序时间为168ms。
进行三数取中后，再来看看性能如何：
//将开头、中间、结尾位置的中间一个元素交换到开头
Array.prototype.partionMedianOfThree = function(start,end){
var mid = Math.floor(start+(end-start)/2);
if(this[start]>this[end]){
this.swap(start,end);
}
if(this[mid]>this[end]){
this.swap(mid,end);
}
if(this[mid]>this[start]){
this.swap(mid,start);
}
}
//quickHelper中先进行三数取中，其余地方不变
Array.prototype.quickSortHelper = function(start,end){
if(start>=end){
return;
}
this.partionMedianOfThree(start,end);
var pivotIdx = start;
var pivot = this[pivotIdx];
var i = start+1;
var n = end;
while(i<=n){
if(this[i]<pivot){
this.swap(pivotIdx,i);
i++;
pivotIdx = i;
}else{
this.swap(n,i);
n--;
}
}
this.quickSortHelper(start,pivotIdx-1);
this.quickSortHelper(pivotIdx+1,end);
}
结果现在的排序时间缩短到：22ms。在这种情况下的性能提升是非常显著的。
