02.5.2.3 归并排序与逆序对
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.2 排序算法与设计
02.5.2.3-001 归并排序的基本思想是什么?
一句话结论
分治:数组折半递归排序左右两段,再合并两个有序段;O(n log n) 稳定,需 O(n) 辅助空间;最坏不退化,适合稳定排序与链表排序。
概念解释
- 折半递归。
- 有序合并。
- 稳定归并。
原理流程
- 中点拆分。
- 递归排序两段。
- 合并有序段。
代码 / 图示
[ 左 | 右 ] → 分别有序 → 合并
常见误区
- 误区:归并原地无额外空间;正解:标准实现 O(n) 辅助数组。
- 误区:归并不稳定;正解:等值先取左侧,稳定。
追问
- Q:归并最坏复杂度? A:O(n log n),不退化。
- Q:递归深度? A:O(log n)。
02.5.2.3-002 归并排序怎么实现?
一句话结论
mergeSort(l,r) 中点递归左右,merge(l,m,r) 双指针合并到临时数组再拷回;O(n log n) 时间 O(n) 空间 O(log n) 递归栈。
概念解释
- 递归拆分。
- 双指针合并。
- 临时数组。
原理流程
l>=r返回。- 中点递归。
- 合并写回。
代码 / 示例
void mergeSort(int[] a, int l, int r) {
if (l >= r) return;
int m = (l + r) >>> 1;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
merge(a, l, m, r);
}
void merge(int[] a, int l, int m, int r) {
int[] tmp = new int[r - l + 1];
int i = l, j = m + 1, k = 0;
while (i <= m && j <= r) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i <= m) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
System.arraycopy(tmp, 0, a, l, tmp.length);
}
常见误区
- 误区:合并时等值先取右侧;正解:
<=先取左,保稳定。 - 误区:临时数组反复申请;正解:可预分配全局 tmp 复用。
追问
- Q:中点防溢出? A:
(l+r)>>>1。 - Q:拷回范围? A:
tmp.length对应区间。
02.5.2.3-003 两个有序段怎么合并?
一句话结论
双指针 i、j 分别指向两段起点,取较小者写入临时数组,移动对应指针;一段耗尽后复制另一段剩余;等值先取左段保证稳定。
概念解释
- 双指针。
- 取小写入。
- 剩余复制。
原理流程
- 两段有序。
- 比较当前取小。
- 补剩余。
代码 / 图示
左 i → 右 j →
取 min → tmp
常见误区
- 误区:剩余段未复制;正解:两个 while 补尾。
- 误区:比较方向写反;正解:升序取小。
追问
- Q:合并 K 个有序段? A:堆取最小,见 02.3.1.3。
- Q:链表合并? A:指针链接,无需临时数组。
02.5.2.3-004 归并排序复杂度与稳定性怎么分析?
一句话结论
每层合并 O(n),共 O(log n) 层,时间 O(n log n) 最坏平均一致;辅助数组 O(n),递归栈 O(log n);等值先取左侧,稳定。
概念解释
- 层代价线性。
- 对数层。
- 稳定口径。
原理流程
- 拆分对数层。
- 每层总合并 O(n)。
- 等值顺序保留。
代码 / 图示
n + 2·n/2 + … = O(n log n)
常见误区
- 误区:归并空间 O(1);正解:辅助数组 O(n)。
- 误区:归并不稳定;正解:稳定。
追问
- Q:为什么最坏不退化? A:折半均衡,不依赖输入。
- Q:递归栈算空间吗? A:O(log n) 另计。
02.5.2.3-005 归并空间怎么优化?
一句话结论
预分配一个与原数组等长的临时数组复用,避免每轮 new;减少分配开销;原地归并可实现但移动复杂、常数大,工程少用;链表归并无需数据数组。
概念解释
- 复用 tmp。
- 原地归并代价。
- 链表适配。
原理流程
- 外层开 tmp。
- 合并写入 tmp 拷回。
- 避免重复分配。
代码 / 示例
int[] tmp = new int[a.length];
常见误区
- 误区:原地归并是 O(1) 且高效;正解:原地归并复杂且常数高。
- 误区:临时数组每次新建;正解:复用降低 GC 开销。
追问
- Q:归并能做到 O(1) 额外空间吗? A:有原地算法,实现复杂,非面试主流。
- Q:链表归并空间? A:O(log n) 递归栈,无数据数组。
02.5.2.3-006 链表为什么用归并排序?
一句话结论
链表合并只需改指针,无需随机访问与额外数据数组;归并按顺序合并两个有序链表正好适配;数组归并需临时数组,链表天然链式拼接。
概念解释
- 指针合并。
- 无随机访问需求。
- 链式适配。
原理流程
- 快慢指针找中点拆分。
- 递归排序两半。
- 有序链表合并。
代码 / 图示
快慢指针拆半 → 递归 → 链表合并
常见误区
- 误区:链表用快排;正解:快排随机访问/交换不便。
- 误区:链表归并复制节点值;正解:改指针链接。
追问
- Q:链表排序(LC 148)? A:归并,详见 02.3.1.3。
- Q:找中点快慢指针? A:见 02.3.1.2。
02.5.2.3-007 什么是逆序对?
一句话结论
下标 i < j 且 a[i] > a[j] 的数对为逆序对;逆序对数量反映数组无序程度;归并合并时可统计;也可用树状数组/线段树求。
概念解释
- 下标在前。
- 值在后更小。
- 无序度量。
原理流程
- 枚举 i<j 比较。
- 满足 a[i]>a[j] 计数。
- 分治批量统计。
代码 / 图示
[3,1,2]:(3,1) (3,2) 共 2 个
常见误区
- 误区:逆序对按值大小不分下标;正解:必须 i<j。
- 误区:相等元素计入;正解:严格
>。
追问
- Q:逆序对与冒泡交换次数? A:冒泡相邻交换消除一个逆序对。
- Q:数组完全排序后逆序对是多少? A:0。
02.5.2.3-008 归并怎么求逆序对?
一句话结论
合并左右有序段时,若右侧元素 a[j] 先于左侧 a[i] 取出,则左侧剩余所有元素都大于它,一次性贡献 m-i+1 个逆序对;累加即总数;O(n log n)。
概念解释
- 右侧先出。
- 左侧剩余贡献。
- 批量计数。
原理流程
- 两段已有序。
- 右元素更小先出。
- 左侧剩余个数计入。
代码 / 示例
int mergeCount(int[] a, int l, int m, int r) {
int[] tmp = new int[r - l + 1];
int i = l, j = m + 1, k = 0, cnt = 0;
while (i <= m && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else { cnt += m - i + 1; tmp[k++] = a[j++]; }
}
while (i <= m) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
System.arraycopy(tmp, 0, a, l, tmp.length);
return cnt;
}
常见误区
- 误区:左元素先出时计数;正解:右元素先出才形成逆序。
- 误区:等值计入逆序;正解:
<=先取左,不计。
追问
- Q:计数为什么是左侧剩余? A:左侧有序,剩余都 ≥ 当前左 > 右元素。
- Q:累加位置? A:每层合并累加,递归返回汇总。
02.5.2.3-009 逆序对计数原理是什么?
一句话结论
逆序对按跨左右段划分:段内由递归统计,跨段在合并时批量统计;每个逆序对恰在某次合并被计一次,不重不漏;分治避免 O(n²) 枚举。
概念解释
- 不重不漏。
- 跨段贡献。
- 递归汇总。
原理流程
- 段内逆序对递归得。
- 跨段合并时计数。
- 三者相加。
代码 / 图示
总数 = 左段 + 右段 + 跨段
常见误区
- 误区:跨段重复计数;正解:每个数对只在其拆分层被统计。
- 误区:段内未递归统计;正解:递归返回段内个数。
追问
- Q:怎么验证不重不漏? A:数对按最近公共拆分层归属。
- Q:小规模怎么验证计数是否正确? A:可暴力枚举所有 i<j 对照结果。
02.5.2.3-010 右侧更小元素个数(LC 315)怎么做?
一句话结论
归并过程中记录每个元素被多少右侧更小元素越过;合并时右元素先出,对应左侧剩余元素各记一个;需保留原始下标;本质是逆序对的按元素分摊。
概念解释
- 按元素计数。
- 原始下标。
- 归并分摊。
原理流程
- 元素带下标归并。
- 右元素先出,左侧剩余累加。
- 结果按下标回填。
代码 / 图示
nums[i] 右侧更小个数 = 归并中越过它的右元素数
常见误区
- 误区:排序后丢失原始下标;正解:携带下标归并。
- 误区:跨元素计数错位;正解:按左侧剩余逐个累加。
追问
- Q:树状数组版本? A:离散化后从右往左查前缀和。
- Q:与逆序对关系? A:各元素计数之和即逆序对数。
02.5.2.3-011 归并求逆序对复杂度怎么算?
一句话结论
递归 O(log n) 层,每层合并与计数 O(n),总 O(n log n) 时间;辅助数组 O(n),递归栈 O(log n);计数不增加渐近复杂度。
概念解释
- 层线性。
- 对数层。
- 计数附带。
原理流程
- 合并扫描 O(n)。
- 每层总 O(n)。
- 共 log n 层。
代码 / 图示
O(n log n) 时间 / O(n) 空间
常见误区
- 误区:计数额外 O(n²);正解:合并时批量累加,常数次比较。
- 误区:逆序对只能 O(n²);正解:归并/树状数组可 O(n log n)。
追问
- Q:空间能否省? A:计数仍需辅助数组归并。
- Q:链表求逆序对? A:可归并,计数逻辑同。
02.5.2.3-012 自顶向下与自底向上归并有什么区别?
一句话结论
自顶向下递归拆半再合并;自底向上按 1、2、4… 宽度逐层两两合并,无递归栈;两者 O(n log n),递归深度口径不同;迭代版避免栈溢出。
概念解释
- 递归拆分。
- 迭代宽度。
- 栈深差异。
原理流程
- 自顶向下:递归到底再合。
- 自底向上:按宽度外层循环。
- 合并逻辑相同。
代码 / 图示
自底向上:width=1 → 2 → 4 …
常见误区
- 误区:自底向上改变稳定性;正解:合并口径相同。
- 误区:末段不足宽度处理遗漏;正解:右段边界判空。
追问
- Q:哪个工程常用? A:视语言实现,递归版更直观。
- Q:外部排序? A:自底向上多路归并思路。
02.5.2.3-013 归并与快排怎么衔接对比?
一句话结论
两者分治;归并先递归后合并,稳定 O(n) 空间;快排先划分后递归,原地不稳定;归并适合稳定/链表/外部,快排适合内存通用排序;逆序对借助归并合并过程统计。
概念解释
- 分治时点。
- 空间稳定。
- 场景选型。
原理流程
- 拆分方式对比。
- 空间稳定对比。
- 场景选择。
代码 / 图示
归并:后合并 O(n) 稳
快排:先划分 原地 不稳
常见误区
- 误区:归并和快排都是原地;正解:归并需辅助数组。
- 误区:逆序对用快排统计;正解:归并合并天然可计数。
追问
- Q:快排求逆序对? A:划分难以批量统计,不直观。
- Q:最坏谁稳? A:归并 O(n log n)。
02.5.2.3-014 外部排序的归并思想是什么?
一句话结论
数据超内存时分批读入内存排序,再多路归并输出;归并只需保留各段当前元素,适合流式合并;是归并分治在磁盘场景的延伸,详见 02.5.2.4。
概念解释
- 分批排序。
- 多路归并。
- 流式合并。
原理流程
- 分块内存排序落盘。
- 多路堆取最小。
- 顺序输出。
代码 / 图示
块排序 → 多路归并
常见误区
- 误区:外部排序一次性载入;正解:分批处理。
- 误区:归并路数无上限;正解:受内存与 I/O 限制。
追问
- Q:多路归并用什么选最小? A:小顶堆。
- Q:详细外部排序见哪页? A:02.5.2.4。
02.5.2.3-015 归并与逆序对有哪些边界用例?
一句话结论
空数组、单元素、已有序(逆序对 0)、完全逆序(n(n-1)/2)、全相等、两元素、含负数;检查计数口径与合并剩余复制。
概念解释
- 空与最短。
- 极端有序。
- 等值负数。
原理流程
- 空/单点返回 0。
- 有序测 0 贡献。
- 逆序测满贡献。
代码 / 图示
[] / [1] / 升序 / 逆序 / 全相等
常见误区
- 误区:全相等计入逆序对;正解:等值不计。
- 误区:逆序总数超 int;正解:用 long 计数。
追问
- Q:完全逆序对数? A:n(n-1)/2。
- Q:负数比较? A:大小口径不变。
02.5.2.3-016 归并排序常见错误有哪些?
一句话结论
中点越界、合并剩余未复制、等值先取右侧破坏稳定、临时数组范围错位、计数加在错误分支、递归区间错位;按拆分 → 合并 → 计数三步复核。
概念解释
- 拆分边界。
- 合并口径。
- 计数分支。
原理流程
- 核对中点与区间。
- 核对等值方向。
- 核对计数条件。
代码 / 图示
拆分 [l,m][m+1,r]
合并 <= 先左
右先出才计数
常见误区
- 误区:
m=(l+r)/2溢出;正解:无符号右移。 - 误区:计数写成左侧先出;正解:右先出贡献。
追问
- Q:怎么自测稳定? A:等值带下标检查顺序。
- Q:计数溢出? A:long 累加。
02.5.2.3-017 归并与逆序对复杂度怎么汇报?
一句话结论
归并排序 O(n log n) 时间,O(n) 辅助 + O(log n) 栈;逆序对同阶 O(n log n);稳定;链表归并无数据数组,栈 O(log n)。
概念解释
- 对数层线性。
- 辅助数组。
- 稳定口径。
原理流程
- 标注层数与每层代价。
- 标注辅助空间。
- 稳定性说明。
代码 / 图示
归并:O(n log n) / O(n) + O(log n) 栈 / 稳定
逆序对:同阶
常见误区
- 误区:归并 O(log n) 空间;正解:辅助数组 O(n)。
- 误区:逆序对计数 O(n²);正解:归并批量 O(n log n)。
追问
- Q:递归栈能否省? A:自底向上迭代可去递归栈,辅助数组仍需。
- Q:空间受限场景? A:考虑快排原地。
02.5.2.3-018 逆序对还有哪些其他解法?
一句话结论
树状数组/线段树:离散化后从右往左,查询当前元素前面(右侧)已插入的更小元素个数;O(n log n);归并适合一次批量,BIT 适合在线与按元素查询。
概念解释
- 离散化。
- 前缀计数。
- 在线查询。
原理流程
- 值离散化排名。
- 从右往左插入。
- 查询更小排名计数。
代码 / 图示
右侧已插入集合 → 查 < 当前值个数
常见误区
- 误区:BIT 处理原始大值域;正解:先离散化。
- 误区:从左往右方向错;正解:求右侧需逆序遍历。
追问
- Q:BIT 详细结构? A:属进阶数据结构,本知识域预告。
- Q:归并与 BIT 选哪个? A:离线批量归并直观,在线 BIT 灵活。
02.5.2.3-019 归并与逆序对常见追问有哪些?
一句话结论
为什么稳定、空间多少、最坏复杂度、逆序对怎么批量计数、右侧更小元素、链表为何归并、与快排对比、其他解法;回答围绕分治合并与计数不重不漏。
概念解释
- 性质追问。
- 计数原理。
- 方案对比。
原理流程
- 说分治合并。
- 讲批量计数。
- 对比替代。
代码 / 图示
合并 → 稳定/空间 → 跨段计数
常见误区
- 误区:追问稳定性答不上;正解:等值先取左段。
- 误区:计数原理说不清;正解:右侧先出,左侧剩余贡献。
追问
- Q:逆序对最多多少? A:n(n-1)/2,注意 long。
- Q:归并能求顺序对吗? A:对称统计左侧更大/右侧更小。
02.5.2.3-020 归并排序常见变体有哪些?
一句话结论
数组归并、链表归并、逆序对计数、右侧更小元素、合并 K 个有序链表/数组、自底向上迭代、外部排序多路归并;主线是两个有序段合并 + 分治递归。
概念解释
- 框架:有序合并。
- 变体:计数/链表/多路。
- 场景延伸。
原理流程
- 拆成有序段。
- 双指针/堆合并。
- 按题附加计数。
代码 / 图示
两段合并 → 递归分治
多路合并 → 堆
常见误区
- 误区:变体题脱离合并框架;正解:有序段合并是核心。
- 误区:多路归并双指针;正解:K 路用堆取最小。
追问
- Q:合并 K 链见哪页? A:02.3.1.3。
- Q:外部排序详见? A:02.5.2.4。