反向归并求解逆序数：基于归并排序的另一种高效实现

在算法题和日常编码里统计一个数组中“位置靠前、数值却更大”的元素对数量是一个非常常见的小需求。这个数量有个专门的名字叫逆序数也有人叫它逆序对。求逆序数最出名的手段就是借归并排序的合并过程顺手做掉复杂度稳定在 O(n log n)。但今天我想分享的是一种不同于标准方法的基于归并排序的逆序数计算代码不按常见的“取右半元素时累加左半剩余”来而是反过来从右往左合并每次取左半元素时累加右半剩余元素个数。文章会把原理、代码、验证和坑一次讲透适合刚学完归并排序、想理解逆序数本质或者准备算法面试的朋友参考。1. 先弄明白逆序数到底在数什么1.1 一句话定义加一个例子正式一点说对于数组 a如果 i j 且 a[i] a[j]那么数对 (i, j) 就叫一个逆序对数组中所有逆序对的数量就是逆序数。比如数组 [5, 3, 2, 4, 1]肉眼扫一遍能把逆序对都列出来以 5 开头后面 3、2、4、1 都比它小有 4 个以 3 开头后面 2、1 比它小有 2 个以 2 开头后面 1 比它小有 1 个以 4 开头后面 1 比它小有 1 个1 后面没有元素。合计 8 个。这个 8 就是数组 [5, 3, 2, 4, 1] 的逆序数。从定义能直接读出两个关键信息逆序对只看“严格大于”两个相等的元素永远不构成逆序对逆序对强调“原数组里的相对位置”位置靠前但数值更大的元素配对才叫逆序。这两点看起来简单却决定了后面所有代码里比较条件怎么写。很多人在归并排序统计逆序数时把结果算多十有八九就是比较条件里混入了“等于”的情况。1.2 逆序数在真实场景里能做什么可能有人觉得这只是刷题时的玩具概念实际用处其实不少。第一个是很直观的有序度度量逆序数为 0 表示数组完全升序逆序数为 n(n-1)/2 表示完全降序夹在中间的数值能直接告诉我们数据乱到什么程度。第二个有意思的点是冒泡排序里交换元素的次数恰好等于逆序数所以分析冒泡排序在最坏和最好情况下的性能归根到底就是在分析输入数据的逆序数。第三个用处是对稳定性敏感的排序场景做输入评估比如外部排序、数据压缩里计算相邻差值的冗余度都会用到类似的概念。可以说逆序数就是一把衡量“乱序程度”的尺子。理解冒泡排序和逆序数的关系对后续推导很有帮助。冒泡排序每交换一次相邻的逆序对都会让整个数组的逆序数减少 1等逆序数降到 0数组就排好了。所以交换次数和初始逆序数是严格相等的。这个等价关系也是很多排序算法分析题的入口值得顺手记下。1.3 暴力做法为什么撑不住最容易想到的写法是两层循环外层定 i内层扫 j只要 a[j] a[i] 就把答案加一。代码短思路直白但代价是 O(n^2) 的时间复杂度。当 n 只有几百的时候完全无所谓可一旦 n 涨到 10^510^5 的平方是 10^10 量级普通计算机跑一遍就是几十秒起步根本没法接受。而逆序数问题在很多场景里恰恰要处理这种规模甚至更大的数据所以必须找一个 O(n log n) 级别的算法。归并排序正是最经典的那条路。2. 标准思路先走一遍经典的正向归并累加2.1 归并排序为什么天然能统计逆序数归并排序是分治思想的标准产物。把数组从中间切开左边和右边分别排好序之后整个数组的逆序数就由三块组成左半部分内部的逆序数右半部分内部的逆序数以及一个元素在左半、一个元素在右半的“跨区逆序数”。前两块靠递归解决第三块在合并两个有序子数组的时候顺手统计。合并过程为什么能统计跨区逆序数关键在于两个子数组都是有序的。假设当前左边指针指向的元素是 x右边指针指向的元素是 y。如果 x y说明 x 比 y 小直接把 x 放进结果数组。如果 x y说明 y 比左边剩余的所有元素都小因为左边剩余的元素都大于等于 x自然也都大于 y又因为左边剩余元素在原数组中的位置都在 y 之前那么 y 和左边每一个剩余元素都能组成逆序对。此时需要累加的数量就是左边剩余元素的个数。2.2 标准 C 语言实现与要点先看代码这段是很多算法教材里的标准写法我习惯把它叫“正向归并统计”long long mergeSortCount(int arr[], int tmp[], int l, int r) { if (l r) return 0; int mid l (r - l) / 2; long long inv 0; inv mergeSortCount(arr, tmp, l, mid); inv mergeSortCount(arr, tmp, mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (arr[i] arr[j]) { tmp[k] arr[i]; } else { tmp[k] arr[j]; inv mid - i 1; // 左边剩余的元素个数 } } while (i mid) tmp[k] arr[i]; while (j r) tmp[k] arr[j]; for (int p l; p r; p) arr[p] tmp[p]; return inv; }调用前先准备好一个和 arr 等长的临时数组 tmp递归过程中不要每次分配内存否则频繁申请释放会引入不必要的性能开销。返回值用 long long 而不是 int原因后面第 5 部分专门说。这里比较条件是 arr[i] arr[j]也就是相等时取左边这样排序是稳定的也保证不会把相等元素错算成逆序对。2.3 用例子走一遍验证它真的对还是拿 [5, 3, 2, 4, 1] 来验证。递归到最底层先合并左半 [5] 和右半 [3]比较时 5 3取右边 3此时左边剩余元素只有 5 一个inv 加 1得到逆序对 (5,3)。接着往上合并 [3,5] 和 [2]取右边 2 时左边剩余两个元素inv 加 2对应 (3,2) 和 (5,2)。右侧 [4] 和 [1] 合并时取 1左边剩余一个 4inv 加 1得到 (4,1)。最后合并 [2,3,5] 和 [1,4]取右边 1 时左边剩余 3 个inv 加 3对应 (2,1)、(3,1)、(5,1)取右边 4 时左边剩余 1 个就是 5inv 加 1得到 (5,4)。把递归过程中所有增量加起来正好是 8和前面手算完全一致。这段验证其实也说明了核心逻辑标准方法里所有的逆序对增量都发生在“把右边元素放到结果数组”的那一刻。因为右边元素一旦小于左边剩余元素它就和左边剩余的全部元素构成逆序对。3. 另一种思路反向归并取左半时累加右半剩余3.1 从右往左合并统计逻辑正好反过来标准方法的统计动作发生在“取右半元素”的时候。那一个自然的疑问就来了能不能把统计动作放到“取左半元素”的时候当然能只要把合并方向调转。标准归并是从两个有序子数组的头部开始每次取较小的元素放到结果数组前面。反向归并则反过来从两个子数组的尾部开始每次取较大的元素放到结果数组的尾部。这样做完结果数组依然是升序只是元素被填充的顺序变了。既然填充顺序变了统计时机也就可以对应地改变每当我们决定取左半元素时说明左半当前这个元素比右半当前最大剩余元素还大于是右半剩余的所有元素都会和它构成逆序对。这就是标题里说的“另一种不同于标准方法的基于归并排序的逆序数计算代码”的核心思想。3.2 反向归并统计的代码实现代码与标准写法对称但方向相反注意指针初始位置和移动方向long long mergeSortCountReverse(int arr[], int tmp[], int l, int r) { if (l r) return 0; int mid l (r - l) / 2; long long inv 0; inv mergeSortCountReverse(arr, tmp, l, mid); inv mergeSortCountReverse(arr, tmp, mid 1, r); int i mid; // 左半尾部 int j r; // 右半尾部 int k r; // 结果数组尾部 while (i l j mid 1) { if (arr[i] arr[j]) { tmp[k--] arr[i--]; inv j - mid; // 右半剩余元素个数 } else { tmp[k--] arr[j--]; } } while (i l) tmp[k--] arr[i--]; while (j mid 1) tmp[k--] arr[j--]; for (int p l; p r; p) arr[p] tmp[p]; return inv; }这段代码里tmp 的长度如果按整个数组 n 来申请k 就从 r 递减到 l如果你只想申请区间长度 r-l1把 k 初始值改成 r-l 也能跑只是下标映射要仔细。注意这里的比较条件是严格大于 arr[i] arr[j]不能用 原因下面单独说。3.3 核心推导为什么加的是右半剩余不是右半已取出这里是我实际写这段代码时栽过跟头的地方值得展开讲。第一次写反向归并时我下意识以为逆序对的数量应该等于“右半已经取出的元素个数”因为那些元素看起来是被左半当前元素“压”到后面去的。一验证就发现结果是错的。原数组 [3, 1] 这一组在最底层的合并里反向归并从尾部取最大元素右半只有一个元素 1第一轮比较时左半尾部 3 大于右半 1于是取左半 3此时右半“已经取出”的元素个数是 0而右半“剩余”的元素个数是 1。可是 (3, 1) 恰恰构成一个逆序对所以加 0 一定是错的必须加剩余个数也就是 j - mid。换个角度重新推导一遍当 arr[i] arr[j] 成立时左半当前元素已经大于右半当前指针指向的最大剩余元素因此右半剩余的所有元素都比 arr[i] 小。这些元素在原数组中都位于 arr[i] 的右侧且数值更小每一个都能和 arr[i] 组成逆序对。所以累加量是右半剩余数量也就是 j - mid而不是已经取出的数量 r - j。这个因果关系想清楚之后代码就不容易写错了。很多博客和题解只给代码不给推导才让“另一种方法”看起来很玄乎其实它就是标准归并统计的镜像版本。3.4 稳定性要说清楚别踩坑反向归并的统计逻辑依赖严格大于这个条件。如果改成 arr[i] arr[j]遇到相等元素时会取左半并累加右半剩余数量可相等元素并不构成逆序对结果就多算了。所以统计版本必须用严格大于。代价是相等时优先取右半破坏了稳定排序的特性。对纯逆序数计算完全没有影响反正相等的两个数本来就不该计入但如果这段代码以后还要兼职当稳定排序用那还是老实回到标准正向写法更省心。我在项目里一般会把“统计逆序对的归并”和“普通稳定排序”拆成两个函数各干各的避免日后面临稳定性问题。提示判断自己写的反向归并是否正确最快的方式就是拿 [3, 1] 和 [1, 3, 2] 这种小数组手推一遍。只要 [3, 1] 能得到 1[1, 3, 2] 能得到 1基本逻辑就对了。4. 索引归并法不动原数组也能算逆序数4.1 思路与适用场景有的场景里原数组不能改。比如数组元素是很大的结构体每次拷贝开销高或者原数组排序后还要用于其他流程再或者调用方要求函数不产生副作用。这时候可以对下标排序而不是对元素排序。思路是把下标 0 到 n-1 放进一个 idx 数组归并时比较 arr[idx[i]] 和 arr[idx[j]] 的大小移动的是下标。这样原数组始终没动最后只知道“排完序后应该是什么样的下标顺序”同时也能算出逆序数。这种“索引归并法”在工程里很有用。C 语言里交换大结构体的成本远高于交换一个 int 下标所以很多排序库内部也是先排索引数组再按索引回填数据。逆序数统计虽然更轻量但同理如果你只是想知道乱序程度并不想把数组本身搅乱索引归并是最舒服的解法。4.2 索引归并统计的实现long long mergeSortCountByIndex(int arr[], int idx[], int tmp[], int l, int r) { if (l r) return 0; int mid l (r - l) / 2; long long inv 0; inv mergeSortCountByIndex(arr, idx, tmp, l, mid); inv mergeSortCountByIndex(arr, idx, tmp, mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (arr[idx[i]] arr[idx[j]]) { tmp[k] idx[i]; } else { tmp[k] idx[j]; inv mid - i 1; } } while (i mid) tmp[k] idx[i]; while (j r) tmp[k] idx[j]; for (int p l; p r; p) idx[p] tmp[p]; return inv; }调用方法初始设置 idx[i] i再传一个等长的 tmp 数组。由于 tmp 里存的是下标而不是原值回写的时候也是回写到 idx不是 arr。统计逻辑和标准正向归并完全一致取右半下标时左边剩余下标对应的元素都更大且在左侧满足逆序对定义。arr 全程只读这一点在函数签名上也能体现。提示索引归并里 arr 不会变化只有 idx 和 tmp 在变。如果你连 idx 都不想污染那再加一层拷贝即可不过会多一份内存开销实际用到的场景比较少。4.3 三种思路放在一起看定位标准正向是思维起点适合绝大多数算法题反向归并是标准方法的镜像适合加深理解也能在面试里展示思路的灵活性索引归并对原数组零侵入适合工程代码。三种方案本质都在做同一件事利用归并排序合并有序区间时“左半剩余 / 右半剩余”的可计数性把跨区逆序对一次性数完。区别只在于取数方向、统计时机、排序对象不同。理解了这一点以后再遇到类似题目比如“右侧小于当前元素的个数”这种变体你会很快意识到它们其实是同一个模型的不同映射。有一说一如果只是想快速拿结果标准正向归并永远是首选索引归并和反向归并更像是在不同约束条件下的变体。正是因为经历了从“标准”到“反向”再到“索引”这三步我对归并过程里指针和剩余数量的关系才算真正吃透。5. 三种写法的复杂度、坑点与选型建议5.1 先说结论复杂度其实一模一样先给一个定心丸三种写法的时间复杂度都是稳定的 O(n log n)空间复杂度都是 O(n)。原因也很简单它们本质上都是归并排序每一层递归要访问 n 个元素递归深度是 log n 层所以时间上是 n log n每次归并都依赖一个 n 大小的临时数组所以空间上是 O(n)。递归调用本身有 O(log n) 的栈空间在大 O 分析里通常不单独算进主项实际工程中也不会因为这个栈深度出问题。下面这个表可以直接拿去对照写法时间复杂度空间复杂度是否修改原数组相等元素处理标准正向归并O(n log n)O(n)会修改 arr相等时取左半稳定反向归并O(n log n)O(n)会修改 arr严格大于取左半统计正确但不稳定索引归并O(n log n)O(n)只修改 idxarr 只读相等时取左半下标稳定5.2 稳定性对逆序数统计的影响逆序数只关心严格大于所以排序本身是否稳定并不会改变正确答案。真正会出错的是合并内部比较条件写得不干净。标准正向里如果写成 arr[i] arr[j]取右边的条件就变成 arr[i] arr[j]相等元素会被当成右半更小照样多算逆序对反向归并如果用大于等于取左半也会多算。所以稳定的不只是排序过程更是“严格大于”这个判断。写代码时可以记住一句话逆序对永远只在左大于右的时候产生比较条件里不能出现等于。我见过不少初学者以为归并排序统计逆序数不准最后定位下来都是比较条件的问题而不是算法框架的问题。遇到“统计结果偏大”的 bug优先检查所有比较符号尤其是相等情况。5.3 我自己的选型经验刷题和面试讲思路我默认用标准正向归并它最直观代码也不容易写错。如果面试官问还有没有别的思路我会把反向归并讲一遍重点讲清楚为什么累加右侧剩余而不是已取出这能体现你对归并过程的理解层次。工程代码里如果调用方不介意原数组被改我也用标准正向一旦原数组有其他用途或者元素是大结构体就切换到索引归并。Java 语言里原理完全一样把 C 代码里的指针和下标翻译成 Java 数组操作就行归并排序本身不绑定语言。另外无论选哪一种我强烈建议统一用 long long 做返回类型和累加变量。逆序数的最大值是 n(n-1)/2当 n 等于 10^5 时大约是 5 x 10^9已经超出 32 位 int 的范围了。用 int 存数据一大就翻车这种问题还特别难查因为小数据时一切正常。6. 常见问题与排查技巧实录6.1 典型问题速查表写这类代码最容易遇到的几个坑我整理成了一张表排查时可以直接对号入座现象可能原因解决办法数据一大结果变负数int 溢出返回值和累加变量改 long long统计值比真实值大比较条件出现等于正向用 取左反向用严格 取左统计值偶尔对偶尔错临时数组未回写合并结束后把 tmp 区间拷回 arr 或 idx递归调用栈溢出递归实现不适合极端环境改用自底向上迭代归并原数组排序后被改坏函数副作用用索引归并arr 保持只读6.2 自测方案随机对拍与边界用例我调试这类归并代码时几乎不靠肉眼方法就两个字对拍。写一个暴力 O(n^2) 的 countBrute 函数再写一个随机数组生成器循环几千组小规模数据n 从 1 到几十两边结果比对任何差异都能在秒级暴露。边界用例直接固定测三个升序数组 [1, 2, ..., n]期望逆序数 0严格降序数组期望 n(n-1)/2全相等数组期望 0。这三个用例能过滤掉绝大多数“相等元素多算”和“指针边界写错”的问题。尤其要注意全相等数组这一条。有些实现会在相等时取右半并累加结果把 0 跑成很大的数也有些实现对重复元素处理不一致导致结果依赖数据分布。固定跑一遍全相等用例能帮你很快确认“严格大于”的语义有没有贯彻到底。6.3 Python 快速验证版如果只是想验证算法思路用 C 写一轮比较费劲Python 完全可以快速跑通。这里给出标准正向版和反向版的核心代码。def count_inv(arr, l, r): if l r: return 0 mid (l r) // 2 inv count_inv(arr, l, mid) count_inv(arr, mid 1, r) tmp [] i, j l, mid 1 while i mid and j r: if arr[i] arr[j]: tmp.append(arr[i]) i 1 else: tmp.append(arr[j]) j 1 inv mid - i 1 tmp.extend(arr[i:mid 1]) tmp.extend(arr[j:r 1]) arr[l:r 1] tmp return inv def count_inv_reverse(arr, l, r): if l r: return 0 mid (l r) // 2 inv count_inv_reverse(arr, l, mid) count_inv_reverse(arr, mid 1, r) i, j mid, r tmp [0] * (r - l 1) k r - l while i l and j mid 1: if arr[i] arr[j]: tmp[k] arr[i] inv j - mid i - 1 k - 1 else: tmp[k] arr[j] j - 1 k - 1 while i l: tmp[k] arr[i] i - 1 k - 1 while j mid 1: tmp[k] arr[j] j - 1 k - 1 arr[l:r 1] tmp return invPython 版写得直白重点是方便跑对拍。先写一个暴力函数然后对随机数组循环验证两个版本确认结果一致再翻译成 C 或 Java思路会清晰很多。6.4 想继续玩可以往哪个方向改到这里另一种不同于标准方法的归并排序逆序数代码已经完整了。剩下的扩展方向可以玩很多把递归改成自底向上的迭代归并避开系统栈限制把两路归并改成多路归并为外部排序打基础或者把“逆序数”推广到“每个元素右侧比它小的个数”这正好是很多在线评测系统里的进阶题。我自己的习惯是每次学一个新算法都会顺手写一个暴力对拍版本留下来下次再遇到类似题目直接复用。归并排序本身不难难的是把合并过程里的数量关系想清楚一旦想通标准方法和反向方法就只是同一枚硬币的两面。