iT邦幫忙

2021 iThome 鐵人賽

DAY 22
0
自我挑戰組

每日攝取一點資料結構和演算法系列 第 22

Day22:[排序演算法]Merge sort - 合併排序法

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20210922/20128604Z3TvFsqWQK.jpg
Merge Sort採用分治法(Divide and Conquer)的方式來處理排序的問題,簡單介紹一下分治法執行的步驟如下

  • Divide:先將大問題不斷切割成小問題
  • Conquer:用遞迴的方式處理所有的子問題
  • Combine:將所有的結果合併起來就是最終解答

實作步驟

將陣列不斷分割,分割到只有一個元素為止,再依照大小依序組合起來,流程可參考下圖
https://ithelp.ithome.com.tw/upload/images/20210922/20128604rucdjN7QkO.png

用js實作merge sort

const merge = (arr1, arr2) => {
    const result = [];
    //用雙指針來紀錄比較位置
    let i = 0;
    let j = 0;

    //兩個陣列裡的元素逐一比較大小
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] > arr2[j]) {
            result.push(arr2[j]);
            j++;
        } else {
            result.push(arr1[i]);
            i++;
        }
    }

    //將剩餘的元素放入result
    while (i < arr1.length) {
        result.push(arr1[i]);
        i++;
    }
    while (j < arr2.length) {
        result.push(arr2[j]);
        j++;
    }
    return result;
};

const mergeSort = (arr) => {
    if (arr.length === 1) return arr;
    //找中間點
    let middle = Math.floor(arr.length / 2);
    //將陣列切為左半邊和右半邊
    let left = arr.slice(0, middle);
    let right = arr.slice(middle, arr.length);
    return merge(mergeSort(right), mergeSort(left));
};

mergeSort([8, 3, 6, 7, 2]);

這邊畫流程圖來講解merge這個函式在做的事情

  1. 假設傳入兩個陣列個別是arr1 和arr2 (這兩個必定是已經排序好的陣列)
    https://ithelp.ithome.com.tw/upload/images/20210922/20128604ECQiRGGRBP.png

  2. 第一個while迴圈會搭配雙指針將兩個陣列相互比大小,先取兩個陣列中的第一個來做比較,1比2小所以放入result裡面,然後本來指向1的j指針就要往後移動一格,指向4
    https://ithelp.ithome.com.tw/upload/images/20210922/20128604PqQBfV9RXQ.png

  3. 2與4做比較,2比較小所以放入result中,本來指向2的i指針就要往後移動一格,指向3
    https://ithelp.ithome.com.tw/upload/images/20210922/20128604IRzpkTFL6T.png

  4. 經過不斷的比較會發現i指針已經指到最後一個了,但是j指針還沒到終點,此時第一個while迴圈已經終止,可以發現arr1的已經全部被放進result裡面了,arr2還有兩個
    https://ithelp.ithome.com.tw/upload/images/20210922/20128604soECGvqAqF.png

  5. 因此會執行第三個while迴圈,將arr2剩下的元素放進result,如果今天是arr1有剩餘的元素就會執行第二個while迴圈,最後可以得到一個合併好的陣列並且排序由小到大
    https://ithelp.ithome.com.tw/upload/images/20210922/20128604AUUfssAQj6.png

空間複雜度相較其它排序演算法會比較高,因為會不斷切割生成新的陣列,需要額外的記憶體空間來存放

時間複雜度

  • 在最差的情況下,時間複雜度是O(n log n)
  • 在最佳的情況下,時間複雜度是O(n log n)
  • 在平均情況下,時間複雜度為 O(n log n)

參考資料: divide-and-conquer


上一篇
Day21:[排序演算法]Heap Sort - 堆積排序法
下一篇
Day23:Greedy Algorithm - 貪婪演算法
系列文
每日攝取一點資料結構和演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言