AcWing 787. 归并排序 解题思路及代码

先贴个题目：

以及原题链接：787. 归并排序 - AcWing题库https://www.acwing.com/problem/content/789/纯板子题，先贴代码吧，根据代码讲思路：

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N], tmp[N];

void gsort(int str[],int left, int right)
{
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    gsort(str,left, mid);
    gsort(str,mid + 1, right);
    int x = left, y = mid + 1, z = 0;
    while (x <= mid && y <= right)
    {
        if (str[x] <= str[y])
            tmp[z++] = str[x++];
        else
            tmp[z++] = str[y++];
    }
    while (x <= mid)
        tmp[z++] = str[x++];
    while (y <= right)
        tmp[z++] = str[y++];
    for (int i = left, j = 0; i <= right; ++i, ++j)
        str[i] = tmp[j];
    return;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    gsort(a,0, n-1);
    for (int i = 0; i < n; ++i)
        cout << a[i] << " ";
    return 0;
}

 每次把要分的数组分成两部分，然后因为递归到数组中只存在一个数，然后是两个数，以此类推，我们待会再来讲排序的原理，先默认他就是有序的，那利用两段有序数组，实现整个合并大数组的有序即可。至于原理，就是创建一个临时的数组，然后如果左边数字小于于等于右边数字，就让左边数字进入到临时数组中， 然后记录的下标都右移一格，如此就能归并了。

by————2024.2.28刷题记录