DIV CSS 佈局教程網

JavaScript 排序演算法三講:希爾排序、快速排序與歸並排序
編輯:關於JavaScript     

以下範例一律以 var a = [4,2,6,3,1,9,5,7,8,0] 為輸入,方便對照每一輪的中間狀態。

一、希爾排序 Shell Sort

希爾排序是插入排序的改良版。插入排序每次只跟相鄰的元素比較,資料稍微大她一點就得一格一格往后挪;希爾排序的做法是先跳著比——用一個 gap 把陣列切成若干子序列,各自做插入排序,然後逐步縮小 gap,最後以 gap=1 收尾。這樣一來,元素在早期的「粗調」階段就能長距離移動,最後一輪的插入排序幾乎不用怎麼搬。

function shellsort(arr) {
    var i, k, j, len = arr.length,
        gap = Math.ceil(len / 2), temp;

    while (gap > 0) {
        for (k = 0; k < gap; k++) {
            // 對間隔為 gap 的子序列做插入排序
            for (i = k + gap; i < len; i = i + gap) {
                temp = arr[i];
                for (j = i - gap; j > -1; j = j - gap) {
                    if (arr[j] > temp) {
                        arr[j + gap] = arr[j];   // 往後挪
                    } else {
                        break;
                    }
                }
                arr[j + gap] = temp;             // 插入
            }
        }
        gap = parseInt(gap / 2);                 // 縮小間隔
    }
    return arr;
}

執行過程(節錄):

gap = 5: [4,9] [2,5] [6,7] [3,8] [1,0] 五組各自排序
        → [4,2,6,3,0,9,5,7,8,1]

gap = 2: [4,6,0,5,8] 與 [2,3,9,7,1] 兩組排序
        → [0,1,4,2,5,3,6,7,8,9]

gap = 1: 一般插入排序收尾
        → [0,1,2,3,4,5,6,7,8,9]

可以明顯看到 gap=5 那輪,索引 0 和 5(4 與 9)、1 和 6(2 與 5)……各自成組比較。等到 gap=1 的最後一輪,陣列已經大致有序,插入排序要搬的次數非常少——這正是希爾排序比樸素插入排序快的原因。

二、快速排序 Quick Sort

分治法(divide and conquer)的代表。任選一個基準值(pivot),把數組分成「比它小」和「比它大」兩堆,然後對這兩堆分別遞迴同樣的動作,直到每堆只剩一個元素。通常以第一個元素當基準。

function quickSort(arr) {
    var len = arr.length, leftArr = [], rightArr = [], tag;
    if (len < 2) { return arr; }        // 遞迴終止條件

    tag = arr[0];
    for (var i = 1; i < len; i++) {
        if (arr[i] <= tag) {
            leftArr.push(arr[i]);
        } else {
            rightArr.push(arr[i]);
        }
    }
    return quickSort(leftArr).concat(tag, quickSort(rightArr));
}

這個寫法簡潔好懂,但它不是原地排序——每次都建立新陣列,額外使用了 O(n) 的空間。實務上的快速排序會用雙指標在原陣列內做分割(partition),空間才能壓到 O(log n)。另外,「固定取第一個元素當 pivot」在遇到已排序或接近已排序的資料時會退化成 O(n²),實作時通常改成隨機取或三數取中。

三、歸並排序 Merge Sort

思路是「先合併兩個已排序的序列」。做法從最小的單位(單一元素)開始,兩兩合併成有序的小段,再把这些有序小段继续两两合併,最後整組就有序了。

先寫合併兩個有序陣列的方法

function subSort(arr1, arr2) {
    var bArr1 = arr1.slice(), bArr2 = arr2.slice(), arr3 = [];

    // 兩邊都還有元素時,每次取較小的那個
    while (bArr1.length != 0 || bArr2.length != 0) {
        if (bArr1.length == 0) {
            arr3 = arr3.concat(bArr2);
            bArr2.length = 0;
        } else if (bArr2.length == 0) {
            arr3 = arr3.concat(bArr1);
            bArr1.length = 0;
        } else {
            if (bArr1[0] <= bArr2[0]) {
                arr3.push(bArr1[0]);
                bArr1.shift();
            } else {
                arr3.push(bArr2[0]);
                bArr2.shift();
            }
        }
    }
    return arr3;
}

注意它預設輸入的兩個陣列已經各自有序,這正是歸並排序能達到 O(n log n) 的關鍵——合併兩個有序序列本身是線性的。

主流程

function mergeSort(arr) {
    var len = arr.length, arrleft = [], arrright = [],
        gap = 1, maxgap = len - 1, gapArr = [], glen, n;

    // 先算出會用到的所有 gap:1, 2, 4, 8 ...
    while (gap < maxgap) {
        gap = Math.pow(2, n);
        if (gap <= maxgap) { gapArr.push(gap); }
        n++;
    }

    glen = gapArr.length;
    for (var i = 0; i < glen; i++) {
        gap = gapArr[i];
        for (var j = 0; j < len; j = j + gap * 2) {
            arrleft  = arr.slice(j, j + gap);
            arrright = arr.slice(j + gap, j + gap * 2);
            arr = arr.slice(0, j).concat(subSort(arrleft, arrright), arr.slice(j + gap * 2));
        }
    }
    return arr;
}

執行過程:

第一輪 gap=1:合併 [4,2] [6,3] [1,9] [5,7] [8,0]
             → [2,4,3,6,1,9,5,7,0,8]

第二輪 gap=2:合併 [2,4]+[3,6]  [1,9]+[5,7]  [0,8]+[]
             → [2,3,4,6,1,5,7,9,0,8]

第三輪 gap=4:合併 [2,3,4,6]+[1,5,7,9]  [0,8]+[]
             → [1,2,3,4,5,6,7,9,0,8]

第四輪 gap=8:合併 [1,2,3,4,5,6,7,9]+[0,8]
             → [0,1,2,3,4,5,6,7,8,9]

可以清楚看到合併單位依序是 1 → 2 → 4 → 8,每輪把相鄰的兩個有序段拼成一個更大的有序段。

三者該怎麼選

快速排序在一般情況下是平均表現最好的,因為常數因子小、快取友善;缺點是穩定性差、最壞情況 O(n²)。

歸並排序時間穩定保證 O(n log n),而且是穩定排序(相等元素的相對順序不變),因此適合排序物件或需要保留原順序的場景;代價是需要 O(n) 的額外空間。外部排序(資料大到記憶體放不下)也只能用它。

希爾排序是插入排序的改良,實作簡單、原地排序、空間 O(1),在中等規模或記憶體受限的環境下有它的位置,但一般用途已多半被前兩者取代。

實務上一個常見的折衷是混合排序:大陣列用快速排序遞迴分割,當子陣列小到某個門檻(例如 16 個元素)就切成插入排序——因為小陣列下插入排序的常數反而更小。多數標準函式庫都是這樣做的。

最後提醒:以上範例為教學目的而寫,重在展示每一輪的中間狀態。真正在專案裡排序,請直接用 Array.prototype.sort(),它已經過高度優化。

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