Array.prototype.swap = function (i, j) {
  var t = this[i];
  this[i] = this[j];
  this[j] = t;
};
//三数取中，将开头、中间、结尾三个数中间那个数交换到数组开头
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);
    }
};
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);
}
Array.prototype.quickSort = function () {
  this.quickSortHelper(0, this.length-1);
};

function test () {
    var arr = [];
    for (var i = 0; i < 1000000; i++) {
        arr.push(Math.round(Math.random(i) * 10000));
    }
    doTest(arr, 1);
}
function doTest(arr, n) {
    var tStart = (new Date()).getTime();
    var re = arr.quickSort1(0,arr.length-1);
    var tEnd = (new Date()).getTime();
    console.log('快速排序使用时间是:' + (tEnd - tStart) + 'ms');
    return re;
}
test();//输出：快速排序使用时间是:227ms