欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

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

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

關(guān)于sort方法：sort方法是Array的一個內(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方法可以接受一個function類型的參數(shù)來自定義自己的排序邏輯，當(dāng)沒有提供參數(shù)的時候，默認按照字符順序排序，所以對整數(shù)排序需要提供一個function類型的參數(shù)，本測試的調(diào)用方式如下：

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

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

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

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

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

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

快速排序算法的實現(xiàn)，這個算法取自我看到的51js論壇上這個網(wǎng)友的實現(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()來判斷, 性能測試代碼如下：
復(fù)制代碼 代碼如下:

function sortIntF(a,b){return a-b}
function pk(num){
//num: 用于排序的數(shù)組的元素個數(shù)
//生成用于排序的數(shù)組
var arr=getRandomArr(1,999999,num);
//當(dāng)元素個數(shù)小于10000時，執(zhí)行n次取平均值
var n=Math.ceil(10000/num);
//生成多個用于排序的數(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("性能比較，對于"+num+"個元素的數(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ù)就可以了，例如你要對300個元素的數(shù)組進行排序性能比較，調(diào)用pk(300) 就可以了

完整的測試代碼如下：

測試結(jié)果
第一次 第一次 第一次(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
從結(jié)果中可以看到，
在ie6.0中快速排序算法比Array對象的sort方法快多了，對于元素比較少的，快速排序的速度基本上是sort方法的5倍左右，對于30000個元素快速排序是sort方法速度的十幾倍
在ff2.0中兩種排序算法速度基本上差不多，快速排序算法稍微快一點，這也說明ff2.0中Array對象的sort還是比較高效的，說不定就是用的快速排序，因為它跟快速排序算法的數(shù)據(jù)很接近
說明：上面的測試只代表我本機上的測試結(jié)果，也許在你機器上結(jié)果會有很大的區(qū)別，希望大家也幫忙測試一下

相關(guān)文章

最新評論