Merge sort 合併排序法

Merge sort 合併排序法
Categories:
Tags:

複雜度

複雜度 Big O
最差時間複雜度 Worst-case time complexity Big O(n log n)
平均時間複雜度 Average-case time complexity Big theta (n log n)
最佳時間複雜度 Best-case time complexity Big omega (n log n)
空間複雜度 Space complexity Big O (n)

演算法

1. 建立儲存最後排序結果陣列

會持續比較陣列數字的大小，然後將找到的最小數字儲存在結果陣列

2. 比較兩個最小的排序陣列

將數字陣列不斷地切割，直到切割到剩下最後一個數字陣列，然後往上遞迴比較

持續比較兩個已排序陣列，然後比較兩個排序陣列中最小的數字，加入到最後的排序結果陣列

3. 加入剩餘尚未比較陣列

兩陣列比較完，避免其中一個陣列比完了，但另外一個陣列還有數字還沒比完

因為兩個都是已排序的陣列，所以剩餘陣列的數字一定是比已加入的數字大

所以就直接將剩餘數字的陣列數字，依序地加入到結果陣列中

4. 陣列往上遞迴合併

比較好的新陣列，也會是排序好的陣列，往上回傳後，持續和其他切割的陣列做比較

最後持續這個步驟，會得到一個完整排序後的陣列

Merge sort 合併排序法

程式

JavaScript

function merge(numberList1, numberList2) {
    // 最後比較結果陣列
    var finalOrderNumberList = [];
    // 陣列 1 比較數量
    var numberList1Counter = 0;
    // 陣列 2 比較數量
    var numberList2Counter = 0;
    // 比較兩個數字陣列，直到其中一個陣列比較完畢
    while (numberList1Counter < numberList1.length && numberList2Counter < numberList2.length) {
        if (numberList1[numberList1Counter] < numberList2[numberList2Counter]) {
            // 「陣列 1 的數字」比「陣列 2 的數字」小，將「陣列 1 的數字」加到結果陣列
            finalOrderNumberList.push(numberList1[numberList1Counter]);
            // 陣列 1 繼續比較下一個
            numberList1Counter++;
        }
        else {
            // 「陣列 2 的數字」比「陣列 1 的數字」小，將「陣列 2 的數字」加到結果陣列
            finalOrderNumberList.push(numberList2[numberList2Counter]);
            // 陣列 2 繼續比較下一個
            numberList2Counter++;
        }
    }
    // 處理剩餘數字
    while (numberList1Counter < numberList1.length) {
        // 如果「陣列 1 的數字」還有剩，將所有陣列 1 數字加到結果陣列
        finalOrderNumberList.push(numberList1[numberList1Counter]);
        numberList1Counter++;
    }
    while (numberList2Counter < numberList2.length) {
        // 如果「陣列 2 的數字」還有剩，將所有陣列 2 數字加到結果陣列
        finalOrderNumberList.push(numberList2[numberList2Counter]);
        numberList2Counter++;
    }
    return finalOrderNumberList;
}
function mergeSort(sortNumberList) {
    if (sortNumberList.length <= 1) {
        // 如果只有 1 個數字，不用排序，直接回傳
        return sortNumberList;
    }
    //  取得中間切割點
    var middlePointer = Math.floor(sortNumberList.length / 2);
    // 計算切割點左方排序
    var leftPartitionOrderNumberList = mergeSort(sortNumberList.slice(0, middlePointer));
    // 計算切割點右方排序
    var rightPartitionOrderNumberList = mergeSort(sortNumberList.slice(middlePointer));
    // 合併兩個排序陣列
    return merge(leftPartitionOrderNumberList, rightPartitionOrderNumberList);
}
console.log(mergeSort([70, 50, 30, 10, 20, 40, 60]));

TypeScript

function merge(numberList1: number[], numberList2: number[]): number[] {
    // 最後比較結果陣列
    let finalOrderNumberList = [];
    // 陣列 1 比較數量
    let numberList1Counter = 0;
    // 陣列 2 比較數量
    let numberList2Counter = 0;

    // 比較兩個數字陣列，直到其中一個陣列比較完畢
    while (numberList1Counter < numberList1.length && numberList2Counter < numberList2.length) {
        if (numberList1[numberList1Counter] < numberList2[numberList2Counter]) {
            // 「陣列 1 的數字」比「陣列 2 的數字」小，將「陣列 1 的數字」加到結果陣列
            finalOrderNumberList.push(numberList1[numberList1Counter]);
            // 陣列 1 繼續比較下一個
            numberList1Counter++;
        } else {
            // 「陣列 2 的數字」比「陣列 1 的數字」小，將「陣列 2 的數字」加到結果陣列
            finalOrderNumberList.push(numberList2[numberList2Counter]);
            // 陣列 2 繼續比較下一個
            numberList2Counter++;
        }
    }

    // 處理剩餘數字
    while (numberList1Counter < numberList1.length) {
        // 如果「陣列 1 的數字」還有剩，將所有陣列 1 數字加到結果陣列
        finalOrderNumberList.push(numberList1[numberList1Counter]);
        numberList1Counter++;
    }
    while (numberList2Counter < numberList2.length) {
        // 如果「陣列 2 的數字」還有剩，將所有陣列 2 數字加到結果陣列
        finalOrderNumberList.push(numberList2[numberList2Counter]);
        numberList2Counter++;
    }

    return finalOrderNumberList;
}

function mergeSort(sortNumberList: number[]): number[] {
    if (sortNumberList.length <= 1){
        // 如果只有 1 個數字，不用排序，直接回傳
        return sortNumberList;
    }

    //  取得中間切割點
    let middlePointer = Math.floor(sortNumberList.length / 2);
    // 計算切割點左方排序
    let leftPartitionOrderNumberList = mergeSort(sortNumberList.slice(0, middlePointer));
    // 計算切割點右方排序
    let rightPartitionOrderNumberList = mergeSort(sortNumberList.slice(middlePointer));

    // 合併兩個排序陣列
    return merge(leftPartitionOrderNumberList, rightPartitionOrderNumberList);
}

console.log(mergeSort([70, 50, 30, 10, 20, 40, 60]));

參考資料