插入排序每次都從已排序序列的尾端往前逐格比較,比較次數偏多。折半插入排序(又稱二分插入排序)把「找位置」這一步換成二分搜尋,比較次數降到 O(log n),雖然整體複雜度仍是 O(n²)(因為搬移元素還是 O(n)),但常數明顯更小。本文用 JavaScript 實作一遍。
JavaScript 沒有內建的 insert,用 slice 切兩段再拼起來是最直覺的做法:
function pushArrayWithIndex(arr, index, value) {
// 把 value 插入 arr 的 index 位置
var temArr = arr.slice(0, index); // 取 index 之前的部分
temArr.push(value); // 放入新元素
return temArr.concat(arr.slice(index)); // 接上 index 之後的部分
}
/* 測試
var arr = [1, 2, 3, 4, 5];
arr = pushArrayWithIndex(arr, 1, 9);
console.log(arr); // [1, 9, 2, 3, 4, 5]
*/
function sortInsert(arr) {
var temArr = []; // 存放已排序的結果
// 在已排序陣列中找出 num 應該插入的位置
function getSortTmpIndex(subArr, num) {
var len = subArr.length;
if (len == 0) return 0; // 空陣列,放在最前面
var cpmIndex = Math.ceil(len / 2); // 中間位置
if (cpmIndex > len - 1) cpmIndex = len - 1;
if (num == subArr[cpmIndex]) {
return cpmIndex; // 剛好相等
}
if (num > subArr[cpmIndex]) {
// 比中間值大,往右半邊找
cpmIndex++;
return cpmIndex + getSortTmpIndex(subArr.slice(cpmIndex), num);
}
// 比中間值小,往左半邊找
return getSortTmpIndex(subArr.slice(0, cpmIndex), num);
}
for (var i in arr) {
var index = getSortTmpIndex(temArr, arr[i]); // 找位置
console.log('index:', index, ' num:', arr[i], ' arr:', temArr);
temArr = pushArrayWithIndex(temArr, index, arr[i]); // 插入
}
return temArr;
}
var arr = [3, 7, 6, 5, 9, 1, 2, 3, 1, 7, 4];
console.log(arr);
arr = sortInsert(arr);
console.log(arr); // [1, 1, 2, 3, 3, 4, 5, 6, 7, 7, 9]
演算法維持一個「已排序區」temArr,每次從原陣列取一個元素,用二分搜尋在已排序區裡找到插入點,再插入。以 [3, 7, 6] 為例:
temArr 為空,插入位置 0 → [3][3, 7][3, 6, 7]遞迴的每一層都在做同一件事:拿中間值比大小,然後把範圍砍半,直到範圍縮成 0 或找到相等值。
temArr 且遞迴中不斷 slice,空間 O(n);標準實作會在原陣列上搬移,空間只需 O(1)。1、遞迴改迴圈。這裡用遞迴說明思路,但每次遞迴都 slice 建立新陣列, overhead 不小。正式實作用兩個指標 low / high 的 while 迴圈即可:
function binarySearchInsert(arr, num, end) {
var low = 0, high = end;
while (low < high) {
var mid = Math.floor((low + high) / 2);
if (num <= arr[mid]) { high = mid; } // 用 <= 保證穩定性
else { low = mid + 1; }
}
return low;
}
function binaryInsertionSort(arr) {
for (var i = 1; i < arr.length; i++) {
var num = arr[i];
var pos = binarySearchInsert(arr, num, i);
// 把 i 位置的元素搬到 pos,中間元素整體往後一格
for (var j = i; j > pos; j--) {
arr[j] = arr[j - 1];
}
arr[pos] = num;
}
return arr;
}
2、用 for 迴圈取代 for...in。遍歷陣列請用傳統索引迴圈,for...in 會枚舉原型上的屬性,也可能顛倒順序。
3、什麼時候用它?資料量小、或資料接近已排序時,插入排序非常快,實務上常被當成快速排序、合併排序的遞迴底層(區間小於某個門檻就切成插入排序)。若只是要排序一般陣列,直接用 arr.sort((a,b) => a-b) 就好,引擎內部已經針對型別做了最佳化。