今天在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权威指南 中是这样定义的：

The sort( ) method sorts the elements of array in place: no copy of the array is made. If sort( ) is called with no arguments, the elements of the array are arranged in alphabetical order (more precisely, the order determined by the character encoding). To do this, elements are first converted to strings, if necessary, so that they can be compared.
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类型的参数，本测试的调用方式如下：

array.sort(function(a,b){return a-b})

当然如果要排序的整数位数相同，不提供参数返回的结果也是一样的，测试一下就知道：
<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]，显然不是我们要的结果
生成需要排序的数组，为了得到公正的结果我先随机生成用于排序的数组，每次比较中两种方法使用的数组都具有相同的元素，下面是生成随机数组的代码

function random(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(random(m,n))
}
return resultArr;
}

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

function doSort(a,s,e)
{
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)+"ms\n"
+"quickSort："+((t2-t1)/n)+"ms\n"
);
alert("排序结果是否正确："+(sortArrs[0].join()==quickSortArrs[0].join()));
}
直接调用pk函数就可以了，例如你要对300个元素的数组进行排序性能比较，调用pk(300) 就可以了

完整的测试代码如下：

测试结果
第一次 第一次 第一次(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还是比较高效的，说不定就是用的快速排序，因为它跟快速排序算法的数据很接近
说明：上面的测试只代表我本机上的测试结果，也许在你机器上结果会有很大的区别，希望大家也帮忙测试一下

评论 (0) All

登陆 还没注册？