当前位置：首页 > news >正文

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

news 2025/6/30 10:49:28

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

输出样例：

理解何为逆序对 🤔

首先，我们来理解一下什么是逆序对。简单来说，逆序对就是在一个数列中，前面的数比后面的数大。比如在数列 [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）回顾「归并排序」算法原理

归并排序是一种经典的分治算法，它的核心思想是将一个数组分成两个子数组，分别对子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。归并排序的时间复杂度是 $\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;
}