咖啡伴侶

在ie6.0中快速排序算法比Array對象的sort方法快多了，對于元素比較少的，快速排序的速度基本上是sort方法的5倍左右，對于30000個元素快速排序是sort方法速度的十幾倍
在ff2.0中兩種排序算法速度基本上差不多，快速排序算法稍微快一點

<script>
function rand(m,n){
????? //生成一個m、n之間的整數(shù)
??????? var i=Math.random();
??????? return Math.round((n-m)*i+m);
?}
?????????? ?
?????????? ?
function getRandomArr(m,n,l){
? //m：生成隨即整數(shù)的最小值，n：生成隨即整數(shù)的最大值，l：生成的數(shù)組的長度
??? var resultArr=[];
??? for(var i=0;i<l;i++){
??????? resultArr.push(rand(m,n))
??? }
??? return resultArr;
}
??? ?
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; ?
} ?

function doSort(a,s,e) ?
{ ?
??? if(s<e) ?
??? { ?
??????? var pos=partition(a,s,e); ?
??????? doSort(a,s,pos-1); ?
??????? doSort(a,pos+1,e); ?
??? } ?
} ?
??? ?
Array.prototype.quickSort = function() ?
{ ?
????? doSort(this,0,this.length-1); ?
}


function sortIntF(a,b){return a-b}
function pk(num){
??? //num: 用于排序的數(shù)組的元素個數(shù)
??? //生成用于排序的數(shù)組
??? var arr=getRandomArr(1,999999,num);
??? ?
??? //當元素個數(shù)小于10000時，執(zhí)行n次取平均值 ?
??? var n=Math.ceil(10000/num);
??? ?
??? //生成多個用于排序的數(shù)組的拷貝
??? 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+"個元素的數(shù)組，平均每次排序花費時間如下：\n"
??? +"Array.prototype.sort："+((t3-t2)/n)+"ms\n"
??? +"quickSort："+((t2-t1)/n)+"ms\n"
??? );
??? ?
??? alert("排序結(jié)果是否正確："+(sortArrs[0].join()==quickSortArrs[0].join()));
}

pk(500);
pk(2000);
pk(30000);
</script>