最稳的分治排序！归并排序凭什么稳定 O(n log n)，还顺手帮你数清逆序对？

昨天我们被快排的随机化和三路切分折腾得够呛今天换个“老实人”——归并排序。它没有快排的花哨但胜在稳定最好、最坏、平均都是O(nlogn)且天生稳定不需要任何随机化技巧。更妙的是在归并的过程中你可以顺手数出数组中的逆序对数量——这本来是Hard级别的题剑指 Offer51但归并排序只需加一行代码就能搞定复杂度依然是 O(nlogn)。今天我们就用归并排序搞定LC.912再顺势拿下逆序对计数一箭双雕。 题目速览30 秒读懂题目1排序数组LC.912给你一个整数数组nums将其升序排列。示例[5,2,3,1]→[1,2,3,5]题目2逆序对计数剑指 Offer51 / LCR170如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。求数组中逆序对的总数。示例[7,5,6,4]→ 输出5解释(7,5),(7,6),(7,4),(5,4),(6,4)约束长度 ≤ 5×10⁴暴力O(n²)必挂。 核心思路分治的另一种姿势——先拆后合逆序对藏在合并里暴力慢在哪排序选择/插入O(n²) → 超时。逆序对双重循环枚举所有ij比较nums[i] nums[j]→ O(n²)且逆序对数量本身可达O(n²)倒序数组但我们需要的是计数而不是枚举。归并排序的“分治”哲学分把数组从中间一分为二递归排序左右两半直到每半只剩一个元素天然有序。合把两个有序数组合并成一个更大的有序数组——用双指针分别扫描每次取较小者放入临时数组。为什么快合并两个总长为n的有序数组只需O(n)递归树高度O(logn)总O(nlogn)。逆序对怎么“免费”数出来当合并左右两半时左右内部都已经有序。此时如果右半的当前元素right[j]小于左半的当前元素left[i]那么由于左半有序从left[i]到左半末尾的所有元素都大于right[j]并且它们原始位置都在right[j]之前。所以可以一口气数出mid - i 1个逆序对i是当前左指针的位置。这就是“批发”计数而不是一个一个枚举从而把O(n²) 优化到O(nlogn)。关键归并排序本身就是有序合并的过程逆序对计数只是多累加一行完全免费。️ 图解算法逆序对计数过程以nums [7,5,6,4]为例递归拆分[7,5,6,4] ├─ [7,5] ──┬─ [7] │ └─ [5] └─ [6,4] ──┬─ [6] └─ [4]自底向上合并关注逆序对产生合并左半有序右半有序触发逆序对的情况计数累加[7] 与 [5][7][5]57左半剩余 [7] 都与5成对1[6] 与 [4][6][4]46左半剩余 [6] 都与4成对1[5,7] 与 [4,6][5,7][4,6]45左半 [5,7] 都与4成对 → 265取5不计67左半 [7] 与6成对 → 13总计数 113 5正确 ✅可见每次“右半元素被取走而左半还有剩余”时批量计入逆序对。 代码实现Python Java二合一Python 版归并排序 逆序对可选classSolution:defsortArray(self,nums:List[int])-List[int]:self.merge_sort(nums,0,len(nums)-1)returnnumsdefmerge_sort(self,nums,lo,hi):iflohi:returnmid(lohi)//2self.merge_sort(nums,lo,mid)self.merge_sort(nums,mid1,hi)self.merge(nums,lo,mid,hi)defmerge(self,nums,lo,mid,hi):tmpnums[lo:hi1]# 复制到临时数组i,j0,mid-lo1# i左半起点j右半起点相对于tmpforkinrange(lo,hi1):ifimid-lo:# 左半用完nums[k]tmp[j];j1elifjhi-lo:# 右半用完nums[k]tmp[i];i1eliftmp[i]tmp[j]:# 相等取左 → 保持稳定nums[k]tmp[i];i1else:# 若需数逆序对在这里加# count (mid - lo) - i 1nums[k]tmp[j];j1Java 版专门用于逆序对计数LCR 170classSolution{privateintcount0;publicintreversePairs(int[]record){if(record.length2)return0;mergeSort(record,0,record.length-1);returncount;}privatevoidmergeSort(int[]nums,intlo,inthi){if(lohi)return;intmidlo(hi-lo)/2;mergeSort(nums,lo,mid);mergeSort(nums,mid1,hi);merge(nums,lo,mid,hi);}privatevoidmerge(int[]nums,intlo,intmid,inthi){int[]tmpnewint[hi-lo1];System.arraycopy(nums,lo,tmp,0,hi-lo1);inti0,jmid-lo1;for(intklo;khi;k){if(imid-lo){nums[k]tmp[j];}elseif(jhi-lo){nums[k]tmp[i];}elseif(tmp[i]tmp[j]){// 相等取左稳定nums[k]tmp[i];}else{// 关键右半较小左半剩余全部 tmp[j]count(mid-lo)-i1;nums[k]tmp[j];}}}}⚠️关键点稳定性来自tmp[i] tmp[j]时取左半相等时左半原位置在前顺序保留。逆序对计数只需在else分支加一行count (mid - lo) - i 1其余不变。临时数组tmp是必需的因为合并时原数组会被覆盖无法同时读取左右段。⏱️ 复杂度分析面试必问时间每层合并O(n)共logn 层 →O(nlogn)不依赖数据分布稳定可靠。空间临时数组O(n) 递归栈 O(logn) →O(n)。这是稳定性和确定性性能的代价。 举一反三4 道高频变种题一套框架通吃题目变化点应对策略LC.493 翻转对统计nums[i] 2*nums[j]的数量归并框架但在 merge之前用双指针单独统计因为 2 倍关系与归并顺序不完全同步LC.327 区间和的个数统计满足条件的子数组和个数前缀和 归并计数同一套路LC.148 排序链表对链表排序归并排序是链表排序的首选快排在链表上partition别扭LC.剑指 Offer 51纯逆序对计数直接套上面的Java版即可 面试追问模拟提前准备惊艳全场Q1归并排序为什么稳定因为合并时当左右元素相等我们优先取左半使用判断。这样左半中相等的元素会先被放入结果它们原始顺序保持不变整体稳定性得以维持。Q2归并排序和快排你选哪个归并稳定、最坏 O(n log n)、需要 O(n) 额外空间 → 适合对象排序、外部排序、需要稳定性的场景。快排不稳定、最坏 O(n²)随机化后概率低、原地排序、缓存友好 → 适合基本类型排序、内存敏感场景。Java 的Arrays.sort()对基本类型用快排变体对对象用 TimSort归并 插入。Q3外部排序是怎么用归并思想的数据太大装不进内存分批读入内存排好序写成有序的“归并段”run然后对这些段进行多路归并用小顶堆或败者树合并成一个大文件。多路归并可以减少磁盘 I/O 次数是数据库和 MapReduce 的基础。Q4逆序对计数能不能用快排不能。快排不涉及两个有序子数组的合并过程无法批量获得跨区间的逆序信息。归并排序天然适合这种“跨左右统计”的问题。 实战小技巧刷题党必备口诀拆到底合有序相等取左稳跨区间批量数。模板凡是需要“统计跨左右区间的某种关系”且区间内有序可复用优先考虑归并排序。防坑临时数组一定要复制完整区间索引计算别搞错特别是 mid 的偏移。 实际应用场景不止是刷题Java 对象排序Arrays.sort(Object[])使用 TimSort归并 插入排序优化。数据库外部排序处理大文件排序时的归并阶段。稳定多关键字排序先按部门排再按工资排稳定保持部门内顺序。Git 合并合并有序提交历史树时也用归并思想。 今日思考题如果题目要求统计“非严格逆序对”即nums[i] nums[j]就算代码需要改哪里提示只需将tmp[i] tmp[j]改成这样相等时会取右半左半剩余与右半相等元素都计入。你能写出这个改动吗