演算法知識 - 合併排序 merge sort

合併排序 merge sort 介紹與實作原理

合併排序主要是透過 divide 的方式將每一個數列不斷分割成兩數堆(將數列進行分割)，平均時間複雜度為 \(O(n log n\)，是目前時間穩定、效率優質的演算法之一。
也是目前大家會選擇的排序演算法之一。

實作原理如下：

• 以下舉例是由小到大
• 準備一個暫存的數列 temp
• 先不斷進行遞迴，將數列分割成兩個子數列
• 處理程序：
  • 如果不能夠再分割，直接回傳數字
  • 將先前遞迴好的兩子數列，定義 A、B，分別給於這兩個子數列一個指針，定義 start_l、start_r
  • 將 start_l、start_r 指針指定的數字進行比較，如果 start_l 比較小就放入 temp，並將 start_;+1，反之 start_r 比較小就反入 temp，並將 start_r+1，
  • 上面此點主要是將兩個已經排序好的子數列，再依照順序放入 temp 中，因為我們可以知道 A、B 一開始一定是最小的數值，後面都是更大的數值，所以我們可以透過此操作來進行優化
  • 如果已經有一邊的子數列用完，而另一邊沒有用完，則將剩下的另一邊依照順序放入 temp
  • 之後將 temp 的數列放回原本的數列

最後就可以輸出答案！

參考來源

合併排序 by wiki

合併排序 merge sort 程式碼說明與應用

透過程式碼來進行說明相信會更好理解，以下我們示範從小到大排序

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e5;
int num[] = {4,96,1546,13,48,34,77,48,31}; //要排序的數字
int temp[MAXN]; //暫存用
int num_size; //要排序的數字大小


void output(){ //輸出排序
    for(int i = 0 ; i < num_size ; i++)
        cout << num[i] << ' ' ;
    cout << '\n' ;
}

void merge_sort(int L, int R){ //進行合併搜尋
    if(L >= R) return ; //表示沒有子數列，所以 return
    //m 表示兩邊的分割點
    int m=(L+R)/2;
    int start_l = L, end_l = m; //start_l 為指針，end_l 為子數列的長度
    int start_r = m+1, end_r = R; //與上方相同

    merge_sort(start_l, end_l); //將左子數列進行 merge_sort
    merge_sort(start_r, end_r); //與上方相同

    int index = l; //我們用於紀錄 temp 資料放入哪些哪邊
    while(start_l <= end_l && start_r <= end_r) //如果 A、B 兩數列的指針並還沒到子數列的最大長度
        //判斷是 start_l 此指針的數值是否有比 start_r 小，如果有，
        //則將 start_l 指針的值放入 temp，並讓 start_l+1，反之亦同
        //注意：這邊有很多++ 的動作請進行留意
        temp[index++] = num[start_l] < num[start_r] ? num[start_l++] : num[start_r++];

    //如果 A 數列還沒用完，就將 A 數列的值依序放入 temp，判斷的標準則是 start_l 是否已經到 end_l，下方相同
    while(start_l <= end_l) temp[index++] = num[start_l++]; 
    while(start_r <= end_r) temp[index++] = num[start_r++];

    //將這次 merge_sort 好的值放入原本的 num，因為我們是要對 num 進行排序，而非 temp
    for(int i = L; i <= R; i++) num[i] = temp[i]; 
}

int main()
{
    num_size = sizeof(num) / sizeof(num[0]);

    merge_sort(0, num_size-1);
    output(); //輸出答案

    return 0;
}

心得

由於 C++ 已經有很多 sort 套件了，因此我在高中學會後我就再也沒有去複習這些知識。

剛好現在上課有用到那就來複習，順便把它寫出邏輯八！

程式執行結果