1. 题面与第一直觉暴力解法为什么撑不过大数据很多人第一次接触归并排序时都把它当成一个普通排序算法来学分两半分别排好再合并。这个理解当然没错但总觉得少了点味道。直到遇到逆序对个数这道题我才真正感受到归并排序的精华不在排序本身而在分治过程中能顺手统计出很多信息。逆序对的定义非常简单给定一个数组如果存在下标i j且a[i] a[j]那么(a[i], a[j])就算一个逆序对。换句话说就是前面某个数比后面某个数大位置和大小关系相反了。比如数组[3, 1, 2]中(3,1)和(3,2)是逆序对(1,2)不是总共 2 个。初学者最容易想到的做法是两层循环枚举所有i j逐个比较复杂度显然是 O(n^2)。当n只有几千时问题不大可一旦n到了十万、百万级别这种写法就会直接超时不仅在线判题系统会卡住真实业务场景里处理大规模序列时也完全不可用。暴力解法的瓶颈在于它浪费了大量重复比较。举个例子[5,4,3,2,1]这个完全逆序的数组逆序对总数是5 * 4 / 2 10而两层循环确实会比较所有 10 对组合。问题是如果数组已经分成前后两段且两段内部各自有序那么统计两段之间的逆序对时完全没必要一个接一个地比可以通过批量的方式一次算出很多对。这个批量的思维正是归并排序解法能降到 O(n log n) 的关键。还有一个值得留意的直觉逆序对的数量等于把一个数组通过相邻交换变成有序数组所需的最少交换次数。冒泡排序每交换一次相邻逆序元素恰好消掉一个逆序对所以它的交换次数就等于逆序对个数。这个等价关系说明逆序对不仅是数大小关系它天然对应着一种操作代价在求最小交换次数或排序代价的题目里经常冒出来。2. 归并排序分治框架里的计数玄机2.1 计数时机不是归并后再数而是归并时就数归并排序的核心是分治把数组从中间分成左右两半递归排序然后合并两个有序子数组。如果把统计逆序对和归并排序结合起来最直接的想法是先递归统计左右两半内部的逆序对再做一次全数组范围的统计。但这个全数组范围的统计如果又用两层循环复杂度还是 O(n^2)等于白干。真正的做法是把计数嵌入merge过程当合并两个有序子数组时凡是发现右边某个数小于左边当前指向的数那么左边从当前指针到左半末尾的所有数都和这个右边数构成逆序对。因为左右两半都已经各自有序左边剩余的数必然都大于右边当前这个数于是可以一口气加上一大片计数不用逐个比较。这个过程极其自然但要理解它为什么是对的需要盯住一个前提合并操作发生之前左右两半内部已经分别排好序。正因为有序才能用长度来批量计数。如果不排序这个批量计算就没有依据这也是为什么必须在归并过程中统计而不能把排序和统计分成互不相干的两步。2.2 核心公式为什么是mid - i 1很多人第一次看到归并排序求逆序对的代码时会对那一行count mid - i 1感到困惑明明只是两个数在比较怎么突然加上一堆假设当前合并left..mid和mid1..right这两段指针i指向左段正在比较的位置指针j指向右段正在比较的位置。如果发现a[i] a[j]说明左段里从i到mid的所有元素都大于a[j]。为什么因为左段已经有序a[i..mid]是递增的既然最小的a[i]都比a[j]大后面的自然更大。而右段里j之前的位置已经在前面处理过了不会和a[j]再组成新的逆序对。所以此时能确定的逆序对数量就是mid - i 1。这里最容易犯的错误是写成count以为当前两个数正好是一对。可惜这样会漏掉大量本可以批量统计的逆序对。比如左段是[5,7,9]右段是[4,6,8]当5和4比较时不仅(5,4)是逆序对(7,4)、(9,4)同样也是。如果只加 1后面每个右段元素到来时又在左段当前指针处单独比较逻辑上也不是完全错但会多出很多次无谓的扫描复杂度退化回 O(n^2)。用公式来印证一下归并排序在处理完全逆序的数组[n, n-1, ..., 1]时第一次合并两个单元素会产生 1 对第二次合并两个长度为 2 的有序段左段元素全部大于右段累计增加 1212...最终总计数一定是n(n-1)/2。如果代码里的批量计数写对任何一个测试都能对上这个公式这是验证实现是否正确的最快方法。2.3 取左还是取右一个就能决定稳定性合并过程中还有一个细节值得单独提当a[i] a[j]时我们会把左边的a[i]放进临时数组指针i后移只有当a[i] a[j]时才把右边的a[j]放进临时数组并增加计数。这个不是随意写的它保证了两个关键属性。第一稳定性。归并排序是稳定排序等值元素的相对顺序不会被打乱。如果用判断那么当a[i] a[j]时会先取右边两个相等元素的相对顺序就反了排序不再稳定。对纯排序算法来说不稳定在某些场景下可能无所谓但逆序对的定义里相等不算逆序对所以等值时绝不能触发计数。第二避免重复计数。如果等值时走了count mid - i 1的分支会把相等的元素也算成逆序对结果偏大。我在帮人 review 代码时见过不止一次这种 bug看起来只是少写了一个等于号实际结果在含重复数据的用例上差了一大截。3. 完整代码实现与一次手工走查3.1 Java 实现把细节一次写对我用 Java 写一个最常用的版本。这里故意把临时数组的创建放在递归入口之外避免每次merge都重新new int[]性能会好很多。public class InversionCounter { public long countInversions(int[] nums) { if (nums null || nums.length 2) { return 0; } int[] temp new int[nums.length]; return mergeSortAndCount(nums, temp, 0, nums.length - 1); } private long mergeSortAndCount(int[] arr, int[] temp, int left, int right) { if (left right) { return 0; } int mid left (right - left) / 2; long count 0; count mergeSortAndCount(arr, temp, left, mid); count mergeSortAndCount(arr, temp, mid 1, right); count mergeAndCount(arr, temp, left, mid, right); return count; } private long mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) { for (int i left; i right; i) { temp[i] arr[i]; } int i left; int j mid 1; int k left; long count 0; while (i mid j right) { if (temp[i] temp[j]) { arr[k] temp[i]; } else { count (mid - i 1); arr[k] temp[j]; } } while (i mid) { arr[k] temp[i]; } while (j right) { arr[k] temp[j]; } return count; } }这里我把temp复制了left..right这一段也可以只在合并时创建长度为right - left 1的临时数组然后拷贝回原数组对应位置。两种写法都常见前者一次性申请最大空间、稍微省一点反复分配的开销后者更贴近很多教材的写法。两种我都实测过数据量到了百万级前者会明显更稳。还有一个细节mid left (right - left) / 2而不是(left right) / 2主要为了防止left right溢出。在普通题目里left right不太会超过int范围但养成习惯总是好的。3.2 一个具体例子的逐步推演拿[7, 5, 3, 4]来走一遍验证代码逻辑。第一层递归left0, right3, mid1。左边排序[7,5]mid0合并时7 5左段剩余元素 1 个所以count 1数组变为[5,7,3,4]。右边排序[3,4]3 4直接合并count 0数组变为[5,7,3,4]。第二层合并现在左段是[5,7]右段是[3,4]。比较5和35 3此时左段从i0到mid1共 2 个元素所以count 2把3放入结果。比较5和45 4又是 2 个元素count 2把4放入结果。最后左段剩余两个直接拼接。最终count 1 2 2 5。手动枚举验证[7,5,3,4]中7和后面三个数都是逆序对共 3 个5和3、5和4是逆序对共 2 个3和4不是。合计 5 个完全一致。走查的时候会发现第二次合并时两次count 2非常高效一个循环就把原先需要四次比较的统计做完了。3.3 计数变量为什么必须用 long逆序对个数最多可能是多少完全逆序时是n(n-1)/2。当n 100000时这个值是4,999,950,000已经超过int的2,147,483,647。所以计数变量必须用long或语言对应的 64 位整数类型。很多人在小数据上跑通后一上大数据就出现负数或者溢出导致的错误结果问题往往就出在这里。如果题目要求取模那么每一处累加都可以先取模但要注意取模后的中间值不能用来参与大小比较逻辑——顺手比较的是原数组元素不是累加的计数。我把这两种场景分开建议明确说答案可能很大的用long明确要求对某个模数取模的在count 时立刻取模返回时再取一次。别为了省那几行代码用int等到溢出再排查会非常痛苦。4. 复杂度、边界与稳定性教科书没说透的部分4.1 时间复杂度递推式为什么总能稳定在 O(n log n)归并排序求逆序对的时间复杂度可以用递推式表达T(n) 2 * T(n/2) O(n)。意思是处理规模为n的问题需要分别处理两个规模n/2的子问题再加上一次线性时间的合并。根据主定理这个递推式的解是O(n log n)。比这个式子更重要的是理解它为什么不会退化。其他很多分治算法可能因为切分不均匀而退化到 O(n^2)但归并排序每次都是严格从中间切分递归深度固定为log n每一层的总合并时间加起来是 O(n)所以总复杂度永远是 O(n log n)最坏、平均、最好都是这个量级。对求逆序对来说这意味着输入数据的排列方式不会影响运行时间上界这在算法竞赛和面试中是一个很大的优点。我记得有人会问递归调用本身不也有开销吗确实有但每层的递归调用次数是 2 的幂次增长单次开销很小log n层总共也就 O(n) 次调用和合并的线性开销同阶不会主导复杂度。实际项目里如果数据量特别大可以把递归深度大约估一下n到一亿时深度不过 27 层完全不用为栈空间担心。4.2 空间复杂度O(n) 的临时数组到底怎么省归并排序的经典实现需要额外 O(n) 空间这也是它对比原地排序算法如堆排序的短板。求逆序对时我们同样需要一块临时数组所以空间复杂度也是 O(n)。很多教材讲归并排序时会提到原地归并的优化但我要提醒一句实现原地归并通常非常复杂而且常数因子巨大实际性能往往还不如用额外空间的版本。我在某个项目里试过用旋转法做原地归并来省空间结果代码难度翻了几倍运行速度还变慢了。除非内存被卡到必须 O(1) 空间否则直接用临时数组是更理性的选择。如果你担心递归调用栈的额外空间它也是 O(log n)和 O(n) 的临时数组相比可以忽略。整体空间复杂度记作 O(n) 是准确的。4.3 边界情况空数组、单元素、全相等、全逆序我把实际测试中最常见的几类边界情况整理成一个表方便自测时逐项对照。输入期望结果说明[]或[x]0没有可比较的对[1,2,3,4,5]0已经升序没有逆序对[5,4,3,2,1]10完全逆序5*4/2[2,2,2,2]0相等不算逆序对最容易漏[3,1,2]2标准小样例[1,3,2]1单个乱序对考验合并细节全相等数组特别值得注意。如果用而不是判断这个用例会返回 6而不是 0。我在面试模拟中问过不少人他们能写出归并的框架却在这个等号上翻车。4.4 稳定性在逆序对问题里的隐藏价值归并排序是稳定排序这一性质在求逆序对时不只是一个额外优点它和计数逻辑是互相绑定的。设想一个场景数组里有两个相等的元素一个在左段一个在右段。它俩之间不应该构成逆序对。归并排序因为遇到相等时优先取左边所以不会出现右边相等元素提前跑到前面去的情况也就自然避免了对这两个元素的重复计数。如果换成不稳定排序你很难保证相等的左右元素不会在合并时交错进而导致统计规则混乱。所以把这个看作一个排序性质之外的正确性要求而不是可有可无的细节。它和公式mid - i 1一样是这道题实现里不可或缺的一环。5. 一题多解树状数组、离散化与归并排序怎么选5.1 树状数组离散化的思路除了归并排序逆序对还有一种非常常见的解法把原数组的值离散化然后逐个遍历用树状数组维护已经出现过的数的个数。每次遇到一个新数a[i]先查询树状数组里小于当前值的数量再用当前已经扫描过的总个数减去它得到的就是以这个数为逆序对右端的逆序对数量。为什么要离散化因为树状数组的下标必须是整数且不能太大。如果原始数据是10^9量级的整数不可能直接开一个这么大的数组。离散化的标准做法是把原数组拷贝一份排序然后用二分查找把每个元素映射成它是第几小的数。排序后相同的值映射到同一个排名查询时能严格排除相等元素保证逆序对定义中的严格大于条件。// 伪代码离散化 树状数组 int[] sorted nums.clone(); Arrays.sort(sorted); int[] rank new int[nums.length]; for (int i 0; i nums.length; i) { rank[i] Arrays.binarySearch(sorted, nums[i]) 1; } long ans 0; BIT bit new BIT(nums.length); for (int i 0; i nums.length; i) { int lessOrEqual bit.query(rank[i]); ans i - lessOrEqual; bit.update(rank[i], 1); }这段思路的时间复杂度同样是 O(n log n)其中排序和二分都是 O(n log n)树状数组每次query和update是 O(log n)。它和归并排序的时间复杂度是同阶的但常数通常更小代码也更短。5.2 两种做法的适用场景对比归并排序解法和树状数组解法各有千秋。归并排序不需要额外离散化对数据值域没有要求哪怕是浮点数、字符串这类能比较大小但不方便做下标的元素它都能直接处理。树状数组则需要把元素对应成整数排名离散化时要求元素可排序而且通常只适合数字类数据。还有一个重要区别归并排序是稳定的它的计算过程不会改变相等元素不计数的规则树状数组离散化时同样能保证相等元素排名一致但如果你不小心把 query 写成小于等于再减就会漏掉相等元素的处理。两者各有坑没有绝对优劣。从代码量看如果面试要求 20 分钟内写出可运行代码归并排序版更稳因为它不需要额外的数据结构类定义。如果面试官追问能不能换一种方法优化常数树状数组就是很好的进阶回答。在算法竞赛中很多选手偏爱树状数组因为它可以很方便地支持动态修改和查询和归并排序的静态快照式统计不是一个思维模型。5.3 从逆序对延伸开的问题逆序对不只存在于数组排序题里。有一个经典应用是衡量两个序列的一致性把两个序列中的一个映射成每个元素在另一个序列里的排名排名序列的逆序对个数就代表两个序列的差异程度。这在统计学里对应一种叫做秩相关的概念在推荐系统的离线评估中也能见到类似思想。在算法题中由逆序对延伸出的变体非常多。比如翻转对要求满足i j且a[i] 2 * a[j]这就不能简单地在合并时用a[i] a[j]直接批量计数得在合并前单独扫描一遍数组做条件判断。再比如二维平面上统计每个点右下方有多少个点可以按某个维度排序后用树状数组处理。这些问题本质上都还在用同一套思想借助有序性把原本 O(n^2) 的枚举降成 O(n log n)。正因为这套思想能复用我才建议把归并排序求逆序对当成一个母题来学。把mid - i 1那个公式彻底想明白后面遇到类似的分治统计题推导新公式时会顺手很多。6. 实测踩坑记录与自测数据清单6.1 我踩过的高频坑第一个坑是递归函数里count写成了局部变量每次递归返回时没有累加导致最后结果只有最底层合并那一次产生的计数。这种错误经常被编译器静默放过因为代码能跑样例也不一定每次都挂。排查方法很简单打印每个mergeAndCount的返回值手动加起来对一遍。第二个坑是合并前把临时数组复制错了范围。我写过一个版本在mergeAndCount里只复制left..mid然后另一个循环复制mid1..right时下标写成了arr[start]结果原数组在合并过程中被自己覆盖排序结果错得一塌糊涂。后来我改成先统一拷贝整个[left,right]到临时数组再逐位写回原数组思路清晰很多。第三个坑和大量测试用例有关一个全局计数器在多个测试用例之间没有清零。某些在线判题系统会把多个测试数据放在同一份代码的一次进程里运行如果计数器是静态成员变量必须在主函数入口重新置零。这种问题往往只有在完整测试集跑完才会暴露单测小样例根本发现不了。第四个坑是性能层面的count mid - i 1虽然本身是 O(1) 操作但如果临时数组每次合并都新建内存分配和 GC 开销会非常大。我之前用一百万元素做压力测试每次新建临时数组的版本耗时大约是不复用版本的 3 倍。数据量上了千万这个差距会进一步拉大。6.2 自测数据与期望输出我建议把下面这组数据直接拿去做单元测试。前几个都是手工就能验证的边界最后一个随机大数组可以配合暴力算法对拍。输入期望输出[]0[1]0[2,1]1[1,2,3,4]0[4,3,2,1]6[7,5,3,4]5[1,3,5,2,4]3[2,2,1,1]4最后一个[2,2,1,1]可以手算验证第一个 2 和两个 1 构成 2 对第二个 2 又和两个 1 构成 2 对总共 4 对两个 2 之间不算两个 1 之间也不算。如果代码输出 6说明相等元素被误计了。6.3 对拍技巧与性能体会写配套的暴力解法来对拍是非常好的排错手段。生成一个长度几万的小数组分别跑暴力 O(n^2) 和归并解法逐项比对结果。两者一旦不一致把数组缩小二分定位到第一个出错的位置调试效率会高很多。我自己的习惯是写一个随机数生成器测试长度从 2 开始一直翻倍到几十万每次跑完都对一下结果。归并排序求逆序对的实现一旦过了这个对拍流程后面搬到各种题目里基本不会因为逻辑错误翻车。最后讲一个我实际用下来的性能体会在普通个人电脑上用 Java 跑一百万元素的完全逆序数组归并解法大概需要几百毫秒级别暴力解法直接跑不动。换到一亿元素时归并解法需要的内存大约是几百兆字节已经接近常规题目的极限。如果你的应用场景里数组规模很大但元素取值范围很窄可以优先考虑树状数组加离散化内存占用会稍微小一些。如果元素不是整数归并排序就是更稳妥的选择。写这道题最值得记住的一句话是归并排序不只是排好序它天然提供了一种有序结构让计数不再需要逐个比较。理解了mid - i 1为什么成立很多看似复杂的分治统计问题都会变得清晰起来。