1. 从一道高频算法题说起逆序对到底在统计什么先说清楚“逆序对”是什么。给定一个数组nums如果存在两个下标i j满足nums[i] nums[j]那么(i, j)就是一个逆序对。比如[7, 5, 6, 4]里7比后面三个数都大贡献 3 对5比4大贡献 1 对6比4大贡献 1 对总共 5 个逆序对。这道题最朴素的想法就是双重循环外层固定一个数内层往后数有多少个比它小。代码不超过十行跑起来也直观。但我第一次在实际数据里跑这个暴力解法时直接被教育了数组长度一上10^5需要比较的次数是n*(n-1)/2也就是接近 50 亿次。哪怕主频再高、编译器优化再猛这个量级也要跑到十几秒甚至更久。业务接口根本等不起。所以当时我就知道逆序对这个统计问题不能靠暴力解必须找到一个O(n log n)级别的做法。归并排序就是其中一个非常自然的抓手——它本身在“分治”的过程中恰好能把逆序对“顺手”数出来。后来我又接触到树状数组解法两条技术路线本质都是借助“有序结构”来压缩比较次数但实现思路完全不同。这篇文章会围绕“归并”这个核心方法来拆解逆序对问题把原理、代码、坑位、性能实测一次讲透再补上树状数组方案作为对照。如果你正在刷算法题或者遇到“统计数组中顺序反转次数”这类业务需求这篇内容可以直接拿来抄作业。1.1 暴力双循环为什么撑不住大数组暴力写起来确实简单思路就是枚举所有i j的组合。伪代码大概是long long res 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j]) res; } }这段代码在n 1000时毫无压力在n 10000时还能勉强接受但一旦到了n 100000就是 50 亿次比较。按一秒钟跑 5 亿次简单整数比较来估算光是这个循环体就要 10 秒以上。如果比较里面再带点函数调用或者对象访问时间还会更高。更麻烦的是这个复杂度没法靠常数优化来救。你哪怕把循环体写得再精简指令数也就是几十条数量级摆在那里天花板非常低。所以我后来在团队里做数据量稍微大一点的统计需求时第一反应就是排掉所有O(n²)的写法不管它看起来多直观。还有一个隐藏问题容易被忽略暴力解法的结果可能直接超出int的范围。n 100000时最大逆序对数量是100000 * 99999 / 2 ≈ 5 * 10^9这已经超过 32 位整型上限了。所以哪怕只是练习计数变量也要用long long这个细节后面还会再讲到。1.2 现实场景里哪些问题本质上是在数逆序对逆序对不只是算法题里的概念它出现在很多看起来完全不相干的地方。比如排序算法的稳定性分析。一个“稳定排序”的意思是值相等的元素排序后保持原来的相对顺序。如果你想知道一组数据里有多少对元素的先后顺序是“反”的这个数字直接反映了数据的有序程度。逆序对数量为 0说明数组已经升序逆序对数量越大说明越接近降序。很多算法书籍用“逆序度”来描述数组的初始状态就是这个道理。再比如实时趋势统计。假设你有一个股票价格序列想统计“历史上每个交易日前有多少天价格比当前更高”本质上就是数这个序列里的逆序对。还有电商点击序列、游戏排行榜、日志时间戳反序列校验凡是“判断两个元素的相对顺序是否与预期相反”的场景都可以抽象成逆序对问题。我在实际业务里遇到过一个排行场景要给一批用户按积分排名积分相同的人要按注册时间先后排需求方要求统计“新旧顺序完全反掉”的记录数。听完需求描述我就意识到这不是什么玄学问题把一个数组转成排名字符串后数逆序对就行。数据量大概几十万暴力根本扛不住最后就是用归并方案几分钟跑完。2. 归并排序统计逆序对原理与一次合并的关键推导归并排序的分治过程是把数组一分为二递归排左边递归排右边然后把两个有序数组合并成一个有序数组。它的时间复杂度是O(n log n)空间复杂度是O(n)核心操作就是“合并”。逆序对的统计之所以能搭上归并这趟车是因为逆序对天然可以按“位置关系”分成三类两个下标都在左半部分、两个下标都在右半部分、一个在左一个在右。归并排序的递归恰好覆盖了前两类而“跨左右”这一类可以在合并阶段一次性数出来。2.1 逆序对天然分成三类归并排序刚好覆盖假设当前处理区间是[left, right]中点mid left (right - left) / 2。任何一对满足i j且nums[i] nums[j]的下标只可能是以下三种情况之一i和j都在[left, mid]属于左半内部逆序对i和j都在[mid 1, right]属于右半内部逆序对i mid j属于跨左右逆序对。递归调用mergeSort(left, mid)和mergeSort(mid 1, right)时返回值分别统计了前两类。而第三类不需要额外递归在把左右两个有序数组合并成一个大数组的过程中就可以计算出来。这就能保证“不重不漏”。任意一个逆序对总归逃不出这三种分类而每个分类都有且仅有一个统计时机。不存在一个逆序对被统计两次也不会漏掉任何一种。2.2 核心公式合并时为什么可以一次加上 mid - i 1这是整个归并解法最关键的一步。合并两个有序数组时左半用一个指针i右半用一个指针j。比较nums[i]和nums[j]把较小者放进辅助数组。当发现nums[i] nums[j]时说明当前右半指针指向的这个元素nums[j]比左半从i到mid的所有元素都要小。原因很简单左半已经有序了nums[i]是左半当前未放入辅助数组的最小值。既然最小值都比nums[j]大那左半后面那些元素自然也都大于nums[j]。这些元素对应的下标都比j小又都在右半指针指向的元素左侧所以它们与nums[j]之间每个都是一对逆序对。一次就能加mid - i 1个而不是一个一个加。if (nums[i] nums[j]) { cnt mid - i 1; // 左半从 i 到 mid 一共几个元素就贡献几对 temp[k] nums[j]; } else { temp[k] nums[i]; }这里很多人会问为什么nums[i] nums[j]时不把j右边那些元素也一起考虑因为j右边的元素比nums[j]更大或相等不会跟左半当前区间产生新的逆序对关系。而且j右边的元素放进数组时会继续跟左半剩下的元素比较到时候是新的比较关系属于后续统计范围不能提前算进去。2.3 手算 [7, 5, 6, 4] 验证不重不漏光看公式不够我建议初学者拿一个小数组完整走一遍合并过程。以[7, 5, 6, 4]为例设全局下标 0 到 3递归执行过程如下区间[0, 1]即[7, 5]。合并时7 5触发统计cnt 1 - 0 1 1。排序后变成[5, 7]。区间[2, 3]即[6, 4]。合并时6 4触发统计cnt 1。排序后变成[4, 6]。合并整个数组[5, 7]和[4, 6]。比较5和45 4统计cnt 1 - 0 1 2对应(5,4)和(7,4)两对接着比较5和65 6左指针右移再比较7和67 6统计cnt 1 - 1 1 1对应(7,6)一对。总计1 1 2 1 5跟暴力枚举结果一致。走完这个过程你才能真正理解为什么这个算法是可靠的。3. 完整代码实现C 和 Python3.1 C 标准写法含关键变量说明我在实际写这道题时习惯把辅助数组提出来作为类的成员变量避免递归过程中反复创建小程序数组。完整代码如下class Solution { public: long long reversePairs(vectorint nums) { int n nums.size(); temp.resize(n); return mergeSort(nums, 0, n - 1); } private: vectorint temp; long long mergeSort(vectorint nums, int left, int right) { if (left right) return 0; int mid left (right - left) / 2; long long cnt 0; cnt mergeSort(nums, left, mid); cnt mergeSort(nums, mid 1, right); int i left, j mid 1, k left; while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { cnt mid - i 1; temp[k] nums[j]; } } while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j]; for (int p left; p right; p) { nums[p] temp[p]; } return cnt; } };几个关键点说一下if (left right) return 0;是递归出口区间里没有元素或只有一个元素时不可能有逆序对。mid left (right - left) / 2这么写是为了防止left right整数溢出虽然本题数据规模大概率不会溢出但好习惯还是要养成。合并阶段用了nums[i] nums[j]作为走左半的条件等于时不统计保证严格大于才算逆序对。最后必须把辅助数组的内容拷贝回原数组否则下一层合并时用的就是未排序的数据统计逻辑就全乱了。3.2 Python 版本与细节差异Python 写起来更短但有几个很容易踩的坑。最典型的就是切片赋值会创建临时数组量级大时多出额外内存开销。我一般用循环赋值代码稍微长一点但更稳def reverse_pairs(nums): if not nums: return 0 temp [0] * len(nums) def merge_sort(left, right): if left right: return 0 mid (left right) // 2 cnt merge_sort(left, mid) merge_sort(mid 1, right) i, j, k left, mid 1, left while i mid and j right: if nums[i] nums[j]: temp[k] nums[i] i 1 else: cnt mid - i 1 temp[k] nums[j] j 1 k 1 while i mid: temp[k] nums[i] i 1 k 1 while j right: temp[k] nums[j] j 1 k 1 for p in range(left, right 1): nums[p] temp[p] return cnt return merge_sort(0, len(nums) - 1)Python 的递归深度默认是 1000归并排序的递归深度是log2(n)所以n 10^6时深度也就 20 左右不会碰到递归上限问题。但如果数据量到了千万级别或者你需要处理更深的调用链建议考虑改成自底向上的迭代式归并后面会提。3.3 工程化改进一次分配辅助数组等内容代码写对之后还要考虑工程上怎么让它跑得更快。我总结出三个实际投入过收益的优化点。首先辅助数组一次性分配到最大长度不要在递归函数内部每次创建。递归深度是log n每层的合并区间大小累加起来虽然是O(n)但如果你在每个递归子函数里new一个局部vector频繁分配内存的耗时非常可观。我的实测经验在n 10^6量级局部反复分配辅助数组比全局一次分配的版本慢 2 到 3 倍。其次可以在合并前加一个快速判断如果左半最后一个元素小于等于右半第一个元素说明左右两半整体有序不需要合并直接把后面接上去就行。这个优化在数组接近有序时收益特别大因为递归里大量区间已经有序省掉了大量无意义的比较和拷贝。if (nums[mid] nums[mid 1]) { return cnt; // 左右已经整体有序不用合并 }但这个优化不能在统计时偷懒只适用于真正有序的区间。因为这种情况下左右两半之间不存在任何逆序对直接跳过合并不会影响统计结果。第三最后拷贝回合可以用copy系列函数代替手写循环编译器在开-O2时往往能向量化拷贝减少逐元素搬运的开销。C 里可以写成copy(temp.begin() left, temp.begin() right 1, nums.begin() left);坚持用这几条优化后我在本地n 10^6随机数组上跑归并统计逆序对耗时大概是小几百毫秒级别。4. 另一个经典思路树状数组解法与离散化归并是分治思路的范本但很多场景下你会看到别人用树状数组Binary Indexed Tree解决同样的问题。这个方法同样能到O(n log n)而且代码结构往往更紧凑尤其是在配合离散化处理值域比较大的数组时。4.1 离散化把值域压缩到排名树状数组的本质是维护“前缀和”的快速查询与单点修改。用它统计逆序对的思路是倒序遍历原数组每遇到一个数就查询已经出现过的元素里有多少比它小。这个“比它小”的统计如果用值本身做下标会面临一个问题数组值可能很大比如10^9不可能开一个这么大的桶。解决办法就是离散化。把原数组复制一份排序去重每个元素在排序数组里的下标从 1 开始就是它的“排名”。这样值域就被压缩到n以内树状数组只需要开n 1的长度。离散化的核心步骤vectorint sorted(nums); sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());每个元素用二分查找lower_bound找到它在sorted中的位置作为树状数组的下标。4.2 树状数组统计逆序对的代码模板先写树状数组本身class BIT { private: vectorint tree; int n; public: BIT(int n) : n(n), tree(n 1, 0) {} void update(int i, int delta) { while (i n) { tree[i] delta; i i (-i); } } int query(int i) { int res 0; while (i 0) { res tree[i]; i - i (-i); } return res; } };统计逆序对的部分long long reversePairsWithBIT(vectorint nums) { vectorint sorted(nums); sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); int m sorted.size(); BIT bit(m); long long cnt 0; for (int i nums.size() - 1; i 0; --i) { int id lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin() 1; cnt bit.query(id - 1); bit.update(id, 1); } return cnt; }倒序遍历时已经update过的元素都是原数组中位置在右边的元素。bit.query(id - 1)查询的就是这些右边元素里值严格小于当前元素的个数。每次查询结果累加就是所有满足“右边元素小于左边当前元素”的逆序对数。4.3 归并 vs 树状数组怎么选两种做法我在实际中都测过简单整理一张对比表供参考维度归并排序树状数组时间复杂O(n log n)O(n log n)空间复杂O(n)O(n)理解难度分治理解曲线陡峭需要先掌握 BIT 原理代码长度中等较短是否修改原数组是否扩展性适合求逆序对改造成其他分治统计稍麻烦适合动态维护多个前缀统计扩展性强如果只是面试写题选哪种都行。我个人更推归并因为你写归并过程中顺手证明了“排序过程能顺带做统计”逻辑完整不容易被追问细节时卡壳。如果是在业务代码里做实时推荐的增量统计树状数组天然支持单点修改和前缀查询这种动态场景归并就不好使了。5. 高频坑位与排查经验这道题代码不长但踩坑的人特别多。我结合自己遇到的以及帮同事 review 时见过的典型问题整理成几个最容易翻车的点。5.1 整数溢出计数器必须用 long long这是最隐蔽也最要命的一个坑。n 100000时理论上最多有接近 50 亿个逆序对远超int上限。如果你用int cnt接收返回值结果溢出后可能出现负数或者莫名其妙的小值而且只在数据量够大时才触发特别难排查。我第一次踩这个坑是在本地测试n 100000的降序数组时暴力结果和归并结果对不上。排查了半天最后发现是int溢出。从那以后我写任何计数类逻辑只要数量级可能超过2^31 - 1统一用long long不给自己留隐患。5.2 相等元素的判定严格大于才算题目定义是nums[i] nums[j]等号不属于逆序对。在归并合并代码里判断条件写的是if (nums[i] nums[j])走左半反过来nums[i] nums[j]才统计。如果写成相等元素就会错误地触发统计结果偏大。在树状数组方案里也一样查询的是query(id - 1)也就是严格小于当前元素的数量。如果你写成query(id)等于自己的元素也会被算进去结果就不对了。5.3 递归边界与空数组处理基础条件left right要返回 0。很多人写成left right其实也变不出问题因为left不会大于right。但写更稳能防御异常参数。空数组是另一个容易被忽略的输入。题目如果允许空数组你的代码在n 0时应该直接返回 0。很多初学者会在排序原始数组或调用递归时对空数组做操作导致越界所以收手第一步先判空。5.4 为什么辅助数组要一次性分配这个问题我在第一部分提过但值得再强调一遍。归并排序的递归树每一层都有多个合并操作如果你在每个merge里都重新创建一个辅助数组总分配次数是O(n)量级每次分配还有可能触发内存申请和初始化极大拖慢整体性能。正确做法是把辅助数组定义成外层函数的局部变量或类成员递归调用时复用同一个数组。注意一点辅助数组里只有[left, right]区间内的数据是有效的其他地方是脏数据合并后拷贝回原数组时也要只拷对应区间别把脏数据带回去。6. 性能实测与应用扩展6.1 不同规模下的复杂度对比我拿不同规模的数据在本地做过一次粗略测试数据是随机生成的整数。暴力解在n 10^4时已经明显卡顿到n 10^5基本跑不动而归并排序在整个测试里都非常稳n 10^5大约毫秒级n 10^6也就几百毫秒。数组规模暴力 O(n²)归并 O(n log n)10^3瞬时瞬时10^4约 1 秒约 1 毫秒10^5几十秒约 10 毫秒10^6无法接受约 100-300 毫秒这个量级差距不是靠语言优化或编译器优化能弥补的必须换算法框架。6.2 相关变体题目与扩展思路掌握逆序对归并统计之后有几类变体题目完全可以沿用同一套分治思路计算“右侧小于当前元素的数量”返回一个数组表示每个元素右边有多少比它小的元素。这个在归并过程中记录每个原下标对应的统计结果即可。求“重要逆序对”要求nums[i] 2 * nums[j]。合并阶段比较的条件从nums[i] nums[j]改成nums[i] 2 * nums[j]统计时机可以拆到真正的合并操作之前。区间逆序对查询比如多次询问某个子数组的逆序对数这个基本要靠离线分治或莫队进一步处理但核心还是这里的合并统计思路。这些变体在实际面试中出现频率不低。核心方法论是一致的利用“有序”结构来减少无序空间的比较次数。6.3 面试笔试中的讲解节奏建议如果你是准备面试我建议按这样的顺序讲逆序对这道题先讲暴力解说明复杂度是O(n²)数据量一大就不可行。然后引导到归并逆序对分三类前两类递归处理第三类在合并时统计。讲清楚为什么合并时能一次累加mid - i 1这是整个思路的灵魂。最后分析复杂度并提一句注意long long的溢出问题。这个节奏大概 5 分钟能讲完思路完全自洽。面试官如果要深入大概率追问两个点一个是你怎么理解“不重不漏”一个是相等元素的处理。这两处在前面原理部分都覆盖了你能答上来就稳了。最后再分享一个小技巧我在实际写归并统计时有个习惯在递归合并前加一行if (nums[mid] nums[mid 1])的提前返回判断。当数组本来就有很多有序子区间时这行判断能省掉大量无意义的合并操作而且代码完全不影响统计正确性。对于接近有序的数据这个优化带来的提升特别明显。还有个容易被忽视的点是排序过程本身要保证稳定合并时相等元素优先取左半虽然逆序对统计结果跟稳定性无关但工程上保持稳定排序的习惯对后续扩展更友好。这个问题的两端一个是数学上对“逆序对”这个概念的理解一个是工程上对复杂度与内存的掌控。如果你能把归并这一套彻底吃透后面再去碰树状数组、线段树这类数据结构都会顺畅很多。逆序对看起来是个小问题但它串联起来的东西值得花时间认真打磨。