本文整理五種常見的 JavaScript 陣列排序實作,並附上原生 sort 的使用注意事項。每個版本都可直接複製使用。
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;
}
實務上這才是最該用的寫法。關鍵在於傳入比較函式,否則 sort 會以字串順序排序。
systemSort:function(array) {
return array.sort(function(a, b) {
return a - b;
});
}
取基準點後分左右兩側遞迴,平均時間複雜度 O(n log n),是實作上最實用的排序之一。
quickSort:function(array) {
var i = 0;
var j = array.length - 1;
var Sort = function(i, j){
// 結束條件
if(i == j ){
return
};
var key = array[i];
var tempi = i; // 記錄開始位置
var tempj = j; // 記錄結束位置
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;
}
}
}
}
// 如果第一個取出的 key 是最小的數
if(tempi == i){
Sort(++i, tempj);
return ;
}
// 最後一個空位留給 key
array[i] = key;
// 遞歸
Sort(tempi, i);
Sort(j, tempj);
}
Sort(i, j);
return array;
}
插入排序的改良版,透過逐步縮小的間距(gap)讓元素先大範圍地移動,最後再以 gap=1 收尾。這裡用了兩組預先算好的步長序列,分別針對小陣列與大陣列。
//Jun.array.shellSort(Jun.array.df(10000));
shellSort:function(array){
var tempArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在維基上看到這個最優的步長 較小數組
//var tempArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1] //針對大數組的步長選擇
var i = 0;
var tempArrtempArrLength = tempArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i < tempArrLength; i++){
if(tempArr[i] > len2){
continue;
}
tempSort(tempArr[i]);
}
// 排序一個步長
function tempSort(temp){
var i = 0, j = 0, f, tem, key;
var tempLen = len%temp > 0 ? parseInt(len/temp) + 1 : len/temp;
for(;i < temp; i++){
// 依次循環列
for(j=1;/*j < tempLen && */temp * j + i < len; j++){
//依次循環每列的每行
tem = f = temp * j + i;
key = array[f];
while((tem-=temp) >= 0){
// 依次向上查找
if(array[tem] > key){
array[tem+temp] = array[tem];
}else{
break;
}
}
array[tem + temp ] = key;
}
}
}
return array;
}
把每個元素往前插入到已排序的區段中,資料量小的時候效率相當不錯,而且近乎有序時接近 O(n)。
insertSort:function(array){
var i = 1, j, temp, key, len = array.length;
for(; i < len; i++){
temp = 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;
}
var arrDemo = new Array();
arrDemo[0] = 10;
arrDemo[1] = 50;
arrDemo[2] = 51;
arrDemo[3] = 100;
arrDemo.sort(); //調用sort方法後,數組本身會被改變,即影響原數組
alert(arrDemo);//10,100,50,51
// 默認情況下sort方法是按ascii字母順序排序的,而非我們認為是按數字大小排序
arrDemo.sort(function(a,b){return a>b?1:-1});//從小到大排序
alert(arrDemo);//10,50,51,100
arrDemo.sort(function(a,b){return a<b?1:-1});//從大到小排序
alert(arrDemo);//100,51,50,10
結論:
1、陣列呼叫 sort 之後會直接影響原陣列本身,而不是回傳新陣列。
2、sort() 預設以字元順序排序,對數字型陣列排序時,別理所當然地以為會按數值大小排。
3、想改變預設行為,就自行指定排序規則函式。
另外補充一個求值上的細節:比較函式請直接寫 return a - b,不要用 a > b ? 1 : -1。後者在 a 等於 b 時會回傳 -1,違反了比較函式「相等要回 0」的契約,在某些引擎上可能導致排序結果不穩定。
希望本文所述對大家 JavaScript 程式設計有所幫助。