题目描述

归并排序

三步:

1. 把数组分成两半，归并两边。

2. 合并两个排序好的数组到tmp中

3. 把tmp复制到原来数组中。

边界为只有一个数组时不需要排序，直接return

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int tmp[N];
void merge_sort(int q[], int l, int r) {
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int i = l, j = mid + 1, 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++];
    for(i = 0, j = l; i < k; i++, j++) {
        q[j] = tmp[i];
    }
    return;
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> q[i];
    merge_sort(q, 0, n - 1);
    for(int i = 0; i < n; i++) cout << q[i] << " ";
    puts("");
}