快速排序是一个最差时间复杂度为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。在这种情况下的性能提升是非常显著的。