文章目录
前言
一、归并排序
二、例题，代码
AcWing 787. 归并排序
本题解析
AC代码
AcWing 788. 逆序对的数量
本题解析
AC代码
三、时间复杂度
前言
本文最初写于 2021 − 06 − 15 2021-06-152021−06−15，于 2022 − 1 − 28 2022-1-282022−1−28 写了另一篇博客：蓝桥杯第七讲–排序【例/习题】，本文对归并排序理解并不深刻，当时为了赶时间写出来的，在博客：蓝桥杯第七讲–排序【例/习题】有很详细的对本文两题的解释，建议直接去读博客：蓝桥杯第七讲–排序【例/习题】
一、归并排序
归并排序模板：
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 k = 0, i = l, j = mid + 1; 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 = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
本模板来自：AcWing算法基础课
二、例题，代码
AcWing 787. 归并排序
本题链接：AcWing 787. 归并排序
本博客提供本题截图：
本题解析
归并排序板子题，直接套模板即可
AC代码
#include <iostream> using namespace std; const int N = 1e5 + 10; int a[N], 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 k = 0, i = l, j = mid + 1; 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 = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); merge_sort(a, 0, n - 1); for (int i = 0; i < n; i ++ ) printf("%d ", a[i]); return 0; }
AcWing 788. 逆序对的数量
本题链接：AcWing 788. 逆序对的数量
本博客提供本题截图：
本题解析
对于数组的第i个和第j个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对。
注意本题会爆int
AC代码
#include <iostream> using namespace std; typedef long long LL; const int N = 1e5 + 10; int a[N], tmp[N]; LL merge_sort(int q[], int l, int r) { if (l >= r) return 0; int mid = l + r >> 1; LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else { res += mid - i + 1; tmp[k ++ ] = q[j ++ ]; } while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; return res; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); cout << merge_sort(a, 0, n - 1) << endl; return 0; }
三、时间复杂度
关于归并排序的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
