数组逆序对（Array Inversion Pairs）
📌 定义
数组的逆序对是指数组中的两个元素 (i, j)，满足 i < j 且 arr[i] > arr[j]。逆序对的数量反映了数组的混乱程度。
数组: [7, 5, 6, 4]
逆序对:
(7, 5), (7, 6), (7, 4), (5, 4), (6, 4)
逆序对总数: 5
核心思路
使用归并排序的思想，在归并过程中统计逆序对：
- 分解：将数组分成左右两部分
- 递归：分别统计左右两部分的逆序对
- 合并：统计跨越左右两部分的逆序对
关键：在合并有序数组时，如果左边元素大于右边元素，则形成逆序对。
数组: [7, 5, 6, 4]
↓
[7, 5] [6, 4]
↓ ↓
[7][5] [6][4]
合并时统计逆序对:
- 左半部分: 1个 (7, 5)
- 右半部分: 1个 (6, 4)
- 跨越部分: 3个 (7, 6), (7, 4), (5, 4)
总计: 5个
状态与不变量
令 count(left, right) 表示子数组 arr[left:right+1] 内的逆序对数量。递归返回时同时保证两件事：
- 返回值已经统计了当前区间内的全部逆序对。
- 当前区间已经被原地整理为有序，供上一层合并使用。
当前区间的答案可以拆成三部分：
左半逆序对 + 右半逆序对 + 跨越左右两半的逆序对
合并时如果 arr[i] > arr[j]，由于左半部分有序，arr[i] 到 arr[mid] 都大于 arr[j]，所以一次累加 mid-i+1，而不是逐个枚举。
🎞️ 合并过程动画
（附件 merge-sort-split-merge.svg 未随站点发布）
看动画时只盯住合并阶段：右半部分元素先被取出时，左边剩余元素的数量就是新增逆序对数量。
复杂度分析
| 指标 | 暴力枚举 | 归并排序 |
|---|---|---|
| 时间复杂度 | O(n²) | O(n log n) |
| 空间复杂度 | O(1) | O(n) |
| 稳定性 | - | 可以保持稳定 |
Go 代码
Go 实现
package main
import "fmt"
func countInversions(arr []int) int {
temp := make([]int, len(arr))
return mergeSort(arr, temp, 0, len(arr)-1)
}
func mergeSort(arr, temp []int, left, right int) int {
if left >= right {
return 0
}
mid := (left + right) / 2
count := mergeSort(arr, temp, left, mid)
count += mergeSort(arr, temp, mid+1, right)
count += merge(arr, temp, left, mid, right)
return count
}
func merge(arr, temp []int, left, mid, right int) int {
i := left
j := mid + 1
k := left
count := 0
for i <= mid && j <= right {
if arr[i] <= arr[j] {
temp[k] = arr[i]
i++
} else {
temp[k] = arr[j]
count += (mid - i + 1) // 统计逆序对
j++
}
k++
}
for i <= mid {
temp[k] = arr[i]
i++
k++
}
for j <= right {
temp[k] = arr[j]
j++
k++
}
for i := left; i <= right; i++ {
arr[i] = temp[i]
}
return count
}
func main() {
arr := []int{7, 5, 6, 4}
inversions := countInversions(arr)
fmt.Printf("逆序对数量: %d\n", inversions)
}思路展开
逆序对统计原理
左半部分: [5, 7] (已排序)
右半部分: [4, 6] (已排序)
合并过程:
比较 5 和 4: 5 > 4
→ 4加入结果，逆序对 += 2 (5,4) (7,4)
比较 5 和 6: 5 < 6
→ 5加入结果
比较 7 和 6: 7 > 6
→ 6加入结果，逆序对 += 1 (7,6)
比较 7 (无): 7加入结果
结果: [4, 5, 6, 7]
跨越逆序对: 3个
为什么是 mid - i + 1？
当 arr[i] > arr[j] 时：
- 左边从
i到mid的所有元素都大于arr[j] - 因为左半部分已经是有序的
- 所以一次性统计
mid - i + 1个逆序对
经典题目
LeetCode 问题
- 数组中的逆序对 - 剑指 Offer 51
- 翻转对 - LeetCode 493
- 计算右侧小于当前元素的个数 - LeetCode 315
扩展问题
- 求数组中的顺序对（正序对）
- 区间逆序对查询
- 二维数组逆序对
⚖️ 优缺点
优点
- ✅ 高效：O(n log n)时间复杂度
- ✅ 稳定：可以保持相等元素的相对顺序
- ✅ 副作用：排序完成后数组也变有序
缺点
- ❌ 空间复杂度：需要O(n)额外空间
- ❌ 实现复杂：相比暴力法代码较复杂
🎨 应用场景
- 排序算法性能分析：逆序对数量反映数组混乱程度
- 推荐系统：计算用户偏好的相似度
- 数据挖掘：寻找数据中的异常模式
- 统计学：Kendall秩相关系数计算
- 竞赛排名：比较两个排名的差异
💡 变体问题
- 翻转对：把判断条件从
arr[i] > arr[j]改成arr[i] > 2*arr[j]，通常在归并前增加双指针统计。 - 右侧小于当前元素的个数：对每个元素记录它在归并过程中被右侧元素跨过的次数。
- 动态逆序对：如果数组会在线修改，通常改用树状数组、线段树或 CDQ 分治。
- 二维偏序问题：先按一个维度排序，再把另一个维度转成逆序对统计。