數(shù)據(jù)排序誰(shuí)最快(javascript中的Array.prototype.sort PK 快速排序)
但是讓我感到意外的是，下面有個(gè)網(wǎng)友回復(fù)說，javascript中的Array本身的sort方法才是最快的，比快速排序算法都快，當(dāng)時(shí)看到了很是郁悶，因?yàn)楫?dāng)時(shí)花了好長(zhǎng)時(shí)間在排序算法上，居然忘記了Array本身的sort方法
不過javascript中內(nèi)置的sort方法真的比快速排序算法還快嗎？
哈哈，測(cè)試一下不就知道了
先說一下我測(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ù)的類型、大小、數(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類型的參數(shù)來自定義自己的排序邏輯，當(dāng)沒有提供參數(shù)的時(shí)候，默認(rèn)按照字符順序排序，所以對(duì)整數(shù)排序需要提供一個(gè)function類型的參數(shù)，本測(cè)試的調(diào)用方式如下：
array.sort(function(a,b){return a-b})
當(dāng)然如果要排序的整數(shù)位數(shù)相同，不提供參數(shù)返回的結(jié)果也是一樣的，測(cè)試一下就知道：
<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ù)組的代碼
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)，代碼如下：
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()來判斷, 性能測(cè)試代碼如下：
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)，這也說明ff2.0中Array對(duì)象的sort還是比較高效的，說不定就是用的快速排序，因?yàn)樗焖倥判蛩惴ǖ臄?shù)據(jù)很接近
說明：上面的測(cè)試只代表我本機(jī)上的測(cè)試結(jié)果，也許在你機(jī)器上結(jié)果會(huì)有很大的區(qū)別，希望大家也幫忙測(cè)試一下
相關(guān)文章
彈出div顯示遮罩層的效果，想必大家都有見到過吧，下面有個(gè)示例，大家可以參考下2014-02-02
禁用鍵盤功能鍵的方法有很多，在本文為大家詳細(xì)介紹下，使用javascript如何實(shí)現(xiàn)禁用鍵盤功能鍵及其他鍵的方法，感興趣的朋友可以參考下2013-10-10
document.selection.createRange方法與實(shí)例
document.selection.createRange() 根據(jù)當(dāng)前文字選擇返回 TextRange 對(duì)象，或根據(jù)控件選擇返回 ControlRange 對(duì)象2006-10-10
最近在做項(xiàng)目的時(shí)候,遇到了有四舍五入保留兩位的需求,當(dāng)時(shí)不假思索的直接使用了js原生的toFixed方法,結(jié)果出現(xiàn)了問題,這篇文章主要給大家介紹了關(guān)于JS中toFixed()方法四舍五入精度問題的相關(guān)資料,需要的朋友可以參考下2021-10-10
JSP中使用JavaScript動(dòng)態(tài)插入刪除輸入框?qū)崿F(xiàn)代碼
這篇文章主要介紹了JSP中如何使用JavaScript動(dòng)態(tài)插入刪除輸入框,需要的朋友可以參考下2014-06-06
微信小程序繼承了微信強(qiáng)大的語(yǔ)音處理功能，提供了錄音、音頻播放控制和背景音樂等功能，它們的功能不同，但有相似性。本文將詳細(xì)介紹小程序中如何實(shí)現(xiàn)錄音與音頻播放控制功能，需要的可以參考一下2022-03-03
JS實(shí)現(xiàn)獲取鍵盤按下的按鍵并顯示在頁(yè)面上的方法
這篇文章主要介紹了JS實(shí)現(xiàn)獲取鍵盤按下的按鍵并顯示在頁(yè)面上的方法,涉及JavaScript針對(duì)鍵盤事件及頁(yè)面元素的相關(guān)操作技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-11-11
這篇文章主要為大家詳細(xì)介紹了微信小程序?qū)崿F(xiàn)簡(jiǎn)易封裝彈窗，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
技術(shù)上沒什么難的，就是定義一個(gè)隱藏的box，當(dāng)觸發(fā)上下文事件時(shí)顯示它，當(dāng)單擊body任意處時(shí)又隱藏它。2011-03-03
這篇文章主要介紹了JavaScrip常見的一些算法總結(jié)的相關(guān)資料,需要的朋友可以參考下2015-12-12