前言
✨本博客讲解 蓝桥杯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; }