DIV CSS 佈局教程網

三種 JS 排序演算法分享:插入排序、希爾排序與歸併排序
編輯:關於JavaScript     

以下三個排序各自對應不同的思路,其中插入排序與希爾排序共用同一個交換輔助函式。

交換輔助函式

refer 負責判斷是否需要交換,需要的話交換後再遞迴往前推進一個間距:

/**
* 值交換操作
* arr 被操作的陣列
* i 被操作元素索引
* j 兩元素的距離
*/
function refer(arr, i, j){
var change = (arr[i] - arr[i - j]) < 0 ? true : false, value;
if (change) {
value = arr[i];
arr[i] = arr[i - j];
arr[i - j] = value;
return arguments.callee(arr, i - j, j);
}
else {
return arr;
}
}

插入排序

從第二個元素開始,只要比前一個小就往回交換,直到落定位:

function insert(array){
for (var i = 1, len = array.length; i < len; i++) {
if (array[i] < array[i - 1]) {
refer(array, i, 1);
}
}
return array;
}

注意這裡的 refer 只在「相鄰且逆序」時被呼叫一次,若元素需要往前挪好幾格,是靠 refer 內部的遞迴一路補完的。

希爾排序

插入排序的改良版:先用較大的間距做粗排序,讓元素能一次跨越多格,再逐步收斂間距至 1:

function shell(array){
var length = array.length, value;
for (var i = Math.floor(length / 2); i > 0; i = Math.floor(i / 2)) {
for (var j = i; j < length; j++) {
if (array[j] < array[j - i]) {
refer(array, j, i);
}
else {
continue;
}
}
}
return array;
}

間距序列這裡用的是最樸素的 n/2 折半,實務上改用 Knuth 序列(3h+1)或 Sedgewick 序列會更快。

歸併排序

把兩個已排序陣列合併成一個:

function order(arr1, arr2){
var arrLong = arr1.length > arr2.length ? arr1 : arr2;
var arrShort = arr1.length <= arr2.length ? arr1 : arr2;
var arr = [];
for (var i = 0, l = arrShort.length; i < l; i++) {
for (var j = 0, len = arrLong.length; j < len; j++) {
if (arrShort[i] < arrLong[j]) {
arr.push(arrShort[i]);
if (i == l - 1) {
for (var m = 0, n = arrLong.length; m < n; m++) {
arr[arr.length] = arrLong[m];
}
}
break;
}
else {
arr.push(arrLong[j]);
arrLong.shift();
continue;
}
}
}
return arr;
}

幾點效能上的提醒

arguments.callee 已不建議使用。在 strict mode 下它會直接報錯,而且會妨礙引擎優化。改成具名函式運算式即可,例如 var refer = function refer(arr,i,j){...},內部就能用 refer 這個名字遞迴。

arrLong.shift() 是隱形成本。shift 需要把後續所有元素往前搬一格,是 O(n) 操作,放在雙層迴圈裡會讓歸併從理想的 O(n) 退化成 O(n²)。改用一個獨立游標指向 arrLong 的目前位置,效率會好很多。

用減法比較有 overflow 風險。refer 裡的 arr[i] - arr[i-j] 遇到極大或極小數值時可能得到 NaN,改用 arr[i] < arr[i-j] 更安全。

這三段的共同優點是短、易讀、好懂;若要在正式環境處理大量資料,仍然建議直接用原生的 Array.prototype.sort 並搭配型別化的比較函式,引擎內部對小陣列會改用插入排序、大陣列改用 TimSort,實測通常優於手寫版本。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved