罗罗编程学习记录
本页内容 展开查看

02.5.2.3 归并排序与逆序对

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.2 排序算法与设计

02.5.2.3-001 归并排序的基本思想是什么?

一句话结论

分治:数组折半递归排序左右两段,再合并两个有序段;O(n log n) 稳定,需 O(n) 辅助空间;最坏不退化,适合稳定排序与链表排序。

概念解释

  • 折半递归。
  • 有序合并。
  • 稳定归并。

原理流程

  1. 中点拆分。
  2. 递归排序两段。
  3. 合并有序段。

代码 / 图示

[ 左 | 右 ] → 分别有序 → 合并

常见误区

  • 误区:归并原地无额外空间;正解:标准实现 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) 递归栈。

概念解释

  • 递归拆分。
  • 双指针合并。
  • 临时数组。

原理流程

  1. l>=r 返回。
  2. 中点递归。
  3. 合并写回。

代码 / 示例

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 分别指向两段起点,取较小者写入临时数组,移动对应指针;一段耗尽后复制另一段剩余;等值先取左段保证稳定。

概念解释

  • 双指针。
  • 取小写入。
  • 剩余复制。

原理流程

  1. 两段有序。
  2. 比较当前取小。
  3. 补剩余。

代码 / 图示

左 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);等值先取左侧,稳定。

概念解释

  • 层代价线性。
  • 对数层。
  • 稳定口径。

原理流程

  1. 拆分对数层。
  2. 每层总合并 O(n)。
  3. 等值顺序保留。

代码 / 图示

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。
  • 原地归并代价。
  • 链表适配。

原理流程

  1. 外层开 tmp。
  2. 合并写入 tmp 拷回。
  3. 避免重复分配。

代码 / 示例

int[] tmp = new int[a.length];

常见误区

  • 误区:原地归并是 O(1) 且高效;正解:原地归并复杂且常数高。
  • 误区:临时数组每次新建;正解:复用降低 GC 开销。

追问

  • Q:归并能做到 O(1) 额外空间吗? A:有原地算法,实现复杂,非面试主流。
  • Q:链表归并空间? A:O(log n) 递归栈,无数据数组。

02.5.2.3-006 链表为什么用归并排序?

一句话结论

链表合并只需改指针,无需随机访问与额外数据数组;归并按顺序合并两个有序链表正好适配;数组归并需临时数组,链表天然链式拼接。

概念解释

  • 指针合并。
  • 无随机访问需求。
  • 链式适配。

原理流程

  1. 快慢指针找中点拆分。
  2. 递归排序两半。
  3. 有序链表合并。

代码 / 图示

快慢指针拆半 → 递归 → 链表合并

常见误区

  • 误区:链表用快排;正解:快排随机访问/交换不便。
  • 误区:链表归并复制节点值;正解:改指针链接。

追问

  • 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] 的数对为逆序对;逆序对数量反映数组无序程度;归并合并时可统计;也可用树状数组/线段树求。

概念解释

  • 下标在前。
  • 值在后更小。
  • 无序度量。

原理流程

  1. 枚举 i<j 比较。
  2. 满足 a[i]>a[j] 计数。
  3. 分治批量统计。

代码 / 图示

[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)。

概念解释

  • 右侧先出。
  • 左侧剩余贡献。
  • 批量计数。

原理流程

  1. 两段已有序。
  2. 右元素更小先出。
  3. 左侧剩余个数计入。

代码 / 示例

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²) 枚举。

概念解释

  • 不重不漏。
  • 跨段贡献。
  • 递归汇总。

原理流程

  1. 段内逆序对递归得。
  2. 跨段合并时计数。
  3. 三者相加。

代码 / 图示

总数 = 左段 + 右段 + 跨段

常见误区

  • 误区:跨段重复计数;正解:每个数对只在其拆分层被统计。
  • 误区:段内未递归统计;正解:递归返回段内个数。

追问

  • Q:怎么验证不重不漏? A:数对按最近公共拆分层归属。
  • Q:小规模怎么验证计数是否正确? A:可暴力枚举所有 i<j 对照结果。

02.5.2.3-010 右侧更小元素个数(LC 315)怎么做?

一句话结论

归并过程中记录每个元素被多少右侧更小元素越过;合并时右元素先出,对应左侧剩余元素各记一个;需保留原始下标;本质是逆序对的按元素分摊。

概念解释

  • 按元素计数。
  • 原始下标。
  • 归并分摊。

原理流程

  1. 元素带下标归并。
  2. 右元素先出,左侧剩余累加。
  3. 结果按下标回填。

代码 / 图示

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);计数不增加渐近复杂度。

概念解释

  • 层线性。
  • 对数层。
  • 计数附带。

原理流程

  1. 合并扫描 O(n)。
  2. 每层总 O(n)。
  3. 共 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),递归深度口径不同;迭代版避免栈溢出。

概念解释

  • 递归拆分。
  • 迭代宽度。
  • 栈深差异。

原理流程

  1. 自顶向下:递归到底再合。
  2. 自底向上:按宽度外层循环。
  3. 合并逻辑相同。

代码 / 图示

自底向上:width=1 → 2 → 4 …

常见误区

  • 误区:自底向上改变稳定性;正解:合并口径相同。
  • 误区:末段不足宽度处理遗漏;正解:右段边界判空。

追问

  • Q:哪个工程常用? A:视语言实现,递归版更直观。
  • Q:外部排序? A:自底向上多路归并思路。

02.5.2.3-013 归并与快排怎么衔接对比?

一句话结论

两者分治;归并先递归后合并,稳定 O(n) 空间;快排先划分后递归,原地不稳定;归并适合稳定/链表/外部,快排适合内存通用排序;逆序对借助归并合并过程统计。

概念解释

  • 分治时点。
  • 空间稳定。
  • 场景选型。

原理流程

  1. 拆分方式对比。
  2. 空间稳定对比。
  3. 场景选择。

代码 / 图示

归并:后合并 O(n) 稳
快排:先划分 原地 不稳

常见误区

  • 误区:归并和快排都是原地;正解:归并需辅助数组。
  • 误区:逆序对用快排统计;正解:归并合并天然可计数。

追问

  • Q:快排求逆序对? A:划分难以批量统计,不直观。
  • Q:最坏谁稳? A:归并 O(n log n)。

02.5.2.3-014 外部排序的归并思想是什么?

一句话结论

数据超内存时分批读入内存排序,再多路归并输出;归并只需保留各段当前元素,适合流式合并;是归并分治在磁盘场景的延伸,详见 02.5.2.4。

概念解释

  • 分批排序。
  • 多路归并。
  • 流式合并。

原理流程

  1. 分块内存排序落盘。
  2. 多路堆取最小。
  3. 顺序输出。

代码 / 图示

块排序 → 多路归并

常见误区

  • 误区:外部排序一次性载入;正解:分批处理。
  • 误区:归并路数无上限;正解:受内存与 I/O 限制。

追问

  • Q:多路归并用什么选最小? A:小顶堆。
  • Q:详细外部排序见哪页? A:02.5.2.4。

02.5.2.3-015 归并与逆序对有哪些边界用例?

一句话结论

空数组、单元素、已有序(逆序对 0)、完全逆序(n(n-1)/2)、全相等、两元素、含负数;检查计数口径与合并剩余复制。

概念解释

  • 空与最短。
  • 极端有序。
  • 等值负数。

原理流程

  1. 空/单点返回 0。
  2. 有序测 0 贡献。
  3. 逆序测满贡献。

代码 / 图示

[] / [1] / 升序 / 逆序 / 全相等

常见误区

  • 误区:全相等计入逆序对;正解:等值不计。
  • 误区:逆序总数超 int;正解:用 long 计数。

追问

  • Q:完全逆序对数? A:n(n-1)/2。
  • Q:负数比较? A:大小口径不变。

02.5.2.3-016 归并排序常见错误有哪些?

一句话结论

中点越界、合并剩余未复制、等值先取右侧破坏稳定、临时数组范围错位、计数加在错误分支、递归区间错位;按拆分 → 合并 → 计数三步复核。

概念解释

  • 拆分边界。
  • 合并口径。
  • 计数分支。

原理流程

  1. 核对中点与区间。
  2. 核对等值方向。
  3. 核对计数条件。

代码 / 图示

拆分 [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)。

概念解释

  • 对数层线性。
  • 辅助数组。
  • 稳定口径。

原理流程

  1. 标注层数与每层代价。
  2. 标注辅助空间。
  3. 稳定性说明。

代码 / 图示

归并: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 适合在线与按元素查询。

概念解释

  • 离散化。
  • 前缀计数。
  • 在线查询。

原理流程

  1. 值离散化排名。
  2. 从右往左插入。
  3. 查询更小排名计数。

代码 / 图示

右侧已插入集合 → 查 < 当前值个数

常见误区

  • 误区:BIT 处理原始大值域;正解:先离散化。
  • 误区:从左往右方向错;正解:求右侧需逆序遍历。

追问

  • Q:BIT 详细结构? A:属进阶数据结构,本知识域预告。
  • Q:归并与 BIT 选哪个? A:离线批量归并直观,在线 BIT 灵活。

02.5.2.3-019 归并与逆序对常见追问有哪些?

一句话结论

为什么稳定、空间多少、最坏复杂度、逆序对怎么批量计数、右侧更小元素、链表为何归并、与快排对比、其他解法;回答围绕分治合并与计数不重不漏。

概念解释

  • 性质追问。
  • 计数原理。
  • 方案对比。

原理流程

  1. 说分治合并。
  2. 讲批量计数。
  3. 对比替代。

代码 / 图示

合并 → 稳定/空间 → 跨段计数

常见误区

  • 误区:追问稳定性答不上;正解:等值先取左段。
  • 误区:计数原理说不清;正解:右侧先出,左侧剩余贡献。

追问

  • Q:逆序对最多多少? A:n(n-1)/2,注意 long。
  • Q:归并能求顺序对吗? A:对称统计左侧更大/右侧更小。

02.5.2.3-020 归并排序常见变体有哪些?

一句话结论

数组归并、链表归并、逆序对计数、右侧更小元素、合并 K 个有序链表/数组、自底向上迭代、外部排序多路归并;主线是两个有序段合并 + 分治递归。

概念解释

  • 框架:有序合并。
  • 变体:计数/链表/多路。
  • 场景延伸。

原理流程

  1. 拆成有序段。
  2. 双指针/堆合并。
  3. 按题附加计数。

代码 / 图示

两段合并 → 递归分治
多路合并 → 堆

常见误区

  • 误区:变体题脱离合并框架;正解:有序段合并是核心。
  • 误区:多路归并双指针;正解:K 路用堆取最小。

追问

  • Q:合并 K 链见哪页? A:02.3.1.3。
  • Q:外部排序详见? A:02.5.2.4。