if(s<e)
{
var pos=partition(a,s,e);
doSort(a,s,pos-1);
doSort(a,pos+1,e);
}
}
function partition(a,st,en)
{
var s=st;
var e=en+1;
var temp=a[s];
while(1)
{
while(a[++s]<temp);
while(a[--e]>temp);
if(s>e)break;
var tem=a[s];
a[s]=a[e];
a[e]=tem;
}
a[st]=a[e];
a[e]=temp;
return e;
}
Array.prototype.quickSort=function(){
doSort(this,0,this.length-1);
}
检查结果是否正确使用array.join()来判断, 性能测试代码如下：
function sortIntF(a,b){return a-b}
function pk(num){
//num: 用于排序的数组的元素个数
//生成用于排序的数组
var arr=getRandomArr(1,999999,num);
//当元素个数小于10000时，执行n次取平均值
var n=Math.ceil(10000/num);
//生成多个用于排序的数组的拷贝
var quickSortArrs=[];
var sortArrs=[];
for(var i=0;i<n;i++){
quickSortArrs.push(arr.slice(0));
sortArrs.push(arr.slice(0));
}
var t1=new Date();
for(var i=0;i<n;i++){
quickSortArrs[i].quickSort();
}
var t2=new Date();
for(var i=0;i<n;i++){
sortArrs[i].sort(sortIntF);
}
var t3=new Date();
alert("性能比较，对于"+num+"个元素的数组，平均每次排序花费时间如下：n"
+"Array.prototype.sort："+((t3-t2)/n)+"msn"
+"quickSort："+((t2-t1)/n)+"msn"
);
alert("排序结果是否正确："+(sortArrs[0].join()==quickSortArrs[0].join()));
}
直接调用pk函数就可以了，例如你要对300个元素的数组进行排序性能比较，调用pk(300) 就可以了
完整的测试代码如下：
[Ctrl+A 全选 注:如需引入外部Js需刷新才能执行]
测试结果
第一次 第一次 第一次(ms)
500个元素: ie6.0: sort: 38.3 39.05 39.05
quickSort: 8.6 8.6 9.4
ff2.0: sort: 3.1 3.15 3.9
quickSort: 4.7 4.7 3.15
2000个元素: ie6.0: sort: 200 203.2 203
quickSort: 40.6 43.6 43.8
ff2.0: sort: 18.8 18.6 18.8
quickSort: 18.6 15.6 15.6
30000个元素: ie6.0: sort: 10360 9765 9203
quickSort: 843 813 891
ff2.0: sort: 422 422 406
quickSort: 328 297 407
从结果中可以看到，
在ie6.0中快速排序算法比Array对象的sort方法快多了，对于元素比较少的，快速排序的速度基本上是sort方法的5倍左右，对于30000个元素快速排序是sort方法速度的十几倍
在ff2.0中两种排序算法速度基本上差不多，快速排序算法稍微快一点，这也说明ff2.0中Array对象的sort还是比较高效的，说不定就是用的快速排序，因为它跟快速排序算法的数据很接近
说明：上面的测试只代表我本机上的测试结果，也许在你机器上结果会有很大的区别，希望大家也帮忙测试一下
