信息奥赛｜归并排序
知识点概览 🚀
- 归并排序の简单介绍
- 归并排序の经典应用
知识点详解 🎥
简单介绍 🎯
归并排序 是分治算法的典型应用之一，也是经典的排序算法之一，其时间复杂度可达到 $O(nlogn)$
归并排序の编程框架 ☘️
归并排序の编程框架
mergesort(int l,int r){
if(l>=r) return; //返回条件
//二分，递归调用，先把两个子序列分别排好
int mid = (l+r)/2;
mergesort(l,mid);
mergesort(mid+1,r);
//将两个有序的子序列合并
1.设定哨兵p1,p2，两个子序列元素不断比较，放入临时数组t中
2.检查哨兵p1是否到末尾，将剩余元素依次放入t中
3.检查哨兵p2是否到末尾，将剩余元素依次放入t中
4.将临时数组t中的元素全部放入原序列中
}对比 快速排序の编程框架
quicksort(int l,int r){
if(l>=r) return; //返回条件
//快速排序每一趟流程
1.选定当前序列的基准数(pivot)
2.哨兵出动，交换序列值，直到找到基准点(两哨兵交汇处)
3.将基准数归位至基准点(pivot_position)
//二分，递归调用
quicksort(l,pivot_position);
quicksort(pivot_position+1,r);
}可以看到，两者的共同点是 都有递归调用的过程，不同点是 递归调用的位置不同。快速排序 是先完成一趟排序，然后将序列二分；归并排序 则是先将序列二分，再将排序后的两个子序列合并。
虽然两者的编程框架看起来有些相似，但 实际的编程难度，快速排序会更难一些。
快速排序的难度提升，并不是指思想上的难度，而是快速排序在编程时，需要考虑的编程细节，如「等号条件」等较为繁琐。在快速排序的编程过程中，很容易出现「漏掉一个等号，排序就失败」的情况。
归并排序の代码模版 🧑🏻💻
void mergesort(int l, int r) {
// 归并排序递归退出条件
if (l >= r) return;
// 二分，递归调用，先把两个子序列分别排好
int mid = l + r >> 1;
mergesort(l, mid);
mergesort(mid + 1, r);
// 此时两个子数组已完成排序，接下来将两个子数组合并
int lp = l, rp = mid + 1; // 设置两个子数组指针lp, rp
int tp = l; // 设置临时数组t指针 tp(tmppoint)
while (lp <= mid && rp <= r) { // 比较过程中合并
if (a[lp] <= a[rp]) {
t[tp++] = a[lp++];
} else {
t[tp++] = a[rp++];
}
}
//若子数组指针未达到子数组尾部，将当前子数组剩余元素全部添加至临时数组
while (lp <= mid) t[tp++] = a[lp++];
while (rp <= r) t[tp++] = a[rp++];
//拷贝临时数组元素至数组a
for (int i = l; i <= r; ++i) a[i] = t[i];
}时间复杂度计算 ⏰
归并排序的时间复杂度分析基于「分治」策略，时间复杂度分析如下：
- 分解：归并排序首先将数组分成两半。这个分解的操作是常数时间复杂度，即 $O(1)$。
- 解决：归并排序递归地对两个小数组进行排序。如果原数组的长度为 $n$，那么两个小数组的长度分别为 $n/2$。因此，时间复杂度为 $2$ 乘以对 $n/2$ 大小数组的排序。
- 合并：将两个已排序的子数组合并成一个有序数组。合并过程的时间复杂度是线性的，即 $O(n)$。
对于整个归并排序算法，我们可以得到递推关系：
$T(n)=2T(n/2)+O(n)$
求解上述递推关系:
$T(n)=2T(n/2)+O(n)=2*(2T(n/4)+O(\frac{n}{2}))+O(n)=…=2^kT(\frac{n}{2^k})+kn$
又 $2^k = n$ ，则 $k = log_2^n$
代入得：$T(n)=2^kT(\frac{n}{2^k})+kn=nT(1) + nlog_2^n$
所以可以得到归并排序的时间复杂度为：
$T(n)=O(nlogn)$
经典应用之统计逆序对个数 🛠
暴力法 🏄🏻
首先，暴力枚举的方法非常容易想到，实现起来也非常简单，只需编写 双重循环，一重循环用于遍历当前数组i → [1,n]，另一重循环遍历 j → [i + 1,n]，当 a[j] < a[i] 时，逆序对数量 + 1 即可。
时间复杂度为：$O(n^2)$
#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main() {
int n, cnt = 0;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i < n; ++i) { //暴力枚举
for (int j = i + 1; j <= n; ++j) {
if (a[j] < a[i])
cnt++;
}
}
cout << cnt << endl;
return 0;
}归并排序法统计 🏄🏻
在暴力枚举中，对于 a[i] 来说， a[i+1],..a[n] 是无序的，所以需要逐个比较。
但假如按照 归并排序 的思想将原数组分成 a[1],.. a[k]，a[k+1],... a[n]，并且各自升序排列，此时再统计两个序列的逆序对就会方便很多。
以数组 6 1 8 7 3 5 2 为例，将其划分为 6 1 8 7 和 3 5 2
- 对于
6 1 8 7中的6来说，无论3 5 2怎么排列，6 3、6 2、6 5始终为逆序对。 - 对于
6 1 8 7中的1来说，无论3 5 2怎么排列，始终没有逆序对。 - 对于
6 1 8 7中的8来说，无论3 5 2怎么排列，8 3、8 2、8 5始终为逆序对。 - 对于
6 1 8 7中的7来说，无论3 5 2怎么排列，7 3、7 2、7 5始终为逆序对。
在保证 升序排列不会改变两个序列外部逆序对个数 的前提下（有同学可能会有疑问，那 6 1 7 8 内部的逆序对，不是因为排序后被打乱了吗？不要急，我们等会来看这个问题），我们按照归并排序的方法，设置双指针不断比较 1 6 7 8 和 2 3 5：
- 当比较到 $a[1]=1 < a[4]=2$ 时，由于
2 3 5升序，1 2不是逆序对，则1 3、1 5不可能是逆序对，无需像暴力法那样，再将1和3 5比较。按照归并排序思路，把 $a[1]$ 放入临时数组t中。 - 当比较到 $a[2]=6 > a[5]=2$ 时，由于
1 6 7 8升序，所以7 2、8 2一定是符合条件的逆序对，共有4 - 2 + 1（a[4] = 8，a[2] = 6）对以 $2$ 为第二个元素的逆序对。按照归并排序思路，把 $a[5]$ 放入临时数组t中。 - 同理，比较到 $a[2]=6 > a[6]=3$ 时，由于
1 6 7 8升序，所以7 3、8 3一定是符合条件的逆序对，共有4 - 2 + 1（a[4] = 8，a[2] = 6）对以 $3$ 为第二个元素的逆序对。按照归并排序思路，把 $a[6]$ 放入临时数组t中。 - 同理，比较到 $a[2] = 6 > a[7] = 5$ 时，由于
1 6 7 8升序，所以7 5、8 5一定是符合条件的逆序对，共有4 - 2 + 1（a[4] = 8，a[2] = 6）对以 $3$ 为第二个元素的逆序对。按照归并排序思路，把 $a[7]$ 放入临时数组t中。
此时双指针遍历完第二个序列，比较停止，按照归并排序思路，把第一个序列的剩余元素 $a[2],a[3],a[4]$ 放入临时数组t中。
也就是说，按照这种方法，我们成功统计了 6 1 7 8 和 3 5 2 的逆序对个数，且复杂度为 $O(n)$。🎉
但是对于一个完整的序列 6 1 8 7 3 5 2 ，还有各自内部的逆序对个数需要统计，即 6 1 8 7 内部的逆序对， 3 5 2 内部的逆序对。
但是我们突然发现，这两个问题和原来的问题一样，只是规模却更小了。
6 1 8 7内部的逆序对，就是6 1、8 7的外部逆序对 +6 1内部逆序对 +8 7内部逆序对- 当执行到
6 1时，程序会统计61的外部逆序对 +6内部逆序对 +1内部逆序对 = 1 + 0 + 0 - 当执行到
8 7时，程序会统计87的外部逆序对 +8内部逆序对 +7内部逆序对 = 1 + 0 + 0
- 当执行到
3 5 2同理
也就是说，按照归并排序的思想，我们可以通过递归调用，一步步把问题规模缩小，就可以求解 6 1 8 7 和 3 5 2 内部的逆序对个数。
这样以来，我们统计的外部逆序对个数 + 内部逆序对个数，就是总的逆序对个数。
且时间复杂度与归并排序一致，为 $O(nlogn)$ 🎉
完整程序如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int n, a[N], t[N];
ll cnt; //逆序对的数量最多约为n^2，爆int
// 归并排序统计逆序对数量
void InversionCount(int l, int r) {
if (l >= r) return;
//归并排序递归调用
int mid = (l + r) / 2;
InversionCount(l, mid);
InversionCount(mid + 1, r);
//对已经有序的两个序列求逆序对数量
int p1 = l, p2 = mid + 1, p3 = l;
while (p1 <= mid && p2 <= r) {
if (a[p1] <= a[p2]) {
t[p3++] = a[p1++];
} else {
t[p3++] = a[p2++];
cnt = cnt + (mid - p1 + 1); //核心代码
}
}
while (p1 <= mid) t[p3++] = a[p1++];
while (p2 <= r) t[p3++] = a[p2++];
for (int i = l; i <= r; ++i) a[i] = t[i];
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 读入数据
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
// 归并排序统计逆序对数量
InversionCount(1, n);
cout << cnt << endl;
return 0;
}时间对比 ⏰
测试数据：100000 999999 … 1
逆序对数量：704982704
消耗时间对比：
- 暴力法：10.5386s
- 归并排序法：0.007551s
由此可见，在数据规模很大时，归并排序法的时间复杂度远远小于暴力法。（下面为测试程序）
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int t[100005];
int cnt;
void inversionscount(int l, int r);
int main() {
clock_t start, finish; //clock_t为CPU时钟计时单元数
int n = 100000;
//暴力法
start = clock(); //clock()函数返回此时CPU时钟计时单元数
cnt = 0;
for (int i = 1; i <= n; ++i) {
a[i] = n - i + 1;
}
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (a[j] < a[i])
cnt++;
}
}
cout << cnt << endl;
finish = clock();
cout << "暴力法 求逆序数对数 消耗时间：" << double(finish - start) / CLOCKS_PER_SEC << endl; //差值即为程序运行花费的CPU时钟单元数量，除以每秒CPU有多少个时钟单元，即为程序耗时
//归并排序法
start = clock();
cnt = 0;
for (int i = 1; i <= n; ++i) {
a[i] = n - i + 1;
}
inversionscount(1, n);
cout << cnt << endl;
finish = clock();
cout << "归并排序法 求逆序数对数 消耗时间：" << double(finish - start) / CLOCKS_PER_SEC << endl;
return 0;
}
void inversionscount(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
inversionscount(l, mid);
inversionscount(mid + 1, r);
int lp = l, rp = mid + 1, tp = l;
while (lp <= mid && rp <= r) {
if (a[lp] <= a[rp]) {
t[tp++] = a[lp++];
} else {
cnt = cnt + mid - lp + 1;
t[tp++] = a[rp++];
}
}
while (lp <= mid) t[tp++] = a[lp++];
while (rp <= r) t[tp++] = a[rp++];
for (int i = l; i <= r; ++i) a[i] = t[i];
}刷题题单 🧑🏻💻
刷题题单与相应题解请见博客：信息奥赛题单｜归并排序🔗 / （备用）信息奥赛题单｜归并排序🔗
如链接失效，可以在文章末尾选择上一篇博客 或 在搜索界面搜索关键词「归并排序」即可。
