快捷導(dǎo)航

JavaScript中幾種常見排序算法小結(jié)

更新時(shí)間：2011年02月22日 19:47:37 作者：

JavaScript中幾種常見排序算法小結(jié)，學(xué)習(xí)js的朋友可以參考下，下面對(duì)多種方法進(jìn)行了簡單的小結(jié)。

說明
寫這個(gè)主要是為了鍛煉自己，并無實(shí)際意義。
每個(gè)瀏覽器測(cè)試得出的數(shù)據(jù)會(huì)不一樣。比如我用chrome 測(cè)試一般快速排序都會(huì)最快，IE 則根據(jù)數(shù)組長度有可能希爾最快。
不要用太大數(shù)據(jù)去測(cè)試冒泡排序(瀏覽器崩潰了我不管)
如果有興趣可以下載測(cè)試頁面

個(gè)人理解

冒泡排序：最簡單，也最慢，貌似長度小于7最優(yōu)
插入排序：比冒泡快，比快速排序和希爾排序慢，較小數(shù)據(jù)有優(yōu)勢(shì)
快速排序：這是一個(gè)非?？斓呐判蚍绞?，V8的sort方法就使用快速排序和插入排序的結(jié)合
希爾排序：在非chrome下數(shù)組長度小于1000，希爾排序比快速更快
系統(tǒng)方法：在forfox下系統(tǒng)的這個(gè)方法非常快

算法源碼

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

 
// ---------- 一些排序算法 
// js 利用sort進(jìn)行排序 
systemSort:function(array){ 
return array.sort(function(a, b){ 
return a - b; 
}); 
}, 
// 冒泡排序 
bubbleSort:function(array){ 
var i = 0, len = array.length, 
j, d; 
for(; i<len; i++){ 
for(j=0; j<len; j++){ 
if(array[i] < array[j]){ 
d = array[j]; 
array[j] = array[i]; 
array[i] = d; 
} 
} 
} 
return array; 
}, 
// 快速排序 
quickSort:function(array){ 
//var array = [8,4,6,2,7,9,3,5,74,5]; 
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]; 
var i = 0; 
var j = array.length - 1; 
var Sort = function(i, j){ 
// 結(jié)束條件 
if(i == j ){ return }; 
var key = array[i]; 
var stepi = i; // 記錄開始位置 
var stepj = j; // 記錄結(jié)束位置 
while(j > i){ 
// j <<-------------- 向前查找 
if(array[j] >= key){ 
j--; 
}else{ 
array[i] = array[j] 
//i++ ------------>>向后查找 
while(j > ++i){ 
if(array[i] > key){ 
array[j] = array[i]; 
break; 
} 
} 
} 
} 
// 如果第一個(gè)取出的 key 是最小的數(shù) 
if(stepi == i){ 
Sort(++i, stepj); 
return ; 
} 
// 最后一個(gè)空位留給 key 
array[i] = key; 
// 遞歸 
Sort(stepi, i); 
Sort(j, stepj); 
} 
Sort(i, j); 
return array; 
}, 
// 插入排序 
insertSort:function(array){ 
// http://baike.baidu.com/image/d57e99942da24e5dd21b7080 
// http://baike.baidu.com/view/396887.htm 
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]; 
var i = 1, j, step, key, 
len = array.length; 
for(; i < len; i++){ 
step = j = i; 
key = array[j]; 
while(--j > -1){ 
if(array[j] > key){ 
array[j+1] = array[j]; 
}else{ 
break; 
} 
} 
array[j+1] = key; 
} 
return array; 
}, 
// 希爾排序 
//Jun.array.shellSort(Jun.array.df(10000)); 
shellSort:function(array){ 
// http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F 
// var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]; 
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在維基上看到這個(gè)最優(yōu)的步長 較小數(shù)組 
//var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//針對(duì)大數(shù)組的步長選擇 
var i = 0; 
var stepArrLength = stepArr.length; 
var len = array.length; 
var len2 = parseInt(len/2); 
for(;i < stepArrLength; i++){ 
if(stepArr[i] > len2){ 
continue; 
} 
stepSort(stepArr[i]); 
} 
// 排序一個(gè)步長 
function stepSort(step){ 
//console.log(step) 使用的步長統(tǒng)計(jì) 
var i = 0, j = 0, f, tem, key; 
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step; 

for(;i < step; i++){// 依次循環(huán)列 
for(j=1;/*j < stepLen && */step * j + i < len; j++){//依次循環(huán)每列的每行 
tem = f = step * j + i; 
key = array[f]; 
while((tem-=step) >= 0){// 依次向上查找 
if(array[tem] > key){ 
array[tem+step] = array[tem]; 
}else{ 
break; 
} 
} 
array[tem + step ] = key; 
} 
} 
} 
return array; 
} 