逆序对是指在一个数列中，任意两个数满足前面的数大于后面的数，这两个数就构成了一个逆序对。计算逆序对的目的是衡量一个数列“乱序”的程度。
逆序对的定义：
对于一个序列 a_1, a_2, ..., a_n ，如果存在 i < j ，并且 a_i > a_j ，那么 (a_i, a_j) 就称为一个逆序对。
例如：
对于数组 [3, 2, 1]，共有 3 对逆序对，分别是：
- (3, 2)
- (3, 1)
- (2, 1)
逆序对可以用于排序相关的算法，例如在判断数组是否接近有序、通过逆序对数衡量乱序程度等。
如何高效计算逆序对？
简单的暴力算法是通过两层循环直接枚举每一对数，复杂度为 O(n^2) 。但对于大规模数据，这种方法效率较低。为了提高效率，可以利用“归并排序”的思想来计算逆序对，时间复杂度可以降到 O(n \log n) 。
归并排序计算逆序对的思想：
在归并排序中，我们将数组划分为两部分，分别对两部分计算逆序对。当我们合并两个有序数组时，通过比较左右两部分的元素，我们可以同时计算出两部分中的逆序对。
步骤：
- 使用归并排序将数组分成两部分。
- 分别递归计算左边和右边部分的逆序对。
- 合并时计算跨越左右两部分的逆序对。
代码实现：
这里是使用归并排序的方式来计算逆序对的C++代码：
#include <iostream>
using namespace std;
const int N = 100010; // 定义数组最大大小
int temp[N]; // 临时数组用于归并
int arr[N]; // 原数组
// 归并排序，并在排序过程中计算逆序对的个数
long long merge_sort(int arr[], int l, int r) {
if (l >= r) return 0; // 递归出口：当数组只有一个元素时，逆序对为0
int mid = (l + r) / 2;
long long cnt = 0;
// 递归计算左右两部分的逆序对数
cnt += merge_sort(arr, l, mid);
cnt += merge_sort(arr, mid + 1, r);
// 合并两个有序数组，并计算逆序对
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
// 逆序对数：因为 arr[i] > arr[j]，所以 [i, mid] 之间的所有元素都大于 arr[j]
cnt += (mid - i + 1);
}
}
// 将剩余元素放入临时数组
while (i <= mid) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
// 将排序后的数组复制回原数组
for (i = l, k = 0; i <= r; ++i, ++k) {
arr[i] = temp[k];
}
return cnt;
}
int main() {
int n;
cout << "输入数组长度: ";
cin >> n;
cout << "输入数组元素: ";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
// 调用归并排序计算逆序对
long long result = merge_sort(arr, 0, n - 1);
cout << "逆序对个数: " << result << endl;
return 0;
}
代码详解：
merge_sort(arr, l, r)函数是递归归并排序的主要函数，它返回的是在区间[l, r]中的逆序对数量。- 递归处理左右两部分后，在合并时，如果发现左边部分的某个元素大于右边部分的元素，说明形成了逆序对，且这些逆序对的数量等于左边部分剩余未处理元素的个数。
- 通过比较并合并两个子数组，我们能够高效地计算出跨越左右两部分的逆序对。
时间复杂度：
归并排序的时间复杂度是 O(n \log n) ，因为它将数组划分为两部分并递归处理，每次合并的时间复杂度为 O(n) 。在此过程中，计算逆序对的额外复杂度与归并操作相同，因此总复杂度是 O(n \log n) 。
总结：
通过归并排序计算逆序对是一种非常经典且高效的算法。利用“分而治之”的思想，在排序的过程中同时计算逆序对，时间复杂度为 O(n \log n) ，适合处理大规模的数组。
