注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

骇客归来

ぁ枫あ

 
 
 

日志

 
 

数据排序谁最快(javascript中的Array.prototype.sort PK 快速排序)  

2007-01-27 11:55:33|  分类: Javascript |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今天在51js论坛中看到一个网友发布了一个javasctipt实现的快速排序的算法,前些日子工作中也涉及到javasctipt中数据排序的应用,当时为了提高排序速度,使用的也是快速排序的算法。

但是让我感到意外的是,下面有个网友回复说,javascript中的Array本身的sort方法才是最快的,比快速排序算法都快,当时看到了很是郁闷,因为当时花了好长时间在排序算法上,居然忘记了Array本身的sort方法

不过javascript中内置的sort方法真的比快速排序算法还快吗?

哈哈,测试一下不就知道了

先说一下我测试的环境

1,我的测试环境是IE6.0和firefox2.0
2,每种算法有很多种不同的实现方法,下面测试中我选择上面网友实现的快速排序算法,只是把内嵌函数搬到了外面
3,算法执行的速度与数据的类型、大小、数据量的多少都有关系,我这里只比较 小于 999999 的整数的排序,数据量分别定为500、2000、30000


关于sort方法:sort方法是Array的一个内置的方法javascript权威指南 中是这样定义的:



If you want to sort the array elements in some other order, you must supply a comparison function that compares two values and returns a number indicating their relative order. The comparison function should take two arguments, a and b, and should return one of the following:

sort方法可以接受一个function类型的参数来自定义自己的排序逻辑,当没有提供参数的时候,默认按照字符顺序排序,所以对整数排序需要提供一个function类型的参数,本测试的调用方式如下:



当然如果要排序的整数位数相同,不提供参数返回的结果也是一样的,测试一下就知道:

<script> alert( [3,4,5,11,1].sort()) alert([3,4,5,11,1].sort(function(a,b){return a-b})) </script>
提示:可以先修改了再运行

得到的结果是 [1, 11, 3, 4, 5],显然不是我们要的结果

生成需要排序的数组,为了得到公正的结果我先随机生成用于排序的数组,每次比较中两种方法使用的数组都具有相同的元素,下面是生成随机数组的代码

 
              //生成一个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(random(m,n))
        }
        return resultArr;
    }



快速排序算法的实现,这个算法取自我看到的51js论坛上这个网友的实现,代码如下:

   
    {
        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 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函数就可以了,例如你要对300个元素的数组进行排序性能比较,调用pk(300) 就可以了

 完整的测试代码如下:
<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>
提示:可以先修改了再运行

测试结果

                                                            第一次       第一次      第一次(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还是比较高效的,说不定就是用的快速排序,因为它跟快速排序算法的数据很接近

说明:上面的测试只代表我本机上的测试结果,也许在你机器上结果会有很大的区别,希望大家也帮忙测试一下

  评论这张
 
阅读(265)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017