DIV CSS 佈局教程網

JavaScript 折半插入排序演算法實作與解析
編輯:關於JavaScript     

插入排序每次都從已排序序列的尾端往前逐格比較,比較次數偏多。折半插入排序(又稱二分插入排序)把「找位置」這一步換成二分搜尋,比較次數降到 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] 為例:

  1. 取 3,temArr 為空,插入位置 0 → [3]
  2. 取 7,與 3 比較後放右邊 → [3, 7]
  3. 取 6,中間位置是 7,6 比它小往左找,與 3 比較後放右邊 → [3, 6, 7]

遞迴的每一層都在做同一件事:拿中間值比大小,然後把範圍砍半,直到範圍縮成 0 或找到相等值。

四、複雜度分析

  • 比較次數:每個元素 O(log n),整體 O(n log n)。
  • 搬移次數:插入時要整體後移,最壞情況 O(n²),這部分沒有改善。
  • 整體時間複雜度:仍是 O(n²)。
  • 空間複雜度:這個版本额外建立 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) 就好,引擎內部已經針對型別做了最佳化。

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