寫這篇主要是為了自我練習,並無實用價值。每個瀏覽器測出來的數據都不一樣——以 Chrome 來說,快速排序通常最快;IE 則要依陣列長度而定,短陣列下希爾排序反而可能勝出。另外提醒一句:不要用太大的資料量去測氣泡排序(瀏覽器當掉我不負責)。
// ---------- 一些排序算法 ----------
// 利用原生 sort 排序
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 i = 0;
var j = array.length - 1;
var Sort = function (i, j) {
// 結束條件
if (i == j) { return };
var key = array[i];
var stepi = i; // 記錄起始位置
var stepj = 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 (stepi == i) {
Sort(++i, stepj);
return;
}
// 最後一個空位留給 key
array[i] = key;
// 遞迴
Sort(stepi, i);
Sort(j, stepj);
}
Sort(i, j);
return array;
},
// 插入排序
insertSort: function (array) {
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;
},
// 希爾排序
shellSort: function (array) {
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // 較小陣列的步長序列
// var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035,
// 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1] // 大陣列用
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]);
}
// 對單一步長做插入排序
function stepSort(step) {
var i = 0, j = 0, f, tem, key;
var stepLen = len % step > 0 ? parseInt(len / step) + 1 : len / step;
for (; i < step; i++) { // 依序遍歷每一列
for (j = 1; step * j + i < len; j++) { // 遍歷該列的每一行
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;
}
希爾排序之所以在中等規模陣列上表現亮眼,關鍵在步長序列的選擇。上面這組步長是依據維基百科上針對較小陣列的建議;大陣列則建議改用差距懸殊的序列(如註解中的那組),讓早期的分割更粗、後期收斂更細。
而快速排序那段實作刻意用「挖坑填數」的方式在原地搬移,避免了額外套用陣列,這也是它在實測中領先的原因之一。若要投入正式專案,直接用原生 sort 並提供比較函式,通常仍是最省事且足夠快的選擇。