企业官网建设流程全解析

逆序对这道题，几乎是算法面试里“排序类问题之后必考”的常客，但很多人对它的理解停留在“会背归并排序模板”的层面。网上讲逆序对的 Go 版本资料并不多，大部分是 C++ 和 Java，我当年为了把 Go 版写顺折腾了不少时间，光是一个“等于到底算不算逆序对”的边界就翻过车。这篇文章我想用 Go 代码把数组逆序对这件事完整讲明白：从暴力方法到归并排序，再到树状数组加离散化，每一份源码都能直接跑，重点是讲清楚“为什么这么写”，而不只是“怎么写”。不管你是在准备算法面试，还是在工程里遇到排序相似度计算的需求，这篇内容应该都能给你一个可以直接落地的答案。

1. 逆序对是什么，为什么值得单独写一篇

1.1 定义与一个手算的例子

逆序对的定义说起来就一句话：在一个数组 arr 中，如果存在两个下标 i < j，并且 arr[i] > arr[j]，那 (i, j) 就称为一个逆序对。换句话说，两个元素，位置靠前的那个数值反而更大，它们就是一对“逆序”。

光背定义没用，拿 [7, 5, 6, 4] 手算一遍：

• i=0，7 后面比它小的有 5、6、4，共 3 个
• i=1，5 后面比它小的只有 4，共 1 个
• i=2，6 后面比它小的只有 4，共 1 个
• i=3，4 后面没有元素，共 0 个

合起来 3 + 1 + 1 + 0 = 5，这就是答案。注意不要重复算：逆序对是二元组 (i, j)，每一对各算一次，i 从前往后扫、j 从 i+1 往后扫，天然不会漏也不会重。

还有一个很有用的结论：如果数组完全升序，逆序对是 0；完全降序时逆序对达到最大值 n(n-1)/2。所以逆序对数量直观反映了一个数组“有多乱”，这个视角在后面理解归并排序解法时会很有帮助。

1.2 它到底出现在哪些真实场景里

很多人觉得逆序对是纯面试题，实际工程里也有它的位置。我遇到过的典型场景是推荐系统里的排序相似度计算：两个用户对同一批候选物品给出了不同的排序，怎么量化这两个排序差多远？一种经典度量叫 Kendall tau 距离，它的计算核心就是基于逆序对数量来评估两个序列的一致程度。还有搜索引擎里分析倒排索引的扫描开销、数据仓库里预评估索引列的区分度，都会间接用到这个统计量。

当然，对大多数同学来说，最直接的动机还是面试。这道题常见的递进是：先问你能不能写出暴力解法，再问能不能优化到 O(n log n)，最后可能追问“数组里有重复元素怎么办”“能不能用树状数组”。如果你只会背模板，第二问之后基本就露馅了。我下面写的归并排序和树状数组两种方案，就是应对这个递进的完整弹药。

2. 暴力解法：先跑通，再谈优化

2.1 双层循环实现与验证

先把最朴素的双层循环写出来。外层 i 固定当前元素，内层从 i+1 一路扫到末尾，凡是遇到比 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] 跑一遍：i=0 时，7 和 5、6、4 比较，三次都满足大于，count 变 3；i=1 时，5 和 6 不满足、5 和 4 满足，count 变 4；i=2 时，6 和 4 满足，count 变 5。结果和手算一致。

我强烈建议你不管最终用什么方案，都先把暴力版写出来。它的价值不是上线，而是当基准：后面不管是归并排序还是树状数组，跑同一组数据，结果必须和暴力版一致。我自己在本地写了一个随机测试脚本，每次生成 1 到 200 长度的随机数组（同时混入重复元素），暴力版和优化版结果不一致就报警。这套验证流程帮我抓出过不止一个隐蔽 bug。

2.2 暴力解法的极限在哪里

复杂度 O(n²) 意味着数据量每扩大 10 倍，耗时扩大约 100 倍。三个量级感受一下：

工程里数组上十万实在太常见，所以暴力解法只能用来确定算法正确性，不能作为生产方案。接下来的两种优化都是 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:right+1] 排序，并返回该区间内逆序对数量 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, mid+1, right) // 合并两个有序区间，顺带统计跨区间的逆序对 temp := make([]int, 0, right-left+1) i, j := left, mid+1 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:right+1], 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，而不是 (left+right)/2。虽然在这个题里 left+right 溢出需要数组长度接近 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-left+1) 预分配容量，避免反复扩容带来的内存分配开销。数据量大时，这个细节能省下不少时间。

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 求前缀和。它用 lowbit（i & -i）把前缀信息分散存储在树状结构里，让两个操作都做到 O(log n)。lowbit 取的就是 i 的二进制表示里最低位的 1 所代表的值，比如 i=6（二进制 110），lowbit=2；i=8（二进制 1000），lowbit=8。这个技巧常见于各类位运算优化的题目，掌握一次，后面复用很值。

完整实现如下：

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, n+1)} } 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 本身是个通用结构，动态修改数组、在线查询前缀和都能复用。下面这张表是我选型时常用的对比：

实际工程里如果只是一次性统计，基本无脑选归并排序。如果后续要维护动态数组、频繁查询逆序对变化，树状数组路线会更值得沉淀。

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]，让相等的元素稳定地从左边出来，不为它计数；树状数组里，离散化去重保证相等的元素映射到同一个 rank，Query(r) 把等于当前值的元素排除在“大于”之外。两边任何一个细节漏掉，重复元素多的测试用例都会算错。我常用的验证用例包括：

5.3 性能实测与递归陷阱

归并排序的递归深度是 log n，十万级数组深度大约 17 层，完全不用担心栈溢出。真正要防的是把“归并”写成每一次都只移动一个元素的“插入式合并”，那样整体复杂度会退化到 O(n²)，数据一大就原形毕露。我实测过本机运行 100 万随机数，归并排序解法大约 150 毫秒，树状数组解法因为要先排序做离散化，略慢一点，但也在同一量级。作为参考，暴力版在这个数据量下要跑到小时级。

5.4 一个高效的验证与调试方法

最后分享一个我用过无数次的方法：写一个辅助函数，用暴力法算结果，再生成大量随机测试数据（长度随机、包含重复值、包含极端升降序），两边结果对比。一旦不一致就打印数组和两个结果，人工定位。这个过程其实花不了几分钟，但能帮你筛掉绝大多数边界问题。我最初写树状数组版本时，就是靠这个随机对比，才发现自己离散化去重那一步漏了，导致 [3, 3, 1] 这类用例全部算错。这些看似“无用功”的验证习惯，恰恰是写算法代码时最值得投入时间的地方。