快捷導(dǎo)航

數(shù)據(jù)排序誰(shuí)最快(javascript中的Array.prototype.sort PK 快速排序)

更新時(shí)間：2007年01月10日 00:00:00 作者：

今天在51js論壇中看到一個(gè)網(wǎng)友發(fā)布了一個(gè)javasctipt實(shí)現(xiàn)的快速排序的算法，前些日子工作中也涉及到j(luò)avasctipt中數(shù)據(jù)排序的應(yīng)用，當(dāng)時(shí)為了提高排序速度，使用的也是快速排序的算法。

但是讓我感到意外的是，下面有個(gè)網(wǎng)友回復(fù)說(shuō)，javascript中的Array本身的sort方法才是最快的，比快速排序算法都快，當(dāng)時(shí)看到了很是郁悶，因?yàn)楫?dāng)時(shí)花了好長(zhǎng)時(shí)間在排序算法上，居然忘記了Array本身的sort方法
不過(guò)javascript中內(nèi)置的sort方法真的比快速排序算法還快嗎？
哈哈，測(cè)試一下不就知道了
先說(shuō)一下我測(cè)試的環(huán)境
1，我的測(cè)試環(huán)境是IE6.0和firefox2.0
2，每種算法有很多種不同的實(shí)現(xiàn)方法，下面測(cè)試中我選擇上面網(wǎng)友實(shí)現(xiàn)的快速排序算法，只是把內(nèi)嵌函數(shù)搬到了外面
3，算法執(zhí)行的速度與數(shù)據(jù)的類(lèi)型、大小、數(shù)據(jù)量的多少都有關(guān)系，我這里只比較小于 999999 的整數(shù)的排序，數(shù)據(jù)量分別定為500、2000、30000

關(guān)于sort方法：sort方法是Array的一個(gè)內(nèi)置的方法：javascript權(quán)威指南中是這樣定義的：

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方法可以接受一個(gè)function類(lèi)型的參數(shù)來(lái)自定義自己的排序邏輯，當(dāng)沒(méi)有提供參數(shù)的時(shí)候，默認(rèn)按照字符順序排序，所以對(duì)整數(shù)排序需要提供一個(gè)function類(lèi)型的參數(shù)，本測(cè)試的調(diào)用方式如下：

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

當(dāng)然如果要排序的整數(shù)位數(shù)相同，不提供參數(shù)返回的結(jié)果也是一樣的，測(cè)試一下就知道：

復(fù)制代碼代碼如下:

 
<script> 
alert( [3,4,5,11,1].sort()) 
alert([3,4,5,11,1].sort(function(a,b){return a-b})) 
</script>

提示：可以先修改了再運(yùn)行
得到的結(jié)果是 [1, 11, 3, 4, 5]，顯然不是我們要的結(jié)果
生成需要排序的數(shù)組，為了得到公正的結(jié)果我先隨機(jī)生成用于排序的數(shù)組，每次比較中兩種方法使用的數(shù)組都具有相同的元素，下面是生成隨機(jī)數(shù)組的代碼

復(fù)制代碼代碼如下:

 
function random(m,n){ 
//生成一個(gè)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ù)組的長(zhǎng)度 
var resultArr=[]; 
for(var i=0;i<l;i++){ 
resultArr.push(random(m,n)) 
} 
return resultArr; 
} 

快速排序算法的實(shí)現(xiàn)，這個(gè)算法取自我看到的51js論壇上這個(gè)網(wǎng)友的實(shí)現(xiàn)，代碼如下：

復(fù)制代碼代碼如下:

 
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); 
} 

檢查結(jié)果是否正確使用array.join()來(lái)判斷, 性能測(cè)試代碼如下：

復(fù)制代碼代碼如下:

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

直接調(diào)用pk函數(shù)就可以了，例如你要對(duì)300個(gè)元素的數(shù)組進(jìn)行排序性能比較，調(diào)用pk(300) 就可以了

完整的測(cè)試代碼如下：

[Ctrl+A 全選注:引入外部Js需再刷新一下頁(yè)面才能執(zhí)行]

測(cè)試結(jié)果
第一次第一次第一次(ms)
500個(gè)元素: 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個(gè)元素: 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個(gè)元素: ie6.0: sort: 10360 9765 9203
quickSort: 843 813 891
ff2.0: sort: 422 422 406
quickSort: 328 297 407
從結(jié)果中可以看到，
在ie6.0中快速排序算法比Array對(duì)象的sort方法快多了，對(duì)于元素比較少的，快速排序的速度基本上是sort方法的5倍左右，對(duì)于30000個(gè)元素快速排序是sort方法速度的十幾倍
在ff2.0中兩種排序算法速度基本上差不多，快速排序算法稍微快一點(diǎn)，這也說(shuō)明ff2.0中Array對(duì)象的sort還是比較高效的，說(shuō)不定就是用的快速排序，因?yàn)樗焖倥判蛩惴ǖ臄?shù)據(jù)很接近
說(shuō)明：上面的測(cè)試只代表我本機(jī)上的測(cè)試結(jié)果，也許在你機(jī)器上結(jié)果會(huì)有很大的區(qū)別，希望大家也幫忙測(cè)試一下

您可能感興趣的文章: