聊一个几乎每个刷题党都绕不过去的经典问题——数组中的逆序对。它在《剑指Offer》里是排序章节的重头戏，LeetCode 上也对应了“交易逆序对总数”这道题。题面本身就一句话：给定一个数组，统计其中所有“前面数字大于后面数字”的数对数量。看起来是个简单的计数问题，但暴力做法在数据量稍大时就彻底歇菜，而最优解法需要你把归并排序的分治过程理解到骨子里。这篇文章我会从暴力解法讲起，完整拆解归并排序计数的原理和代码实现，把取模溢出、边界条件、调试方法这些实战中容易踩的坑全部摊开讲清楚。正在准备算法面试，或者想彻底搞懂归并排序本质的同学，这题值得你花一晚上认真吃透。
1. 先搞清楚问题：逆序对的定义与题目定位
1.1 一个例子看懂什么是逆序对
先说定义。设数组为nums，长度n，如果存在下标i < j，并且nums[i] > nums[j]，那这一对(i, j)就是一个逆序对。注意两个约束：一是下标必须从小到大，二是比较的是数值的大小，严格大于才算，等于不算。
拿最经典的例子来说，[7, 5, 6, 4]一共有 5 个逆序对：
(7, 5)，因为 7 在 5 前面且 7 > 5(7, 6)，同理(7, 4)(5, 4)(6, 4)
而(5, 6)不是逆序对，因为 5 < 6；(4, 5)也不是，虽然 4 < 5，但 4 出现在 5 的后面，不满足“前面数字大于后面数字”的条件。这里最容易犯的错就是把逆序对当成“任意两个数字的降序排列”，漏掉了下标顺序的限制。我在实际给同学讲这题的时候就发现，不少人会下意识地去看“数组中有几对逆序”，却不自觉地把元素重新排了序，这是理解上的偏差。
如果数组是升序的，比如[1, 2, 3, 4]，逆序对数就是 0；如果数组是降序的，比如[4, 3, 2, 1]，那任意两个元素都构成逆序对，总数是n*(n-1)/2，也就是 4 个元素时有 6 个逆序对。这两个极端情况可以用来验证你后面写的算法是否正确，我每次写完代码第一件事就是拿这两个例子跑一遍，比写一堆测试用例还快。
1.2 这道题到底在考察什么
面试官出这道题，表面上问的是“你会不会统计逆序对”，实际上想看你三个层面的能力。
第一，基础的数据结构认知。你至少能想到暴力解法，说明你理解数组的遍历和下标关系。第二，对排序算法本质的理解。逆序对的数量和排序过程有天然的联系：一次交换相邻元素的排序（比如冒泡排序），每一轮交换本质上就是在消除一个逆序对。所以逆序对总数也可以理解为“把这个数组排成升序所需的最小相邻交换次数”。第三，分治与归并思想。最优解法需要你意识到，在归并排序合并两个有序子数组的过程中，可以用 O(1) 的时间批量统计一大片逆序对，把复杂度从 O(n²) 降到 O(n log n)。
这个考察梯度其实挺清晰的：暴力解能拿基础分，归并解才是这道题真正的分水岭。很多人知道归并排序能求逆序对，也知道代码模板长什么样，但面试官只要多问一句“为什么在这个时机计数就是对的”，立刻就卡壳了。所以后面我会重点讲清原理，而不是只甩一个模板出来。
2. 暴力解法：双重循环15分钟搞定，但跑不过大数据
2.1 双重循环实现与代码
先写最直观的暴力做法。既然逆序对就是i < j且nums[i] > nums[j]，那直接枚举所有下标对就行：
int reversePairs(vector<int>& nums) { int n = nums.size(); int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] > nums[j]) { count++; } } } return count; }这段代码逻辑没有任何问题，边界也干净，空数组直接返回 0。如果你在笔试里时间不够、数据量又小（几百个元素），这么写完全能过。但问题在于，当n到 10⁵ 量级时，双重循环要执行大约10¹⁰次比较，这在任何OJ上都是妥妥的超时。
2.2 为什么O(n²)到了10的5次方就危险
可以简单算一笔账。假设你的机器每秒能跑 10⁸ 次简单运算，n = 10⁵时双重循环的比较次数接近5 × 10⁹，光是循环体就要跑 50 秒以上，这还没算count++的开销。即使运气好数据随机、提前剪枝，也改变不了量级上注定超时的结局。
另外一个容易被忽略的问题：count用int来存，在n = 10⁵时逆序对最多有10⁵ × 99999 / 2 ≈ 5 × 10⁹，早就溢出 32 位整型了。所以即使你写了暴力解，也得用long long或者对结果取模，否则会得到完全错误的负数。这个细节在后面的归并解里同样要注意，我见过不止一个同学算法写对了，结果栽在数据类型上。
暴力解存在的意义不是让你真去提交，而是作为 baseline。你可以用它生成随机小数组，再用归并解法跑同样的数据，对比两边结果是否一致。这个对拍方法是我调试一切算法题的万能第一步，后面在排查部分我会专门展开讲。
3. 归并排序解法：边排序边计数的核心思路
3.1 为什么选归并排序而不是其他排序
求逆序对的最优解法是归并排序，这里需要解释清楚“为什么是归并”。你可能会想，快速排序也是 O(n log n)，能不能用它？答案是不能，至少不能直接套。
归并排序的核心动作是“合并两个有序数组”。当两个子数组[left...mid]和[mid+1...right]都已经各自有序时，合并的过程天然地暴露了一个信息：如果右半部分的某个元素nums[j]小于左半部分当前元素nums[i]，那么左半部分从i到mid的所有元素都大于nums[j]，这中间有多少个元素，就有多少个逆序对。一次可以批量统计，而不是一个个比较。
快速排序没有这个性质。它的partition过程是把元素按照 pivot 分成两堆，但两堆之间不存在“左边堆的所有元素都对应右边某些元素的一一比较关系”，你很难在一次交换中批量计数。所以刷这类题，归并排序几乎是唯一自然的解法，这也是为什么《剑指Offer》会把这题放在排序章节里。
3.2 统计时机：右半元素小于左半当前元素的那一刻
理解归并求逆序对，我建议只盯住一个时刻：合并两个有序子数组时，右半部分的当前指针j指向的元素小于左半部分当前指针i指向的元素。
假设当前状态是：
左半数组：[2, 5, 8] 右半数组：[1, 3, 6]合并开始时，i指向 2，j指向 1。因为1 < 2，说明右半的这个元素比左半当前元素小。由于左右两个子数组都是升序的，左半从i到末尾的所有元素——也就是 2、5、8——都大于 1。这一下子就找到了 3 个逆序对：(2,1)、(5,1)、(8,1)。
然后j移动到 3，继续和i指向的 2 比较，这次2 < 3，没有逆序对，把 2 放入结果数组，i指向 5。接着3 < 5，右半的 3 又比左半的 5、8 小，于是又得到 2 个逆序对：(5,3)、(8,3)。
关键在于，每次发现右半元素小于左半元素时，不需要回头遍历左半剩余部分，直接用mid - i + 1这个公式算出逆序对数量。这个公式的+1是为了把当前位置i自己也算进去，写成mid - i就会漏数一个。
3.3 用一个例子完整演示统计过程
还是用[7, 5, 6, 4]来跑一遍完整的归并过程，你可以跟着手写一遍加深理解。
第一步，拆分成[7, 5]和[6, 4]，继续拆成[7]、[5]、[6]、[4]四个单元素数组。
第二步，合并[7]和[5]。i指向 7，j指向 5，5 < 7，此时左半只剩 7 这一个元素，mid - i + 1 = 1，计入 1 个逆序对(7, 5)。合并后得到[5, 7]。
第三步，合并[6]和[4]，同样是 1 个逆序对(6, 4)，合并后得到[4, 6]。
第四步，合并[5, 7]和[4, 6]：
i指向 5，j指向 4，4 < 5，计mid - i + 1 = 2，对应(5,4)和(7,4)，然后j移到 6i指向 5，5 < 6，没有逆序对，把 5 放入结果，i移到 7i指向 7，j指向 6，6 < 7，计mid - i + 1 = 1，对应(7,6)，j移到末尾- 左半剩余 7 直接放入结果
四次合并累计：1 + 1 + 2 + 1 = 5，和暴力解完全一致。
这个例子我建议你亲自在纸上画一遍。归并排序求逆序对最怕的就是“好像懂了原理，但代码一写就乱”，核心原因就是没有把合并过程走一遍，脑子里没有那个指针移动的画面。
4. 代码实现与落地细节：C++版完整代码
4.1 完整可运行的代码
归并求逆序对的代码框架和归并排序几乎一样，区别只在合并时多一行计数。下面给出一个可以直接跑通的 C++ 实现：
class Solution { public: int reversePairs(vector<int>& nums) { vector<int> tmp(nums.size()); return mergeSort(nums, tmp, 0, nums.size() - 1); } int mergeSort(vector<int>& nums, vector<int>& tmp, int left, int right) { if (left >= right) return 0; int mid = left + (right - left) / 2; int count = mergeSort(nums, tmp, left, mid) + mergeSort(nums, tmp, mid + 1, right); int i = left; int j = mid + 1; int k = left; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) { tmp[k++] = nums[i++]; } else { count += mid - i + 1; tmp[k++] = nums[j++]; } } while (i <= mid) tmp[k++] = nums[i++]; while (j <= right) tmp[k++] = nums[j++]; for (int p = left; p <= right; p++) { nums[p] = tmp[p]; } return count; } };代码里有两个容易踩的细节，我特意标注一下。第一，mid用left + (right - left) / 2而不是(left + right) / 2，是为了防止left + right溢出，虽然这道题n通常到不了溢出的量级，但写成这种形式更稳妥。第二，合并时的tmp数组只创建一次，每次合并只是拷贝对应区间，不要在递归里反复new数组，否则空间和时间开销都会变大。
4.2 三个容易写错的细节
第一个细节是递归的终止条件。if (left >= right) return 0;这个条件同时覆盖了空数组和单元素数组。如果写成left == right，空数组传进来时left = 0, right = -1，会直接出错。我之前就犯过这个低级错误，后来养成习惯，凡是递归的区间函数，一律写成left >= right或者额外判断空数组。
第二个细节是nums[i] <= nums[j]的等号。合并时如果左半元素等于右半元素，应该先取左半，不产生逆序对。如果把等号漏掉，写成<，那相等的元素也会被误判成逆序对。题目要求“严格大于”才计数，这个等号的位置直接决定结果是否正确。我之前给别人 review 代码时，就有人在这里纠结了很久，最后发现是等号问题。
第三个细节是递归先统计左右两半的逆序对数，再统计当前合并的逆序对数。很多初学归并的人会忘记mergeSort的返回值需要累加，导致只算了最后一次合并的逆序对，结果比正确答案小很多。如果你发现自己的输出总是比预期少，优先检查这一行。
4.3 时间复杂度与空间复杂度验证
归并排序的时间复杂度可以这样理解：每一层递归处理整个数组的所有元素，需要 O(n) 的时间，递归深度是 O(log n)，所以总时间是 O(n log n)。在归并排序的基础上额外做逆序对计数，是在合并时用 O(1) 的公式批量计算的，不会增加复杂度量级。
空间复杂度是 O(n)，因为需要额外的tmp数组。这里有一个常被问到的问题：能不能不用额外数组，原地归并？理论上可以，但实现复杂度很高，实际工程和面试中都不推荐，老老实实用 O(n) 的辅助数组就好。
我用一个n = 100000的随机数组做了简单测试，暴力解法跑了 15 秒以上还没出结果，归并解法大约 0.02 秒就返回了。这个对比非常直观，也是我向别人解释“为什么要学归并”时最常用的例子，复杂度分析再详细也不如实际跑一次来得震撼。
5. 做题中常见的坑与排查方法
5.1 大数溢出：为什么结果要对1000000007取模
这是我见过最多人栽的坑，没有之一。《剑指Offer》原题里有一个要求：结果如果很大，需要对1000000007取模。很多同学看到“取模”两个字就习惯性地在每次累加后% 1000000007，但如果中间结果用的是int，在累加之前就已经溢出了，后面再取模也是错的。
正确做法是用long long存逆序对数量，累加完再取模，或者直接全程用long long。我建议这样写：
const long long MOD = 1000000007; long long count = 0; // ... 在合并时执行 count = (count + mid - i + 1) % MOD;要注意的是，mid - i + 1这个增量本身也要保证不会溢出。当n很大时，单次增量最多是数组长度，用long long完全没压力。如果用int累加到一定程度再取模，就会出现“模出来是对的，但实际是负数加回来的错误结果”，这种 bug 非常难查，因为小数据测试永远是过的，只有大数据才会翻车。
5.2 空数组和单元素数组怎么处理
这两个边界情况是 OJ 上最容易出现的隐藏用例。空数组传入时，nums.size() - 1会得到size_t下溢的巨大数，如果不做处理，递归调用直接跑飞。单元素数组虽然没有下溢问题，但如果你的递归终止条件写得不对，也会进入无限递归。
我建议在入口函数里额外守一道：
int reversePairs(vector<int>& nums) { if (nums.size() <= 1) return 0; vector<int> tmp(nums.size()); return mergeSort(nums, tmp, 0, nums.size() - 1); }这样即使递归函数本身能处理边界，入口也能提前挡掉最极端的情况，双保险。有些同学觉得这步多余，但实际提交时多一个边界守护往往能少一次 Wrong Answer。
5.3 原数组被排序了怎么办
归并排序会改变原数组的顺序。如果你的业务场景里原数组之后还要用，就得先拷贝一份副本，对副本做归并和计数：
vector<int> copy(nums); reversePairs(copy); // 计数后原数组 nums 不受影响这一点在面试里值得主动提出来。面试官很喜欢问“你的解法会不会修改原数组”，如果你提前意识到这个问题，说明你真的理解了归并排序的副作用，而不只是背了一个模板。我自己的习惯是，如果题目没有说明允许修改原数组，一律先拷贝，宁可多花 O(n) 空间，也不要留下隐患。
5.4 用对数器排查逻辑错误
排查归并逆序对逻辑错误最有用的工具就是对数器（对拍程序）。思路很简单：写一个绝对正确的暴力解，再随机生成大量小数组，对比暴力解和归并解的结果是否一致。一旦发现不一致，立即缩小数组规模，直到能手动模拟为止。
我实际调试时一般是这样的流程。先固定数组长度为 10 以内，随机生成几千组数据，暴力解和归并解都跑一遍。如果有某一组不一致，把那组数据单独拿出来，人工推演一遍归并过程。很多时候错误都出在合并时mid - i + 1的计算上，要么是i的更新时机不对，要么是equality处用了错误的比较符号。这个排查方法比盯着代码看半小时高效得多，强烈建议每个人都试试。
6. 从逆序对延伸开的变体题
6.1 计算右侧小于当前元素的个数
LeetCode 上有一道经典的变体题“计算右侧小于当前元素的个数”：对数组中的每一个元素，统计它右边有多少元素比它小，并输出一个等长的数组。比如[5,2,6,1]对应输出[2,1,1,0]。
这道题不能直接套逆序对的代码，因为逆序对只统计总和，这道题要输出每个位置的单独计数。在归并合并时，当右半元素nums[j]小于左半当前元素nums[i]，说明nums[i]的“右侧小于它的元素”数量需要一次性加上j到右半末尾的所有元素。这里的关键变化是，计数方向从“左半有多少比右半当前元素大”变成了“右半有多少比左半当前元素小”，公式也从mid - i + 1变成right - j + 1。
这类变体题在面试中很常见，因为它们考察的是同一个归并思想，但从“总数统计”变成了“分段统计”，如果你理解了归并计数的本质，换一下统计对象就能轻松应对。
6.2 翻转对：把比较条件改一改
“翻转对”这道题要求统计i < j且nums[i] > 2 * nums[j]的数对数量。表面上看只是把条件改成了两倍，但实际上不能直接在合并归并排序时趁着nums[j] < nums[i]的机会顺手计数，因为nums[i] > 2 * nums[j]的判断时机和归并合并的移动时机不再吻合。
解决办法是在归并排序的过程中，对每个左半元素，二分查找右半数组中第一个不满足nums[i] > 2 * nums[j]的位置，从而批量统计。这一下就变成“归并排序 + 二分查找”的组合题，难度明显上了一个台阶。但如果你能把逆序对的基本原理吃透，翻转对只是在这个基础上多了一步二分查找而已。
6.3 树状数组解法：另一种常见的实现思路
除了归并排序，求逆序对还有一个广泛使用的解法：树状数组（Fenwick Tree）。思路是先把数组离散化，然后从左到右遍历，每次查询当前已经插入的数中有多少个比当前元素大，再把当前元素插入树状数组。查询和插入都是 O(log n)，总复杂度同样是 O(n log n)。
两种方法各有优劣。归并排序不需要离散化，直接就能做，代码相对长一些；树状数组代码更短，但需要额外处理离散化，并且理解门槛略高。面试中我更推荐先用归并排序，因为它顺带复习了分治思想，而且代码不容易写错。但如果面试官追问“你有没有其他解法”，能说出树状数组的思路会是不错的加分项。
回到题目本身，数组中的逆序对这道题最大的价值不在于背答案，而在于它把“排序”和“统计”两个看似无关的动作联系到了一起。我在实际做题中的体会是，只有当你亲手画过一遍归并合并的过程、亲手踩过一次long long溢出的坑，才能真正理解为什么归并解法是对的。如果看完这篇文章你能独立推导出mid - i + 1这个公式，而不是只记住了代码模板，那这题就算真正吃透了。最后再分享一个小技巧：遇到这类“求某种数对数量”的问题，先想想能不能利用有序性批量统计，这往往是通向最优解的那把钥匙。
