前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第七讲：排序【例/习题】
本博客是讲排序这一专题，在蓝桥杯中，我们常用的就是快排和归并排序，而对于快排而言，我们一般习惯调用sort函数，读者可以看博文：STL—algorithm（2），如果你是用的 C语言，那么对于快排而言可以手写快排，见博文：快速排序。
💖有关归并排序模板见博文：归并排序算法模板
本篇博客所包含习题有：
👊归并排序
👊逆序对的数量
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
归并排序
题目要求
题目描述：
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式：
输出格式：
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围：
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
思路分析
代码
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 100010; int n; int a[N], backup[N]; void merge_sort(int l, int r) { if (l >= r) return; int mid = l + r >> 1; merge_sort(l, mid); merge_sort(mid + 1, r); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (a[i] < a[j]) backup[k ++ ] = a[i ++ ]; else backup[k ++ ] = a[j ++ ]; } while (i <= mid) backup[k ++ ] = a[i ++ ]; while (j <= r) backup[k ++ ] = a[j ++ ]; for (int i = l, j = 0; i <= r; i ++, j ++ ) a[i] = backup[j]; } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); merge_sort(1, n); for (int i = 1; i <= n; i ++ ) printf("%d ", a[i]); return 0; }
逆序对的数量
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数，表示逆序对的个数。
数据范围：
输入样例：
6
2 3 4 5 6 1
输出样例：
5
思路分析
我们在上一题的模板基础上让归并排序具有一些特殊含义，比如我们的归并排序可以返回其中逆序对的个数，我们把一个大区间分成了两个子区间，然后现在，我们的逆序对就会分为如下三种情况：
- 左子区间上的两个数构成逆序对
- 右子区间上的两个数构成逆序对
- 左字区间的一个数和右子区间的一个数构成逆序对
对于 1 和 2 而言，因为我们现在给归并排序赋予了返回区间上逆序对的个数这个含义，所以，处理 1 , 2 如下代码可解决：
res = merge_sort(l, mid) + merge_sort(mid + 1, r);
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010; int n; int a[N], backup[N]; LL res; LL merge_sort(int l, int r) { if (l >= r) return 0; int mid = l + r >> 1; res = (LL)merge_sort(l, mid) + merge_sort(mid + 1, r); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (a[i] <= a[j]) backup[k ++ ] = a[i ++ ]; else //因为j肯定是大于i的,所以证明此时是一个逆序对 { backup[k ++ ] = a[j ++ ]; res += mid - i + 1; } } while (i <= mid) backup[k ++ ] = a[i ++ ]; while (j <= r) backup[k ++ ] = a[j ++ ]; for (int i = l, j = 0; i <= r; i ++, j ++ ) a[i] = backup[j]; return res; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); printf("%lld\n", merge_sort(1, n)); return 0; }
