逆序对这道题几乎是算法面试里“排序类问题之后必考”的常客但很多人对它的理解停留在“会背归并排序模板”的层面。网上讲逆序对的 Go 版本资料并不多大部分是 C 和 Java我当年为了把 Go 版写顺折腾了不少时间光是一个“等于到底算不算逆序对”的边界就翻过车。这篇文章我想用 Go 代码把数组逆序对这件事完整讲明白从暴力方法到归并排序再到树状数组加离散化每一份源码都能直接跑重点是讲清楚“为什么这么写”而不只是“怎么写”。不管你是在准备算法面试还是在工程里遇到排序相似度计算的需求这篇内容应该都能给你一个可以直接落地的答案。1. 逆序对是什么为什么值得单独写一篇1.1 定义与一个手算的例子逆序对的定义说起来就一句话在一个数组 arr 中如果存在两个下标 i j并且 arr[i] arr[j]那 (i, j) 就称为一个逆序对。换句话说两个元素位置靠前的那个数值反而更大它们就是一对“逆序”。光背定义没用拿 [7, 5, 6, 4] 手算一遍i07 后面比它小的有 5、6、4共 3 个i15 后面比它小的只有 4共 1 个i26 后面比它小的只有 4共 1 个i34 后面没有元素共 0 个合起来 3 1 1 0 5这就是答案。注意不要重复算逆序对是二元组 (i, j)每一对各算一次i 从前往后扫、j 从 i1 往后扫天然不会漏也不会重。还有一个很有用的结论如果数组完全升序逆序对是 0完全降序时逆序对达到最大值 n(n-1)/2。所以逆序对数量直观反映了一个数组“有多乱”这个视角在后面理解归并排序解法时会很有帮助。1.2 它到底出现在哪些真实场景里很多人觉得逆序对是纯面试题实际工程里也有它的位置。我遇到过的典型场景是推荐系统里的排序相似度计算两个用户对同一批候选物品给出了不同的排序怎么量化这两个排序差多远一种经典度量叫 Kendall tau 距离它的计算核心就是基于逆序对数量来评估两个序列的一致程度。还有搜索引擎里分析倒排索引的扫描开销、数据仓库里预评估索引列的区分度都会间接用到这个统计量。当然对大多数同学来说最直接的动机还是面试。这道题常见的递进是先问你能不能写出暴力解法再问能不能优化到 O(n log n)最后可能追问“数组里有重复元素怎么办”“能不能用树状数组”。如果你只会背模板第二问之后基本就露馅了。我下面写的归并排序和树状数组两种方案就是应对这个递进的完整弹药。2. 暴力解法先跑通再谈优化2.1 双层循环实现与验证先把最朴素的双层循环写出来。外层 i 固定当前元素内层从 i1 一路扫到末尾凡是遇到比 arr[i] 小的就计数。Go 代码很短func bruteForceCount(arr []int) int { count : 0 for i : 0; i len(arr); i { for j : i 1; j len(arr); j { if arr[i] arr[j] { count } } } return count }就这几行复杂度 O(n²)但正确性一目了然。用 [7, 5, 6, 4] 跑一遍i0 时7 和 5、6、4 比较三次都满足大于count 变 3i1 时5 和 6 不满足、5 和 4 满足count 变 4i2 时6 和 4 满足count 变 5。结果和手算一致。我强烈建议你不管最终用什么方案都先把暴力版写出来。它的价值不是上线而是当基准后面不管是归并排序还是树状数组跑同一组数据结果必须和暴力版一致。我自己在本地写了一个随机测试脚本每次生成 1 到 200 长度的随机数组同时混入重复元素暴力版和优化版结果不一致就报警。这套验证流程帮我抓出过不止一个隐蔽 bug。2.2 暴力解法的极限在哪里复杂度 O(n²) 意味着数据量每扩大 10 倍耗时扩大约 100 倍。三个量级感受一下数组长度 n比较次数约 n²/2实测感受1 万5 千万几十毫秒勉强能用10 万50 亿秒级起步明显卡顿100 万5000 亿基本不可用工程里数组上十万实在太常见所以暴力解法只能用来确定算法正确性不能作为生产方案。接下来的两种优化都是 O(n log n)思路完全不同但都比暴力快几个数量级。3. 归并排序解法把“比较”批量变成“统计”3.1 核心思路归并过程里藏着答案归并排序解法的关键洞察是在合并两个已经有序的左右子区间时如果从右边取出一个元素放进结果序列说明这个元素比左边当前指针指向的元素小而左边尚未处理的所有元素也都比它大。换句话说右边这个元素一次性和左边剩余的所有元素构成了若干个逆序对数量就是“左边剩余元素的个数”。用 [7, 5, 6, 4] 完整走一遍。递归先把数组拆成 [7, 5] 和 [6, 4]处理 [7, 5]合并时 5 7取 5左边剩余 [7] 共 1 个计数 1处理 [6, 4]合并时 4 6取 4左边剩余 [6] 共 1 个计数 1最后合并 [5, 7] 和 [4, 6]4 5取 4左边剩余 [5, 7] 共 2 个计数 2接着 5 6取 5再比较 6 7取 6左边剩余 [7] 共 1 个计数 1总计 1 1 2 1 5。这里特别要注意的是左右两个子区间内部的逆序对在递归调用时就已经被统计并返回了合并时只需要补上跨区间的部分。如果你只盯着合并那一步数很容易把答案算小比如上面的例子只数合并时的 2 1会得出 3忽略了两个子区间内部的各 1。理解了这一点归并排序解法的代码就没什么秘密了。3.2 完整源码与关键步骤拆解直接上完整代码package main import fmt // mergeSortCount 对 arr[left:right1] 排序并返回该区间内逆序对数量 func mergeSortCount(arr []int, left, right int) int { if left right { return 0 } mid : left (right-left)/2 count : mergeSortCount(arr, left, mid) mergeSortCount(arr, mid1, right) // 合并两个有序区间顺带统计跨区间的逆序对 temp : make([]int, 0, right-left1) i, j : left, mid1 for i mid j right { if arr[i] arr[j] { temp append(temp, arr[i]) i } else { temp append(temp, arr[j]) j count mid - i 1 // 左边剩余元素个数 } } for i mid { temp append(temp, arr[i]) i } for j right { temp append(temp, arr[j]) j } copy(arr[left:right1], temp) return count } func main() { arr : []int{7, 5, 6, 4} count : mergeSortCount(arr, 0, len(arr)-1) fmt.Println(逆序对数量:, count) // 5 }四个关键点第一mid 计算写成 left (right-left)/2而不是 (leftright)/2。虽然在这个题里 leftright 溢出需要数组长度接近 int 上限才会发生但这是一个值得固化的好习惯尤其 Go 里可能处理超大切片。第二合并时一旦 arr[j] arr[i] 触发了 else 分支count 增加的是 mid - i 1也就是左边从 i 到 mid 的所有元素个数。这里的 i 是当前左边指针不是 left写错的话答案会大面积偏差。第三等于时必须走“左边先出”的分支也就是用 arr[i] arr[j]这样相等的元素不会被计成逆序对。如果你把条件写成 arr[i] arr[j]那么 arr[i] arr[j] 时会进入 else错误地把相等元素算成逆序对。这个边界在第五节还会专门说。第四合并用的临时切片用 make([]int, 0, right-left1) 预分配容量避免反复扩容带来的内存分配开销。数据量大时这个细节能省下不少时间。3.3 复杂度与稳定性的额外收益归并排序解法的时间复杂度是 O(n log n)每一层归并总工作量 O(n)一共 log n 层。空间复杂度是 O(n)主要消耗在临时切片和递归栈。值得一提的是归并排序本身是稳定排序如果你在工程里本来就需要排序用归并排序可以一边排序一边统计逆序对一份代码做两件事。4. 树状数组解法换个思路用数据结构维护前缀统计4.1 离散化把任意值域压缩成 1 到 k归并排序是分治思想树状数组则是“在线统计”思想从左到右扫数组每遇到一个元素检查前面已经扫过的元素里有多少个比它大累加进答案然后把这个元素标记为已出现。关键在于“检查比它大的数量”需要快速完成而树状数组恰好擅长做前缀和查询。但树状数组的下标必须是整数而且要开长度等于值域的数组。如果数组里是 100 万、-5、3 这种值直接开数组不现实。离散化就是解决这个问题的把所有出现过的值排序、去重然后按大小映射成 1 到 k 的排名。这样值域从“任意”压缩到“最多 n 个不同值”树状数组只需要开 k 的长度。举个例子数组 [100, 5, 100, 3]去重排序后是 [3, 5, 100]映射就是 3→1、5→2、100→3。原始数组变成排名数组 [3, 2, 3, 1]所有后续统计都在这个排名域上进行不改变元素之间的大小关系逆序对数量自然不变。4.2 树状数组实现与统计逻辑树状数组的核心是两个操作Update 在某个位置加值Query 求前缀和。它用 lowbiti -i把前缀信息分散存储在树状结构里让两个操作都做到 O(log n)。lowbit 取的就是 i 的二进制表示里最低位的 1 所代表的值比如 i6二进制 110lowbit2i8二进制 1000lowbit8。这个技巧常见于各类位运算优化的题目掌握一次后面复用很值。完整实现如下package main import ( fmt sort ) // Fenwick 树状数组下标从 1 开始 type Fenwick struct { n int tree []int } func NewFenwick(n int) *Fenwick { return Fenwick{n: n, tree: make([]int, n1)} } func (f *Fenwick) Update(i, delta int) { for ; i f.n; i i (-i) { f.tree[i] delta } } func (f *Fenwick) Query(i int) int { res : 0 for ; i 0; i - i (-i) { res f.tree[i] } return res } // inversionCount 返回 arr 的逆序对数量 func inversionCount(arr []int) int { // 第一步离散化 sorted : make([]int, len(arr)) copy(sorted, arr) sort.Ints(sorted) unique : make([]int, 0, len(sorted)) for i, v : range sorted { if i 0 || v ! sorted[i-1] { unique append(unique, v) } } rank : make(map[int]int, len(unique)) for i, v : range unique { rank[v] i 1 } // 第二步从左到右扫描 bit : NewFenwick(len(unique)) count : 0 total : 0 for _, v : range arr { r : rank[v] // 已出现元素总数 - 小于等于当前值的元素数 大于当前值的元素数 greater : total - bit.Query(r) count greater bit.Update(r, 1) total } return count } func main() { arr : []int{7, 5, 6, 4} fmt.Println(逆序对数量:, inversionCount(arr)) // 5 }这段代码的统计逻辑也可以换一种写法从右往左扫统计每个元素右边有多少小于它的元素也就是 Query(r-1)。两种写法等价我习惯从左往右因为更贴近“前面有多少比我大”的直观描述。真正容易写错的是两个细节。第一树状数组下标必须从 1 开始所以 rank 映射时要加一。如果直接拿去重排序后的下标从 0 开始当树状数组下标Update(0, 1) 会让 lowbit 循环出问题这是很多新手第一次写 BIT 必踩的坑。第二离散化去重不能省如果不去重两个相等的值会被映射成不同排名Query(r) 统计“小于等于当前值”时就会漏算相等的元素把相等的值误当成比它大逆序对数量偏大。用 [3, 3, 1] 这个用例一测就能发现错误结果正确答案是 2。4.3 归并与树状数组怎么选两个方案各有适用面。归并排序代码更短、边界更少适合一次性的离线统计面试时优先选它树状数组需要额外写 BIT 和离散化理解成本高一些但 BIT 本身是个通用结构动态修改数组、在线查询前缀和都能复用。下面这张表是我选型时常用的对比对比项归并排序解法树状数组解法时间复杂度O(n log n)O(n log n)空间复杂度O(n)O(n)对数据的要求只要求可比较大小要求可排序、可映射排名实现长度较短较长BIT 离散化是否修改原数组会排序不会可扩展性较低BIT 可复用支持动态更新实际工程里如果只是一次性统计基本无脑选归并排序。如果后续要维护动态数组、频繁查询逆序对变化树状数组路线会更值得沉淀。5. 实战中的坑与排查清单5.1 逆序对结果溢出问题逆序对数量最大是 n(n-1)/2这个数涨得比想象快得多。n 10 万时最大约 50 亿n 100 万时约 5 万亿。虽然 Go 在 64 位平台下 int 是 64 位但 Go 官方规定 int 在 32 位平台是 32 位最大只有 21.47 亿左右。如果你的代码可能在 32 位环境编译运行或者要和其他语言的同学讨论算法count 用 int64 是更稳妥的做法。5.2 重复元素与等号边界这是全题最容易错的地方。记住一句话严格大于才算逆序对等于不算。归并排序里合并条件必须写成 arr[i] arr[j]让相等的元素稳定地从左边出来不为它计数树状数组里离散化去重保证相等的元素映射到同一个 rankQuery(r) 把等于当前值的元素排除在“大于”之外。两边任何一个细节漏掉重复元素多的测试用例都会算错。我常用的验证用例包括测试数组期望结果说明[1, 2, 3]0完全升序无逆序对[3, 2, 1]3完全降序最大逆序对[3, 3, 1]2两个 3 分别与 1 构成逆序对3 与 3 不算[7, 5, 6, 4]5经典手算用例5.3 性能实测与递归陷阱归并排序的递归深度是 log n十万级数组深度大约 17 层完全不用担心栈溢出。真正要防的是把“归并”写成每一次都只移动一个元素的“插入式合并”那样整体复杂度会退化到 O(n²)数据一大就原形毕露。我实测过本机运行 100 万随机数归并排序解法大约 150 毫秒树状数组解法因为要先排序做离散化略慢一点但也在同一量级。作为参考暴力版在这个数据量下要跑到小时级。5.4 一个高效的验证与调试方法最后分享一个我用过无数次的方法写一个辅助函数用暴力法算结果再生成大量随机测试数据长度随机、包含重复值、包含极端升降序两边结果对比。一旦不一致就打印数组和两个结果人工定位。这个过程其实花不了几分钟但能帮你筛掉绝大多数边界问题。我最初写树状数组版本时就是靠这个随机对比才发现自己离散化去重那一步漏了导致 [3, 3, 1] 这类用例全部算错。这些看似“无用功”的验证习惯恰恰是写算法代码时最值得投入时间的地方。