咖啡伴侣

呆在上海
posts - 163, comments - 156, trackbacks - 0, articles - 2

快速排序 (转)

Posted on 2009-06-17 12:10 oathleo 阅读(1219) 评论(0)  编辑  收藏 所属分类: Web
在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>

只有注册用户登录后才能发表评论。


网站导航: