分治算法详解：归并排序统计逆序对的高效解法-育师

1. 题目到底在考什么：别被"交易"两个字带偏

先把这个题目本身说清楚。"分治(交易逆序对的总数)(6)"，我第一眼看到这行字的时候也愣了一下，什么交易？什么总数？其实这就是一道很经典的逆序对统计题，只不过在不同平台、不同题单里换了个马甲。你去翻剑指Offer，它叫"数组中的逆序对"；去LeetCode搜，是"LCR 170. 交易逆序对的总数"；在牛客或者洛谷，可能就叫"求逆序对"。名字怎么换都无所谓，核心问题只有一个：

给定一个长度为 n 的数组 nums，计算出有多少对下标 (i, j) 满足 i < j，且 nums[i] > nums[j]，最后把总数返回。

注意"交易"这两个字纯粹是题面包装——可能是某些平台把数组想象成交易记录的价格序列，逆序对就是"后一天价格低于前一天"的情况，去掉了包装，底子还是那个逆序对。我见过不少人在评论区被这种包装搞得一脸懵，以为是什么区块链、金融风控的题目，其实完全不是。

那为什么这个题值得单独拿出来写一份，而且还要专门强调分治？因为它是面试高频题，更是分治思想的一个绝佳样本。你说暴力也能做，两层循环 i 从 0 到 n，j 从 i+1 到 n，判断条件累加，思路三分钟就能写出来。但一旦 n 到 10^5 甚至 10^6 的规模，O(n^2) 的算法跑起来就是灾难。我看过不少初学者拿暴力代码去提交，大数据直接超时，心态瞬间崩掉。所以这个题真正的考点是：你能不能从暴力 O(n^2) 的思路里跳出来，用 O(n log n) 的分治法在排序的副产物中把逆序对数出来。

顺带说一句，题目里括号还有个"(6)"，这种编号通常表示这是某个专题训练里的第 6 题，比如"分治专题的第六道题"。这说明出题人希望你练习的就是分治这一块。包括热词里那些"分治法求一个n元素数组中最大元素的位置"、"四边形不等式优化dp 分治解法"，都是同一个专题下不同的问题——它们都在反复锤炼一个能力：把大问题拆成小问题，解决小问题，再合并结果。逆序对归并排序的写法，正是这个能力的集中体现。

2. 归并排序统计逆序对的底层原理：一次合并批量清算

2.1 先复习一下归并排序本身的"拆"与"合"

归并排序是分治思想的经典代言人。整个流程就两步：

拆：把数组从中间劈开，分成左右两半，然后递归地继续劈，直到每个子数组只有一个元素。一个元素当然是有序的，不需要排序。

合：从最小子问题开始向上回溯，把两个已经有序的左右子数组合并成一个更大的有序数组。

合并过程用双指针：i 指向左半部分开头，j 指向右半部分开头，比较 nums[i] 和 nums[j]，小的放进临时数组，然后对应指针后移。哪边先走完，就把剩下的一股脑拷贝进临时数组，最后把临时数组的内容覆盖回原数组对应区间。代码框架大概是下面这样：

void mergeSort(vector<int>& nums, int l, int r) { if (l >= r) return; int mid = l + (r - l) / 2; mergeSort(nums, l, mid); mergeSort(nums, mid + 1, r); merge(nums, l, mid, r); }

但如果你只是把归并排序写出来，这道题只能拿一半的分数——排序本身并不直接告诉你逆序对的数量，你得在"合"的过程里做文章。这里就是逆序对问题的精髓所在。

2.2 合并时的一次巧合：才发现逆序对可以"批量结算"

先说结论：逆序对的数量，可以在合并两个有序数组的时候顺手统计出来，不需要额外扫描。

关键点在于，递归到某层时，左右两个子数组内部都已经有序（这是归并排序的性质）。假设左半部分叫 L，右半部分叫 R，它们分别有序。那么任意一个 L 中的元素和 R 中的元素，它们之间的相对大小关系，恰好能反映跨左右两部分的逆序对数量。具体规则：

如果 L[i] <= R[j]，说明 L[i] 比当前 R[j] 小，它不会和 R[j] 构成逆序对，i 后移。
如果 L[i] > R[j]，那说明 L[i] 比 R[j] 大，而且因为 L 是有序的，L[i] 后面所有元素也都比 L[i] 大，自然也都比 R[j] 大。于是从 i 到 L 的末尾，这一整段全部和 R[j] 构成逆序对——一次就统计出一批逆序对，数量是 L长度减去 i 的位置。

你看明白这个逻辑的巧妙之处了吗？在暴力解法里，一个 R[j] 要和左边所有比它大的元素分别比较；但在归并排序里，因为 L 已经有序，一旦发现 L[i] > R[j]，就能确定 L[i]、L[i+1]……L[mid] 全都大于 R[j]，然后一口气累加 mid - i + 1 个数。单次比较引发的统计量从"1"变成了"一堆"，这就是 O(n log n) 的来源。

2.3 手算一遍：数组 [7, 5, 6, 4] 的完整推演

光说理论容易飘，我拿一个经典小数组走一遍完整流程。假设 nums = [7, 5, 6, 4]。

第一层拆：mid = 1，左半边 [7, 5]，右半边 [6, 4]。

左半边再拆：[7] 和 [5]，各自只有一个元素，不用再拆。合并 [7] 和 [5]：左指针在 7，右指针在 5。7 > 5，所以 7 这一整个左区间（只有一个元素）都和 5 构成逆序对，累加 1。合并结果是 [5, 7]。

右半边同理：[6] 和 [4]，6 > 4，累加 1。合并结果是 [4, 6]。

回到顶层，合并 [5, 7] 和 [4, 6]：

左指针指向 5，右指针指向 4。5 > 4，左区间从 5 开始到末尾 [5, 7] 都大于 4，累加 2。
右指针移到 6。5 <= 6，左指针右移到 7。7 > 6，左区间从 7 到末尾 [7] 都大于 6，累加 1。
右指针移到末尾，左区间还剩 [7]，全部拷贝。

三次合并共累加 1 + 1 + 2 + 1 = 5。验证一下原数组 [7, 5, 6, 4] 的逆序对：(7,5)、(7,6)、(7,4)、(5,4)、(6,4)，确实是 5 对，一个不多一个不少。注意顶层合并时一次累加 2 的效果——这就是"批量结算"的直观感受。

2.4 为什么这个算法是 O(n log n) 而不是 O(n^2)

归并排序每一层合并的总工作量是 O(n)，因为每一层的所有区间加在一起恰好覆盖整个数组长度 n；而数组被递归拆分成 log n 层（每次折半）。所以总复杂度 O(n log n)。

相比暴力的 O(n^2)，当 n = 10^5 时，暴力要比较大约 10^10 次，归并排序只要大约 10^5 × 17 次，差距接近六个数量级。这也是为什么所有高效逆序对解法都离不开分治或者树状数组这类低复杂度框架——不是技巧炫技，是数据规模逼着你必须这么做。

3. 代码落地：C++ 和 Python 两版实现的关键差异

3.1 C++ 版：注意临时数组的作用域和引用传递

C++ 写这个题，最稳妥的姿势是直接在递归函数内部维护一个临时数组，或者作为成员变量复用。我推荐在类里开一个全局的 temp 数组，避免每次递归都 vector 拷贝导致额外的 O(n log n) 内存开销和拷贝耗时。核心代码直接给出来：

class Solution { private: vector<int> temp; long long mergeCount(vector<int>& nums, int l, int r) { if (l >= r) return 0; int mid = l + (r - l) / 2; long long cnt = 0; cnt += mergeCount(nums, l, mid); cnt += mergeCount(nums, mid + 1, r); int i = l, j = mid + 1, p = 0; while (i <= mid && j <= r) { if (nums[i] <= nums[j]) { temp[p++] = nums[i++]; } else { cnt += mid - i + 1; // 关键：批量累加 temp[p++] = nums[j++]; } } while (i <= mid) temp[p++] = nums[i++]; while (j <= r) temp[p++] = nums[j++]; for (i = l, p = 0; i <= r; ++i, ++p) { nums[i] = temp[p]; } return cnt; } public: long long reversePairs(vector<int>& record) { temp.resize(record.size()); return mergeCount(record, 0, record.size() - 1); } };

注意我用了 long long 作为返回类型，这个细节下面专门说。还有递归函数里cnt += mergeCount(...)这两个递归调用必须写在"合并前"还是"合并后"没区别，因为左右两侧内部的逆序对已经在它们的合并阶段统计完了，我们只需要保证顶层合并前左右各自有序即可。顺序不影响正确性。

3.2 Python 版：优雅但注意递归深度

Python 写分治通常比 C++ 松弛一些，但有两个坑必须提前规避：一是temp列表的传递方式，二是递归深度。

class Solution: def reversePairs(self, record: List[int]) -> int: nums = record n = len(nums) temp = [0] * n def merge_sort(l: int, r: int) -> int: if l >= r: return 0 mid = (l + r) // 2 cnt = merge_sort(l, mid) + merge_sort(mid + 1, r) i, j, p = l, mid + 1, l while i <= mid and j <= r: if nums[i] <= nums[j]: temp[p] = nums[i] i += 1 else: cnt += mid - i + 1 temp[p] = nums[j] j += 1 p += 1 while i <= mid: temp[p] = nums[i] i += 1 p += 1 while j <= r: temp[p] = nums[j] j += 1 p += 1 for k in range(l, r + 1): nums[k] = temp[k] return cnt return merge_sort(0, n - 1)

Python 里temp直接闭包引用外层的 list，不需要重新赋值。递归深度要注意：当 n 很大时，Python 默认递归深度是 1000，归并排序递归深度是 log n（约 17~20），所以纯递归没问题。但如果你把递归改成 while 模拟，或者某些极端写法里递归深度变成 O(n)，就会碰 RecursionError。归并排序天然深度 O(log n)，所以这点其实很安全。

3.3 为什么合并时必须做"稳定排序"式的 <= 判断

代码里用的是if nums[i] <= nums[j]，注意这里的等号。有人会问：改成严格小于nums[i] < nums[j]行不行？

分情况讨论。如果是求逆序对，题目定义是 nums[i] > nums[j] 才算一对，相等不算。那么合并时如果左指针的值等于右指针的值，应该让左指针先走（即 nums[i] <= nums[j] 时走左指针），这样相等元素不会被误判为逆序对。这是稳定性的要求，也决定了排序后相等元素相对顺序不变。如果你把判断条件改成严格小于，一旦相等元素出现，右指针可能先走，导致它被错误地统计进逆序对里。

我当初第一次写的时候就用错了条件，结果测试数组 [1, 2, 1, 1] 一直多算两对，排查了很久才意识到是等于号的问题。这个细节虽然一行，但足以让整道题全错。

4. 边界问题、取模陷阱与调试心得

4.1 数据范围为什么逼你用 long long

逆序对的最大数量是 C(n, 2) = n × (n-1) / 2。如果 n = 10^5，最大逆序对数大约是 5 × 10^9，远超 int 的 2^31 - 1（约 2.1 × 10^9）。所以只要你用 int 存结果，在最坏情况（数组严格降序）下必然溢出，提交就会得到莫名其妙的错误答案。

我的建议是：不管题目数据范围写没写，一律用 long long。30 位以内够用吗？如果 n 是 10^9 量级，long long 也扛不住，但那种规模通常不会用归并排序硬做。工程上，long long 是逆序对题型的默认安全选择。C++ 里注意mid - i + 1这个表达式的类型，i 和 mid 是 int，但它们参与累加时编译器会自动提升到 long long，所以只要 cnt 是 long long 就没问题。

Python 读者倒是不用担心溢出——Python 的 int 是任意精度。但 C++ 就得老老实实写对类型，这是初学者最容易忽略又最致命的地方。

4.2 取模要求的处理：不是最后取一次就完事

有些版本的题目要求返回结果对 1000000007 取模（比如某些大厂笔试题变体）。这时候有个坑：不能只在 return 前取模。因为在递归中途，cnt 可能已经越过 int 甚至 long long 的范围，导致提前溢出，最后取模也救不回来。

正确做法有两种：

整个 cnt 都全程用 long long，中途不做任何取模，只在最终 return 前取模。这要求 n 不太大，long long 能全程装下最大值。
如果 n 特别大（比如 10^6 以上），在累加时每加一次就取一次模，也就是cnt = (cnt + mid - i + 1) % MOD。

但千万注意第二种做法里，返回值本身是取模后的，而取模后的 cnt 再参与递归统计是安全的，因为逆序对数量只做加法，取模满足加法交换律和结合律。不过有个问题：如果中途取模，递归排序时的比较大小判断不受影响，因为排序只关心元素值，不关心计数。所以两种做法正确性都没问题，区别是性能：每步取模有一点点额外开销，但可以接受。

我个人的经验是：能不取模就不取模（肝语言特性题时），但如果题面写了取模，简化起见还是在累加的同时每一步用cnt = (cnt + ...) % MOD，省得最后忘了。

4.3 合并边界最容易翻车的地方

递归出口是 l >= r，不是 l == r。因为某些写法 mid 计算可能让区间划分出问题，虽然归并排序通常不会导致 l > r，但二手习惯：任何递归都写成if (l >= r) return;更安全。

循环条件while (i <= mid && j <= r)里的等号必须写。漏掉等号会导致左右区间剩余元素没有被处理完，虽然排序结果可能还是对的（因为后面有两个 while 兜底），但对逆序对统计来说，漏掉的元素可能是逆序对——尤其在右指针 j 走完后，左指针剩余元素不会额外产生新的逆序对，因为在前面循环里该统计的已经统计完了。如果你漏了等号导致提前跳出，前面循环少执行了一次，"该在循环里统计的逆序对"可能刚好漏掉。

还有 mid 的计算要用l + (r - l) / 2，不要用(l + r) / 2。虽然对普通小数组这俩没区别，但 l + r 在极端边界（r 接近 INT_MAX）时可能溢出，养成本能性写前者能避免很多潜在 bug。这种"看起来等价但实际有坑"的细节最容易在面试手撕代码时翻车。

4.4 对数器验证：别急着提交，先暴力对拍

写算法题，我发现最有效的自检不是静态读代码，而是写一个暴力解法和自己的高效解法做对拍。随机生成小数组（长度 1 到 10，元素数值范围 -100 到 100），各跑 1000 次，比较两种结果是否一致。

对拍器代码很简单，我通常直接在主函数里跑随机测试：

bool test() { Solution s; for (int t = 0; t < 1000; ++t) { int n = rand() % 10 + 1; vector<int> a(n); for (int i = 0; i < n; ++i) a[i] = rand() % 201 - 100; vector<int> b = a; int ans1 = s.reversePairs(a); int ans2 = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (b[i] > b[j]) ans2++; if (ans1 != ans2) return false; } return true; }

这个对拍器几乎能抓住 90% 以上的边界问题：负数、相等元素、空数组、单元素数组全都能测到。我第一次写逆序对的时候就是靠它发现<=条件错误的。真的强烈建议每个人都养成这个习惯，尤其是分治、递归这类容易小边界出错的题型。

5. 从逆序对看分治思维：相关变体与工程启发

5.1 同源问题：分治法求数组最大元素的位置

热词里的"分治法求一个n元素数组中最大元素的位置"和逆序对是同一个专题的两道兄弟题。思路也是拆成左右两边，分别求左边最大值的位置和右边最大值的位置，再比较两个最大值谁更大，谁就是全数组最大值。代码核心长这样：

int findMaxPos(vector<int>& nums, int l, int r) { if (l == r) return l; int mid = l + (r - l) / 2; int leftPos = findMaxPos(nums, l, mid); int rightPos = findMaxPos(nums, mid + 1, r); return nums[leftPos] >= nums[rightPos] ? leftPos : rightPos; }

这个题很直白地展示了分治的最小化思想：先递归到单元素，再在每层合并时"比较并选出胜者"。和逆序对的区别在于，最大元素位置在合并时只需要常数次比较，而逆序对在合并时利用有序性做了批量统计。但两者的递归骨架完全同源，你先学会其中一个，另一个几乎就是顺手的事。

5.2 树状数组解法：另一种统计逆序对的思路

分治不是唯一解法。逆序对还能用树状数组（Fenwick Tree）做，原理是"离散化 + 顺序扫描 + 前缀查询"。大致思路：把数组元素离散化成排名，然后从左往右扫描，每遇到一个元素，就查询已经扫描过的元素里比它大的数量，然后把它自己加进树状数组。这里查询和修改都是 O(log n)，总复杂度同样是 O(n log n)。

两种解法怎么选？归并排序版不依赖离散化，适合直接处理，而且分治思想更容易在面试中现场讲清楚；树状数组版代码更短（大约 20 行），但引入离散化和树状数组两个额外概念，如果面试官让你现场证明正确性，解释成本更高。我一般建议：面试首选归并排序，因为写法天然和分治专题契合；工程或比赛里如果对线段树、树状数组更熟，用树状数组成熟度更高。别贪多，先把归并排序版本写到肌肉记忆级别。

5.3 变体：翻转对（LeetCode 493）

另一个常见变体是 LeetCode 493 "翻转对"：统计 i < j 且 nums[i] > 2 * nums[j] 的对数。归并排序同样适用，但注意合并时不能直接在排序比较里统计——因为条件带了一个 2 倍关系，你不能只在nums[i] <= nums[j]的分支里顺手统计。处理方式是在合并前对左区间依次查找右区间中有多少元素满足 nums[i] > 2 * nums[j]，也就是一个额外的双指针扫描，然后再做正常的合并排序。这个变体进一步说明：归并排序的框架是灵活的，真正难点在于"统计什么、在哪个阶段统计"。

5.4 工程上的启发：合并阶段的"增量信息"

从逆序对这个题里，我最想分享的一点是：分治不是单纯把问题拆开再拼回去，而是要在合并阶段捕捉那些"只有合并才能看清的增量信息"。

暴力的逆序对统计为什么会慢？因为它每一次比较都是孤立的，没有任何信息可以被复用。归并排序之所以快，是因为排序让左右区间的内部结构变得有序，于是"某个右元素比多少个左元素小"这个问题，从一个一个数，变成了"左区间剩余长度"这个 O(1) 的结论。本质上，排序产生的有序性就是一种可以被复用的"数据预处理"信息。

我在实际工作里其实不太会手写归并排序——大多数语言自带 sort。但分治思想本身到处都有：git merge 的过程是分治合并，SQL 的归并连接是分治外排，分布式系统里 MapReduce 的 shuffle 阶段也是大排序拆成小排序再合并。搞懂逆序对这一道题，你不仅刷了一道算法题，还理解了一个非常底层的计算机思维模式：先让局部有序，再让局部之间的比较变得廉价。