Merge Sort(合併排序法) 實作 ^^

作者：パっパっパスタ│2019-04-01 17:01:30│巴幣：56│人氣：1558

昨天看別人寫的程式碼看了3個小時+問別人問題才搞懂這些程式碼在寫的內容

今天靠著昨天練習的記憶寫出來的

C++:

#include <iostream>

using namespace std;

void Merge(int arr[], int l, int m, int r) //開始合併
{
    int L_size, R_size, i, j, k; //L跟R陣列的大小、i,j,k為指針
    L_size = m - l + 1;          //+1 是因為一開始會有0-0的可能性
    R_size = r - m;
    int L[L_size], R[R_size]; //宣告兩個新陣列分別為左陣列跟右陣列，沒有內容值

    for (i = 0; i < L_size; i++) //把原陣列的值塞進剛定義的L跟R陣列
    {
        L[i] = arr[l + i];
    }

    for (j = 0; j < R_size; j++)
    {
        R[j] = arr[m + 1 + j];
    }

    i = 0;
    j = 0;
    k = l;
    while (i < L_size && j < R_size) //當其中一個比較完就跳出這個陣列
    {
        if (L[i] <= R[j]) //比較小的丟進arr[]
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < L_size) //剩餘的部分全塞進剩下的arr[]
    {
        arr[k] = L[i];
        k++;
        i++;
    }

    while (j < R_size)
    {
        arr[k] = R[j];
        k++;
        j++;
    }
}

void MergeSort(int arr[], int l, int r) //運用遞迴去 divide 陣列，當陣列只有一格時就 return
{
    if (l < r)
    {
        int mid = (l + r - 1) / 2;
        MergeSort(arr, l, mid);
        MergeSort(arr, mid + 1, r);
        Merge(arr, l, mid, r);
    }
}

int main()
{
    int arr[] = {2, 4, 6, 8, 1, 3, 5, 7};
    int len = sizeof(arr) / sizeof(arr[0]);
    int l = 0, r = len - 1;
    cout << "Before Merge: " << endl; //Merge前
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    MergeSort(arr, l, r); //進行 Merge 去切割陣列並排序

    cout << "After Merge: " << endl; //Merge 後
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    system("pause");
}

實作的觀念是看這兩個影片搞懂的