合併排序(Merge Sort)


合併排序(merge sort)

進階排序演算法的一種,以「分治法(divide and conquer)」實現,即將大問題拆成多個小問題,一一處理小問題後,就能解決大問題。

圖示

以下可用圖示理解「merge sort」如何以「divide and conquer」方式,將原陣列 [5,4,6,9,8,1,3,2] 由小到大排列。

上半部的「divide」將陣列的長度從 8 縮減為 1,再一一比較每個小陣列中值的大小,並進行排列。

下半部「conquer」排序過程

在陣列長度為 1 時,這八個陣列都已經排序好:

將已經排序好、長度為 1 的陣列兩兩比較,數值較小者先取,組合成已經排序好、長度為 2 的陣列:


排序好長度為 2 的陣列如下:

接著將已經排序好、長度為 2 的陣列兩兩比較,數值小者先取,組合成已經排序好、長度為 4 的陣列:




排序好長度為 4 的陣列如下:

最後將已經排序好、長度為 4 的陣列兩兩比較,數值小者先取,組合成已經排序好、長度為 8 的陣列:









整個陣列最終排序結果如下:


偽代碼&說明

「合併排序」的程式碼分為兩個部分,包含 MERGE() 將兩個已排序的小陣列合併成排序好的大陣列,還有 MERGE-SORT() 實現「分而治之」。

下列偽代碼及程式碼皆以「將陣列由小到大排序」為目標:

第一部分:MERGE()

輸入兩個已經排序好的小陣列「arr1」與「arr2」,透過指標「i」與「j」逐一比較兩陣列中的值,較小者優先放入新建的空陣列「result」。

若其中一陣列全部比較完後,另一陣列仍有未放入「result」的值,因為小陣列的資料都已經排序過,可以直接把小陣列中剩下的值直接搬運到「result」當中。

第二部分:MERGE-SORT()

先取陣列中間值「middle」,接著用「slice()」將陣列分為左右兩邊,直到陣列長度為 1 為止;接著透過遞迴搭配「MERGE()」函數,將小陣列不斷合併、排序,直到輸入的「arr」每筆資料都被排序過為止。

合併排序透過兩個小陣列各自的指標逐一比較、排序,同樣大小的值會按照原順序排在最終結果中,屬於「穩定排序(stable sort)」。


程式碼範例(JavaScript)

//第一部份
function merge(arr1, arr2){
    //製作空陣列result&指標i、j
    let result = [];
    let i = 0;
    let j = 0;

    //將兩陣列合併,並由小到大一一放進result
    while(i < arr1.length && j < arr2.length){
        if(arr1[i] < arr2[j]){
            result.push(arr1[i]);
            i++;
        } else {
            result.push(arr2[j]);
            j++;
        }
    }

    //若arr2比arr1先清空,則將arr1剩下的資料直接搬到result
    while(i < arr1.length){
        result.push(arr1[i]);
        i++;
    }

    //若arr1比arr2先清空,則將arr1剩下的資料直接搬到result
    while(j < arr2.length){
        result.push(arr2[j]);
        j++;
    }

    return result;
}

//第二部分
function mergeSort(arr){
    //遞迴終止條件:arr長度被切為1時
    if(arr.length === 1){
        return arr;
    } else {
        //透過遞迴,先將arr不斷分兩半,再用MERGE()將切小的陣列不斷合併、排序

        //用slice把陣列切兩半,slice括弧內的開始處有包含、結束處不包含
        let middle = Math.floor(arr.length / 2); 
        let left = arr.slice(0, middle); //做一個0到middle-1的小陣列
        let right = arr.slice(middle,arr.length); //做一個middle到arr.length的小陣列

        //用遞迴實現「分而治之」
        return merge(mergeSort(left), mergeSort(right));
        /*
        1. 首先執行括號內的mergeSort:
        左半邊小陣列跟右半邊小陣列都持續對半切,直到所有陣列長度變成1為止,就會到上面的if條件判斷區,回傳arr

        2. mergeSort全部跑完後,接著執行外面的merge:
        將陣列一一用merge比較、合併,持續回傳已經排序好的小陣列,直到整個陣列都被merge為止 
        */
    }
}

時間複雜度

不論最差、最佳或平均情況,皆為 O(n·log n)。

現假設原陣列長度為 n,在逐次分割至長度為 1 的陣列之過程中,每分割一次長度都減半,圖示如下:

由上圖可觀察「分割次數」與「陣列長度」之關係,結果如下表,表中最右方以對數形式呈現的「分割次數」相等於最左方以正整數形式呈現「分割次數」的值:

由右方綠色表格最下方的結論可知:若要將原長度為 n 的陣列切到長度剩下 1,共需要分割 (log₂ n) 次,過程中的每層又有 n 筆資料要處理,因此分割過程的時間複雜度為 O(n·log₂ n)。

同樣地,從長度為 1 的陣列合併回長度為 n 的陣列也會有 (log₂ n) 層,而在每層的小陣列中,這 n 筆資料全都要排序、比較一次,因此合併過程的時間複雜度也是 O(n·log₂ n)。

分割的時間複雜度為 O(n·log₂ n)、合併的時間複雜度同為 O(n·log₂ n),因此總時間複雜度為 O(2n·log₂ n)=O(n·log n)。


空間複雜度

O(n):由於合併排序非屬「原地演算法(in-place algorithm)」,在分割及合併的過程中,需額外 O(n) 的空間儲存小陣列,遞迴過程另需要 O(log n),兩者加總取較大者:O(n)+O(log n)=O(n)。

#演算法 #合併排序







你可能感興趣的文章

OOP - 7 關於封裝

OOP - 7 關於封裝

C# 檔案相關應用

C# 檔案相關應用

[進階 js 05] hoisting(提升)

[進階 js 05] hoisting(提升)






留言討論