今天在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) 就可以了
完整的測試代碼如下：
<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>
[Ctrl+A 全選 注:如需引入外部Js需刷新才能執行]
測試結果
第一次 第一次 第一次(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還是比較高效的，說不定就是用的快速排序，因為它跟快速排序算法的數據很接近
說明：上面的測試只代表我本機上的測試結果，也許在你機器上結果會有很大的區別，希望大家也幫忙測試一下
詳細出處參考：http://www.jb51.net/article/6136.htm