AcWing 787. 歸并排序

題目傳送門

一、算法原理

二、執行個體模拟

具體的我們以一組無序數列\(\{14，12，15，13，11，16 \}\)為例分解說明，如下圖所示：

上圖中首先把一個未排序的序列從中間分割成\(2\)部分，再把\(2\)部分分成\(4\)部分，依次分割下去，直到分割成一個一個的資料，再把這些資料兩兩歸并到一起，使之有序，不停的歸并，最後成為一個排好序的序列。

三、代碼模闆

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int q[N];    //原數組
int tmp[N];  //臨時數組

/**
 * 功能：歸并排序
 * @param q 要排序的數組，按位址引用
 * @param l 左下标
 * @param r 右下标
 */
void merge_sort(int q[], int l, int r) {
    //數組空，傳回
    if (l >= r) return;
    //中間位置
    int mid = (l + r) >> 1;
    //遞歸左側
    merge_sort(q, l, mid);  // mid歸前不歸後
    //遞歸右側
    merge_sort(q, mid + 1, r);  //後面是從mid+1開始的

    //在完成歸後，并的過程，就是本輪需要自己處理的合并事情
    int i = l;        //左側出發點
    int j = mid + 1;  //右側出發點
    int k = 0;        //臨時數組下标索引
    //雙指針，周遊兩個子數組，誰小誰進入臨時數組
    while (i <= mid && j <= r)
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    //有剩餘的就全部掃進臨時數組
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    //将tmp數組資料複制回q數組
    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

int main() {
    //讀入優化
    ios::sync_with_stdio(false);
    //輸入
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> q[i];
    //歸并排序
    merge_sort(q, 1, n);  //注意參數為1~n
    //輸出結果
    for (int i = 1; i <= n; i++) printf("%d ", q[i]);
    return 0;
}