1. 概述
在本教程中，我们将讨论如何计算数组中的逆序对（Inversion）。我们会先明确定义该问题，并通过一个例子来解释“逆序”的含义。
随后，我们会介绍两种解决该问题的思路：一种是暴力枚举的朴素解法，另一种是基于分治策略的高效解法。最后，我们还会简要说明逆序对的实际应用场景。
2. 问题定义
假设我们有一个由 n 个整数组成的数组 A，索引从 0 到 n - 1，其中第 i 个元素的值为 A[i]。
一个逆序对（Inversion）是指满足如下条件的一对索引 (i, j)：
- i < j
- A[i] > A[j]
换句话说，逆序对是一对索引顺序与其元素值顺序相反的组合。
我们的问题是：给定一个数组 A，求出其中所有逆序对的数量。
举个例子：
数组 A = [1, 2, 3, 1, 2]
在这个数组中，有以下三个逆序对：
- (1, 3)：A[1] = 2 > A[3] = 1
- (2, 3)：A[2] = 3 > A[3] = 1
- (2, 4)：A[2] = 3 > A[4] = 2
所以总共有 3 个逆序对。
注意：
- 当数组已升序排列时，逆序对数量为 0
- 当数组已降序排列时，逆序对数量为最大值 n × (n - 1) / 2（假设所有元素互不相同）
因此，逆序对的数量可以看作是数组与“有序”状态之间的距离度量。
3. 朴素解法（Brute Force）
3.1 思路
思路非常简单：暴力枚举所有 i < j 的组合，统计其中 A[i] > A[j] 的情况数量。
虽然实现简单，但时间复杂度较高。
3.2 实现代码
int countInversions(int[] A) {
int count = 0;
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length; j++) {
if (A[i] > A[j]) {
count++;
}
}
}
return count;
}
3.3 时间复杂度分析
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
适用于小规模数据，但不适用于大规模数组。
4. 分治解法（Divide and Conquer）
4.1 核心思想
该方法基于归并排序的思想，利用递归将数组划分为左右两部分，分别统计：
- 左半部分内部的逆序对数
- 右半部分内部的逆序对数
- 跨左右两部分的逆序对数（即左半部分元素 > 右半部分元素）
其中第 3 类是关键，它可以通过归并过程中两个已排序子数组的比较来统计。
4.2 关键步骤说明
- 递归拆分数组：将数组一分为二，递归处理左右两部分
- 归并并统计跨区逆序对数
- 合并两个已排序子数组
4.3 实现代码
public class InversionCounter {
public static int countInversions(int[] A) {
return mergeSortAndCount(A, 0, A.length - 1);
}
private static int mergeSortAndCount(int[] A, int left, int right) {
if (left >= right) return 0;
int mid = (left + right) / 2;
int invCount = 0;
// 递归处理左右两半
invCount += mergeSortAndCount(A, left, mid);
invCount += mergeSortAndCount(A, mid + 1, right);
// 合并并统计跨区逆序对
invCount += mergeAndCount(A, left, mid, right);
return invCount;
}
private static int mergeAndCount(int[] A, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
int invCount = 0;
while (i <= mid && j <= right) {
if (A[i] <= A[j]) {
temp[k++] = A[i++];
} else {
temp[k++] = A[j++];
invCount += (mid - i + 1); // 所有 A[i...mid] 都 > A[j]
}
}
while (i <= mid) temp[k++] = A[i++];
while (j <= right) temp[k++] = A[j++];
// Copy back to original array
System.arraycopy(temp, 0, A, left, temp.length);
return invCount;
}
}
4.4 时间复杂度分析
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)（归并排序需要额外空间）
✅ 优点：适用于大规模数组，效率远高于暴力解法
❌ 缺点：实现相对复杂，需要理解归并排序原理
5. 应用场景
逆序对在实际中有一些有趣的应用，例如：
- 衡量两个排序序列之间的相似性（如推荐系统中用户排序偏好对比）
- 计算交换操作次数：如果每次只能交换相邻两个元素，那么将数组排序所需的最少交换次数等于逆序对数量
⚠️ 注意：逆序对本身并不直接给出排序路径，但它是一个重要的中间指标。
6. 总结
本文介绍了计算数组中逆序对数量的问题，包括：
| 方法 | 时间复杂度 | 适用场景 | 实现难度 |
|---|---|---|---|
| 暴力枚举 | O(n²) | 小规模数据 | ✅ 简单 |
| 分治法（归并排序变种） | O(n log n) | 大规模数据 | ⚠️ 中等 |
✅ 建议：对于 n 较大的数组，应优先使用分治法
✅ 踩坑提醒：不要在实际项目中使用暴力解法处理大规模数据，否则可能遇到性能瓶颈
如果你在处理排序、推荐、比较、交换类问题时遇到瓶颈，不妨尝试用逆序对的思路来建模问题。