咖啡伴侣

在ie6.0中快速排序算法比Array对象的sort方法快多了，对于元素比较少的，快速排序的速度基本上是sort方法的5倍左右，对于30000个元素快速排序是sort方法速度的十几倍
在ff2.0中两种排序算法速度基本上差不多，快速排序算法稍微快一点

<script>
function rand(m,n){
      //生成一个m、n之间的整数
        var i=Math.random();
        return Math.round((n-m)*i+m);
 }
            
            
function getRandomArr(m,n,l){
  //m：生成随即整数的最小值，n：生成随即整数的最大值，l：生成的数组的长度
    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: 用于排序的数组的元素个数
    //生成用于排序的数组
    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)+"ms\n"
    +"quickSort："+((t2-t1)/n)+"ms\n"
    );
     
    alert("排序结果是否正确："+(sortArrs[0].join()==quickSortArrs[0].join()));
}

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