一个优化的快速排序

Apr 17 2016 数据结构与算法

快速排序是一个最差时间复杂度为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.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

JavaScript, 算法