【算法学习】归并排序算法思想的应用—求逆序对数量

Hey，大家好！👋 今天我们来聊聊一个有趣的话题——如何在归并排序的基础上，高效解决求逆序对数量的问题。如果你对算法感兴趣，或者正在准备算法面试，这篇文章一定会对你有所帮助！🚀

题目描述 📝

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：
对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1 ≤ n ≤ 100000，数列中的元素的取值范围 [1,10^9]。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

---

理解何为逆序对 🤔

首先，我们来理解一下什么是逆序对。简单来说，逆序对就是在一个数列中，前面的数比后面的数大。比如在数列 [2, 3, 4, 5, 6, 1] 中，2 和 1 就是一个逆序对，因为 2 > 1 且 2 在 1 的前面。

解题策略 🛠️

1. 策略①：暴力解决 💪

算法思路
在理解了逆序对的概念之后，很自然能想到可以直接使用逐个比较的策略进行求解：

分别将每个元素和其后面的所有元素进行逐个比较

• if 后面有比其小的元素: 逆序对数量++
• 重复直至最后一个元素

核心代码

// 暴力解决策略的核心代码
int count = 0;
for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (a[i] > a[j]) {count++;}}
}

复杂度分析
需要使用两个for循环——$O(n^2)$

复杂度较高，在一些要求较高的情况下会报超时错误

小挑战：你能尝试用暴力解法解决这个问题吗？试试看，感受一下它的时间复杂度吧！😉

---

2. 策略②：运用「归并排序」的算法思想 🧠

（1）回顾「归并排序」算法原理

归并排序是一种经典的分治算法，它的核心思想是将一个数组分成两个子数组，分别对子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。归并排序的时间复杂度是 $O(n\log n)$，比暴力解法高效得多。

（2）改动以求逆序对数量

原理分析
在归并排序的过程中，当我们合并两个有序的子数组时，如果左边的某个元素 a[i] 大于右边的某个元素 a[j]，那么 a[i] 和 a[j] 就构成了一个逆序对。不仅如此，由于左边的子数组是有序的，a[i] 后面的所有元素也都大于 a[j]，因此我们可以一次性计算出多个逆序对。

代码实现

#include <iostream>using namespace std;typedef long long LL; // 结果较大const int N = 100010;
int n;
int a[N], temp[N];// 求逆序对数量
LL rev_pair(int a[], int l, int r)
{if (l >= r)return 0;int mid = l + r >> 1;LL res = rev_pair(a, l, mid) + rev_pair(a, mid + 1, r);int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r){if (a[i] <= a[j])temp[k++] = a[i++];else{temp[k++] = a[j++];// 当a[i]>a[j]时，对于a[j]：与[i, mid]区间内的元素可组成逆序对res += mid - i + 1;}}while (i <= mid)temp[k++] = a[i++];while (j <= r)temp[k++] = a[j++];for (int i = l, j = 0; i <= r; ++i, ++j)a[i] = temp[j];return res;
}int main()
{cin >> n;for (int i = 0; i < n; ++i)cin >> a[i];LL res = rev_pair(a, 0, n - 1);cout << res << endl;return 0;
}

复杂度分析
归并排序的时间复杂度是 $O(n\log n)$，因此这个解法的时间复杂度也是 $O(n\log n)$，比暴力解法高效得多。

---

学习建议和鼓励 🌟

1. 多动手实践：算法的学习离不开实践，建议你亲自编写代码并运行，感受算法的魅力。
2. 不要害怕挑战：算法的学习过程中难免会遇到困难，但每一次克服困难都是一次成长。💪
3. 多与他人交流：加入一些算法学习群，和志同道合的小伙伴一起讨论问题，互相学习。

---

互动性元素 🎉

小挑战：你能尝试用归并排序的思想解决其他问题吗？比如求一个数组中的顺序对数量？🤔

推荐阅读：如果你对归并排序还不熟悉，推荐你阅读这篇关于「归并排序」的博客，里面有详细的归并排序讲解。

---

结语 🎯

通过这篇文章，我们不仅学习了如何用归并排序的思想高效解决求逆序对数量的问题，还了解了暴力解法和优化解法之间的差异。希望你能从中有所收获，并在算法的学习道路上越走越远！🚀

如果你有任何问题或想法，欢迎在评论区留言，我们一起讨论！😄

Happy Coding! 🎉