七、排序（第 79-94 题）
79. 以下排序算法中，平均时间复杂度为O(n log n)的是( )
标签：【互联网/国企笔试超高频】
A. 冒泡排序 B. 快速排序 C. 插入排序 D. 选择排序
答案：B
【结论】 快速排序平均时间复杂度为 O(n log n)，选 B。
【逐项辨析】
- A 冒泡排序：平均 O(n²)。
- B 快速排序：正确。 平均 O(n log n)，是比较排序中实际性能最好的算法之一。
- C 插入排序：平均 O(n²)。
- D 选择排序：平均 O(n²)。
【知识点】 常见排序的平均复杂度对照
| 排序算法 | 平均复杂度 | 是否达到下界 O(n log n) |
|---|---|---|
| 冒泡排序 | O(n²) | ❌ |
| 插入排序 | O(n²) | ❌ |
| 选择排序 | O(n²) | ❌ |
| 快速排序 | O(n log n) | ✅ |
| 归并排序 | O(n log n) | ✅ |
| 堆排序 | O(n log n) | ✅ |
O(n log n) 是基于比较的排序算法的理论下界 —— 由决策树模型可证：比较排序至少需要 ⌈log₂(n!)⌉ ≈ n log₂n 次比较。
【记忆锚点】 “只有快排、归并、堆排序达到 n log n，冒泡、插入、选择都停在 n²”。
【易混对比】 注意题干问的是“平均” —— 快排最坏会退化为 O(n²)（见第 81 题）。三个 O(n log n) 的算法中，只有归并和堆排序在所有情况下都是 O(n log n)，快排的最坏情况是例外。
【自测】 下列哪个排序算法平均复杂度不是 O(n log n)? A. 快速排序 B. 归并排序 C. 堆排序 D. 简单选择排序
答：D。简单选择排序平均为 O(n²)。与第 80 题连考。
【知识关联】
- 同库连考：与第 80 题（最坏最优=归并）、第 81 题（快排最坏 O(n²)）、第 91 题（任何情况都不退化 O(n²) 的是归并/堆）构成「排序复杂度」决策组；与第 82/83 题（稳定性）双维度交叉；与第 2 题（复杂度取决于规模与初态）总纲相连——快排平均 n log n、最坏 n² 正是「初态改变复杂度」的典型。
- 工程实现：Java 基本类型
Arrays.sort用双轴快排（平均 n log n）；对象类型用 TimSort（归并+插入，保证稳定且最坏 n log n）；C++std::sort是 introsort（快排+堆排兜底），避免最坏 n²。工程选型看平均，但必须给最坏兜底。 - 408 / 国企真题：408 与国网排序章必考「下列平均为 O(n log n) 的是」；注意题干若改成「最好/最坏」答案会变（冒泡最好 O(n)，快排最坏 O(n²)）。国企题库还常考「比较排序下界 O(n log n)」的判断。
- 面试追问:①「为什么 O(n log n) 是比较排序下界？」（决策树模型，n! 个叶子，树高 ≥ log₂(n!)）；②「归并/堆排平均也是 n log n，为何常推快排？」（常数小、缓存局部性好）；③「哪些排序能突破下界？」（基数/计数/桶等非比较排序）。
【拓展延伸】
变式问法:①「平均 O(n log n) 的是？」（快排，本题；归并/堆排若出现也是对的，看选项）；②「冒泡平均？」（O(n²)）；③「比较排序平均下界？」（O(n log n)）。
工程映射：JDK/C++/Python（Timsort）排序实现的复杂度合同都是「平均/最坏有明确上界」；基准测试要分 random/sorted/reverse 三组数据，正是为了看见平均与最坏的落差。
易错提醒：本题只给了快排一个 n log n 选项；若选项同时出现归并/堆排而题干问「平均」，三者都对，需看是否是多选或题干限定。另勿把「平均 n log n」误读成「最坏 n log n」——快排最坏会掉到 n²。
80. 以下排序算法中，最坏情况下时间复杂度最低（最优）的是( )
标签：【互联网/国企笔试超高频】
A. 归并排序 B. 快速排序 C. 冒泡排序 D. 选择排序
答案：A
【结论】 归并排序最坏为 O(n log n)，是四者中最优的，选 A。
【逐项辨析】
- B 快速排序：最坏 O(n²)（数据已有序时）。
- A 归并排序：正确。 最好、平均、最坏均为 O(n log n)。
- C 冒泡排序：最坏 O(n²)。
- D 选择排序：最坏 O(n²)。
【知识点】 三种情况的完整对照
| 排序算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | ❌ |
归并排序的复杂度与数据初始状态无关 —— 因为它总是“分成两半 → 递归排序 → 合并”，分治结构与数据内容无关。
【记忆锚点】 “归并稳如泰山，快排怕有序”——归并三种情况都是 n log n，快排最坏会掉到 n²。
【易混对比】 与第 91 题同考点（任何情况下都不退化为 O(n²) 的排序），与第 86 题连考（归并的空间代价是 O(n))。“最坏情况最优”是归并排序最突出的标签。
【自测】 下列排序算法中，最坏情况时间复杂度为 O(n log n) 的有哪些？
答：归并排序、堆排序（快排最坏 O(n²)；冒泡、插入、选择也都有 O(n²) 的最坏情况）。与第 84、91 题连考。
【知识关联】
- 同库连考：与第 79 题（平均 O(n log n)=快排）对照——本题问「最坏最优」才选归并；与第 81 题（快排最坏 O(n²)）、第 91 题（不退化 O(n²) 的算法）、第 86 题（归并空间 O(n)）、第 83 题（归并稳定）构成归并的「复杂度-空间-稳定」三件套；与第 2 题（初态影响时间复杂度）相连：归并是少数与初态无关的算法。
- 工程实现：Java 对象排序 TimSort 底层是归并，合同上最坏 O(n log n)，专为「不能接受最坏平方」的场景；外部排序（大数据 sort、数据库 external sort）几乎都是多路归并；Git 合并、大数据 shuffle 也是归并思想。快排虽平均常数更小，但最坏要靠随机 pivot/introsort 兜底。
- 408 / 国企真题：408 与国网「最坏情况下时间复杂度最低/最优的排序」标准答案归并（或归并与堆排）；干扰项快排——学生记得「快排很快」却忽略最坏。真题变体：「在最坏情况下时间复杂度仍为 O(n log n) 的是」（归并、堆）。
- 面试追问:①「归并三种情况？」（最好/平均/最坏都是 O(n log n)）；②「既然归并最坏更好，为何基本类型不用它？」（O(n) 空间，快排原地且平均更快）；③「堆排最坏也是 n log n 且原地，为何对象排序不用？」（不稳定、缓存差）。
【拓展延伸】
变式问法:①「最坏复杂度最低？」（归并，本题）；②「与初态无关的排序？」（归并、堆、选择）；③「最坏 O(n log n) 且稳定？」（归并；堆排不稳定）。
工程映射：金融清算、审计流水排序要求结果可预期（最坏有界）且稳定，故工业上多用归并/TimSort；实时系统禁止最坏平方，就是本题结论的工程化。
易错提醒：题干「最坏情况下最优」时不能选快排；「平均最好/常数最小」才偏快排。四选项里若同时有归并和堆排而题目是单选，优先看是否强调「稳定」——本题选项只有归并，直接选 A。
81. 快速排序在最坏情况下的时间复杂度为( )，发生在( )
标签：【互联网/国企笔试超高频】
A. O(n log n)，数据随机时 B. O(n²)，数据已有序时 C. O(n)，数据全相等时 D. O(n log n)，数据已有序时
答案：B
【结论】 最坏为 O(n²)，发生在数据已有序时，选 B。
【逐项辨析】
- A O(n log n)，数据随机时：数据随机时快排接近平均性能 O(n log n)，不是最坏。
- B O(n²)，数据已有序时：正确。 每次划分只能把问题规模减少 1。
- C O(n)，数据全相等时：题干问的是最坏情况。标准二路划分的快排在全相等数据上每趟只能划掉基准一个元素，同样退化到 O(n²)；O(n) 只有改用三路划分（荷兰国旗式，把等于基准的元素一次归中）才成立，那是优化变体而非快排自身的最坏结论，故该项不选。
- D O(n log n)，数据已有序时：方向反了，已有序恰恰是最坏。
【知识点】 快排为什么在“已有序”时最坏？
以第一个元素为基准(pivot),数据已升序:
第 1 趟:划分后基准归位到最左,右半区剩 n−1 个元素
第 2 趟:右半区再划分,右半区剩 n−2 个元素
...
总比较次数 = n + (n−1) + ... + 1 = n(n+1)/2 = O(n²)有序数组 [1, 2, 3, 4, 5],取 1 为基准:
划分后 → [1] + [2, 3, 4, 5] 每次只切掉 1 个元素
递归深度 = n,每层代价 O(n) → O(n²)三种优化方法：
- 三数取中法选基准（取首、中、尾的中位数）；
- 随机选择基准；3. 对小规模子数组切换为插入排序。
【记忆锚点】 “有序表是快排的灾星”——越有序，划分越不平衡。
【易混对比】 “数据已有序”对快排是最坏情形(O(n²))，对冒泡、插入排序却是最好情形(O(n)) —— 这一对反差是笔试最爱考的（见第 88、89 题）。
【自测】 快排取中间位置元素为基准时，数据已有序还会退化吗？
答：不会退化。 取中间元素为基准时，已有序数据的划分恰好是平衡的（左右各一半），复杂度仍为 O(n log n)。这正是“三数取中法”能解决问题的原因。
【知识关联】
- 同库连考：与第 2 题（初态影响复杂度）、第 79 题（平均 O(n log n)）、第 80/91 题（归并不退化）、第 87 题（一趟划分）、第 88/89 题（冒泡/插入「已有序=最好」）构成反差考点组——同一「数据已有序」，快排最坏、冒泡/插入最好。
- 工程实现：JDK 双轴快排 + 随机/打乱；C++ introsort 限制递归深度并在子问题过深时切堆排；三数取中避免有序输入退化；TimSort 则干脆不用快排给对象排序。生产排序库必须处理「近有序」输入。
- 408 / 国企真题：408「快速排序最坏情况及触发条件」标准答案 O(n²)+已有序（取首/固定 pivot 时）；国网计算题会模拟第一趟划分。注意：若 pivot 取中位数，已有序不一定最坏——真题默认首元素为基准。
- 面试追问:①「如何避免最坏？」（随机 pivot、median-of-3、小数组改插入）；②「取中间元素时有序还退化吗？」（划分平衡，仍是 n log n）；③「快排稳定吗？」（不稳定）。
【拓展延伸】
变式问法:①「最坏复杂度及情形？」（O(n²)，数据已有序，本题）；②「数据随机时？」（平均 O(n log n)）；③「全相等？」（朴素划分可能失衡，三路划分可 O(n) 量级处理）。
工程映射：基准测试必须含 sorted/reverse/random；分布式排序对已分区有序数据要防退化；面试手写快排常被追问有序输入。
易错提醒：题干「最坏+发生在」要同时满足复杂度与情形；D 把复杂度与情形搭配反了。「已有序」对不同算法意义不同，这是全章最经典对照。
82. 以下排序算法中，不稳定的是( )
标签：【互联网/国企笔试超高频】
A. 冒泡排序 B. 归并排序 C. 快速排序 D. 插入排序
答案：C
【结论】 快速排序不稳定，选 C。
【逐项辨析】
- A 冒泡排序：稳定（相等元素不交换）。
- B 归并排序：稳定（合并时相等优先取左半区）。
- C 快速排序：不稳定。 交换操作可能改变相等元素的相对顺序。
- D 插入排序：稳定（相等时不后移）。
【知识点】 稳定性分类（必背）：
| 稳定排序 | 不稳定排序 |
|---|---|
| 冒泡排序 | 选择排序 |
| 插入排序 | 快速排序 |
| 归并排序 | 希尔排序 |
| 基数排序 | 堆排序 |
口诀：“选快希堆”不稳定，“归插冒基”稳定。
快排不稳定的例子:序列 [3a, 2, 3b, 1],以 3a 为基准划分
划分后 3b 可能被交换到 3a 前面 → 相等元素相对顺序改变 → 不稳定【记忆锚点】 “选快希堆”不稳定，“归插冒基”稳定。
【易混对比】 稳定性的实际意义：当排序关键字有多个维度时（如先按成绩排、成绩相同的保持原来的学号顺序），必须用稳定排序。例如“按成绩排序后，同分者保持原顺序”，用冒泡 / 插入 / 归并可实现，用快排 / 堆排则不能保证。
【自测】 下列哪一组全部是不稳定排序？ A. 冒泡、插入、归并 B. 快排、堆排、选择 C. 归并、基数、冒泡 D. 插入、快排、堆排
答：B。快排、堆排、选择排序都不稳定。与第 83 题连考。
【知识关联】
- 同库连考：与第 83 题（稳定的是归并）成对——「不稳定的是快排/稳定的是归并」；与第 81 题（快排最坏）、第 91/92 题（堆排不稳定、基数稳定）组成稳定性全表；与第 40 题一带的「口诀记忆」风格一致，本题口诀「选快希堆」不稳定。
- 工程实现：Java 对象排序必须稳定 → TimSort，这是 JDK 的硬性兼容合同（程序员依赖「先按 A 再按 B，A 相同时保持 B 序」）；基本类型排序不要求稳定，可用双轴快排。C++
stable_sortvssort对应同一分野。数据库ORDER BY多列时，引擎若用不稳定算法，第一列相同时第二列序可能乱——所以引擎常归并/稳定化处理。 - 408 / 国企真题：408「下列排序算法不稳定的是」超高频；国网/银行选择题口诀化：稳定=归插冒基，不稳定=选快希堆。注意选择排序也不稳定，有时干扰项会写「选择排序稳定」。
- 面试追问:①「快排为什么不稳定？」（划分交换可能把相等元素换到前面，如 [3a,2,3b] 以 3a 为基准）；②「如何把不稳定算法变稳定？」（比较键附加原始下标作为次级键）；③「多关键字排序为何要稳定？」（保证前一轮排序结果在本轮相等时被保留，即可省去多轮）。
【拓展延伸】
变式问法:①「不稳定的是？」（快排，本题；选择/希尔/堆也不稳定）；②「稳定的是？」（归并、插入、冒泡、基数）；③「堆排稳定吗？」（不稳定，筛选交换会打乱相等元序）。
工程映射：前端表格「先按分数排，再按姓名排」若底层不稳定会闪乱；Excel 多级排序、报表引擎都要求稳定；JDK 为对象选择 TimSort 正是把本题结论写进了 API 契约。
易错提醒：稳定性与时间/空间复杂度正交——归并稳定但要 O(n) 空间；堆排最坏 n log n 且原地但不稳定。考试把「稳定」「原地」「最坏复杂度」混在选项里是经典挖坑方式。
83. 以下排序算法中，稳定的是( )
标签：【互联网/国企笔试超高频】
A. 快速排序 B. 堆排序 C. 归并排序 D. 选择排序
答案：C
【结论】 归并排序稳定，选 C。
【逐项辨析】
- A 快速排序：不稳定。
- B 堆排序：不稳定（堆调整会打乱相等元素的顺序）。
- C 归并排序：稳定。 合并两个有序子序列时，遇相等元素优先取前一个子序列的元素，从而保持稳定性。
- D 选择排序：不稳定（交换可能跨越相等元素）。
【知识点】 归并排序为什么稳定？
合并两个有序子序列时,比较规则:
若 left[i] <= right[j] → 取 left[i] ← 注意用"<="
否则 → 取 right[j]
用"<="意味着相等时优先取左半区的元素,
而左半区的元素原本就在前面 → 相对顺序保持不变 → 稳定 ✓| 排序算法 | 稳定性 | 稳定的原因 |
|---|---|---|
| 冒泡排序 | ✅ | 只有严格逆序时才交换 |
| 插入排序 | ✅ | 相等时不再后移 |
| 归并排序 | ✅ | 合并时相等优先取左 |
| 基数排序 | ✅ | 按位分配收集，天然保持顺序 |
| 快速排序 | ❌ | 交换跨越相等元素 |
| 选择排序 | ❌ | 交换跨越相等元素 |
| 希尔排序 | ❌ | 分组插入破坏相对顺序 |
| 堆排序 | ❌ | 堆调整打乱顺序 |
【记忆锚点】 “归插冒基”稳定（归并、插入、冒泡、基数）。
【易混对比】 注意“稳定”与“原地”是两个独立维度：归并排序稳定但不原地（需 O(n) 额外空间）；堆排序原地但不稳定。考试中常把这两个维度交叉设置选项。
【自测】 归并排序的稳定性靠什么保证？
答：靠合并时相等元素优先取左半区的规则（用
left[i] <= right[j]才取左）。与第 82 题连考。
【知识关联】
- 同库连考：与第 82 题（不稳定的是快排）成对互锁；与第 79/80/91 题（复杂度）、第 86 题（归并空间 O(n)）、第 92 题（基数排序也稳定）同属排序性质网；与第 16 题（两个有序表合并）是归并的母操作，稳定性就在合并比较规则里产生。
- 工程实现：Java
Arrays.sort(Object[])强制稳定（TimSort）；Python、Ruby 对象排序同样稳定；JDK 文档直接写明 stable sort，因为大量业务代码依赖「先按时间再按金额」这类多键排序的隐含顺序。外部排序、数据库 sort 也优先稳定归并。 - 408 / 国企真题：408「下列排序算法稳定的是」与第 82 题互为镜像；国网题库要求默写「归插冒基稳定，选快希堆不稳定」。常考变体：给序列演示归并合并过程，问相等元素最终相对位置。
- 面试追问:①「归并为何稳定？」（合并时
left[i] <= right[j]优先取左，相等元保持原前后）；②「若改成<会怎样？」（相等时优先取右，稳定性被破坏）；③「稳定 vs 原地？」（归并稳定不原地；堆排原地不稳定；两者维度不同）。
【拓展延伸】
变式问法:①「稳定的是？」（归并，本题）；②「基数排序稳定吗？」（稳定，按位分配收集保持顺序）；③「希尔排序稳定吗？」（不稳定，跨步插入打乱）。
工程映射：报表「一级部门、二级部门」多级排序；消息队列按 partition 内 offset 有序；电商「销量优先，同销量保持上架顺序」——业务语义常隐含稳定排序假设，算法选型必须兑现。
易错提醒：稳定性的保证写在合并/交换规则里，不是算法名字玄学；背口诀之外要能解释归并合并的 <=。另：存在「稳定堆排序」的研究实现，但经典堆排序按教材口径判不稳定。
84. 堆排序的时间复杂度在最好、平均、最坏情况下分别为( )
标签：【互联网/国企笔试高频】
A. O(n), O(n log n), O(n²) B. O(n log n), O(n²), O(n²) C. O(n), O(n), O(n log n) D. O(n log n), O(n log n), O(n log n)
答案：D
【结论】 最好、平均、最坏均为 O(n log n)，选 D。
【逐项辨析】
- A O(n), O(n log n), O(n²)：混入了快排的最坏情况。
- D O(n log n), O(n log n), O(n log n)：正确。 三种情况一致。
- C O(n), O(n), O(n log n)：误把建堆的 O(n) 当成整体复杂度。
- B O(n log n), O(n²), O(n²)：混入了快排的复杂度。
【知识点】 堆排序的复杂度分解
建初始堆: O(n) ← 自底向上调整,线性时间(见第 85 题)
反复取堆顶并调整堆:O(log n) × n 次 = O(n log n)
总复杂度: O(n log n) ← 建堆的 O(n) 被 O(n log n) 吸收| 排序算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ |
堆排序的两个突出优点：
- 时间复杂度稳定 —— 不受数据初始状态影响；2. 空间 O(1) —— 原地排序（优于归并的 O(n))。
【记忆锚点】 “堆排序：时间稳（都是 n log n）、空间省（原地 O(1))，可惜不稳定”。
【易混对比】 与归并排序（第 80 题）同为“三种情况都是 O(n log n)”，区别在
| 堆排序 | 归并排序 | |
|---|---|---|
| 空间 | O(1) | O(n) |
| 稳定性 | ❌ | ✅ |
| 数据访问 | 跳跃（缓存不友好） | 顺序（缓存友好） |
【自测】 在空间受限的场景下，堆排序和归并排序哪个更优？
答：堆排序。堆排序空间 O(1)，归并排序需 O(n) 额外空间。与第 86 题连考。
【知识关联】
- 同库连考：与第 85 题（堆排复杂度）、第 93 题(TopK)、第 75 题（下标）。
- 工程实现:Java
PriorityQueue小顶堆。 - 408 / 国企真题:408 与国网。
- 面试追问:①「建堆为何 O(n)？」（自底向上下沉总和收敛）；②「逐个插入建堆？」(O(n log n))。
【拓展延伸】
完整验算：高度 h 层约 n/2^{h+1} 个结点 × 代价 h → Σ 收敛 O(n)。
变式:d 叉堆。
工程应用：定时器、任务优先级、TopK。
85. 对n个元素进行堆排序时，建初始堆的时间复杂度为( )
标签：【互联网/国企笔试高频】
A. O(n log n) B. O(n) C. O(n²) D. O(log n)
答案：B
【结论】 建初始堆的时间复杂度为 O(n)，选 B。
【逐项辨析】
- A O(n log n)：这是“排序过程”的复杂度，不是建堆。
- B O(n)：正确。 自底向上建堆的总代价是线性的。
- C O(n²)：无依据。
- D O(log n)：这是单次下沉调整的复杂度。
【知识点】 建堆为什么是 O(n) 而不是 O(n log n)?
自底向上建堆:从最后一个非叶结点开始,依次向前做"下沉"调整
关键:不同深度的结点,下沉代价不同
深度 1 的结点(约 n/2 个):下沉 0 次
深度 2 的结点(约 n/4 个):下沉最多 1 次
...
根结点(1 个): 下沉最多 log n 次
总代价 = Σ(该层结点数 × 该层下沉次数)
= n/4×1 + n/8×2 + n/16×3 + ... + 1×log n
< n × (1/4 + 2/8 + 3/16 + ...) < n × 1 = O(n)直观理解：绝大多数结点都在底层，下沉次数很少；只有极少数结点在顶层，下沉次数多。加权求和后收敛到线性。
自底向上建堆示意(数组 [4, 1, 3, 2, 16, 9, 10],n = 7，**以下标 1 起计**：a[1]=4…a[7]=10):
最后一个非叶结点 = 下标 ⌊7/2⌋ = 3（a[3]=3）→ 下沉
下标 2（a[2]=1）→ 下沉
下标 1(值 4)→ 下沉(根结点,下沉次数最多)【记忆锚点】 “建堆 O(n)，排序 O(n log n)”——建堆是“一次性”的线性工作，排序是“n 次取顶”的对数工作。
【易错提醒】 这是一个精确的线性时间复杂度，而非 O(n log n) 的粗略估计 —— 很多人误答 O(n log n)。注意区分：建堆 O(n)，而整个堆排序过程（反复取堆顶并调整）是 O(n log n)。
【易混对比】 注意“逐个插入建堆”与“自底向上建堆”的区别：逐个插入建堆的复杂度是 O(n log n);自底向上建堆才是 O(n) —— 教材与考试通常指的是后者。
【自测】 堆排序的建堆是 O(n)，那整个堆排序的总复杂度是多少？
答：O(n log n)。建堆 O(n) 加上 n 次“取堆顶 + 调整”的 O(n log n)。与第 84 题连考。
【知识关联】
- 同库连考：与第 84 题建堆 O(n) 区分 —— 建堆线性，整个堆排 n log n；与第 83 题不稳定。
- 工程实现：同堆。
- 408 / 国企真题：必考。
- 面试追问:①「空间？」(O(1) 原地）;②「缓存？」（比快排差）。
【拓展延伸】
完整验算:n 次取顶 × log n 调整。
变式：奇偶堆排序并行。
工程应用：内存受限场景。
86. 以下关于排序算法空间复杂度的说法，正确的是( )
标签：【互联网/国企笔试高频】
A. 快速排序的空间复杂度为O(1) B. 冒泡排序的空间复杂度为O(n) C. 堆排序的空间复杂度为O(n) D. 归并排序的空间复杂度为O(n)
答案：D
【结论】 归并排序空间复杂度为 O(n)，该说法正确，选 D。
【逐项辨析】
- A错：快速排序空间复杂度为 O(log n)（递归栈深度），不是 O(1)。
- D 对：归并排序需要 O(n) 的额外空间来合并子序列。
- C错：堆排序空间复杂度为 O(1)（原地排序）。
- B错：冒泡排序空间复杂度为 O(1)（只需一个临时变量）。
【知识点】 各排序算法的空间复杂度（必背）：
| 排序算法 | 空间复杂度 | 是否原地 |
|---|---|---|
| 冒泡排序 | O(1) | ✅ |
| 插入排序 | O(1) | ✅ |
| 选择排序 | O(1) | ✅ |
| 希尔排序 | O(1) | ✅ |
| 堆排序 | O(1) | ✅ |
| 快速排序 | O(log n) | 基本原地（递归栈） |
| 归并排序 | O(n) | ❌ |
| 基数排序 | O(n + r) | ❌ |
为什么快排是 O(log n) 而非 O(1)?
快排是递归实现的,递归调用栈的深度 = 递归树高度
平均情况递归深度为 O(log n) → 栈空间 O(log n)
(最坏情况下递归深度为 O(n),栈空间 O(n))【记忆锚点】 “归并最费空间(O(n))，快排花在栈上(O(log n))，其余都是 O(1)”。
【易混对比】 空间复杂度与稳定性是两个独立维度，常被交叉考查
| 算法 | 空间 | 稳定 |
|---|---|---|
| 堆排序 | O(1) | ❌ |
| 归并排序 | O(n) | ✅ |
| 快速排序 | O(log n) | ❌ |
在空间有限的场景下，堆排序优于归并排序。
【自测】 若要求“空间 O(1) 且时间复杂度稳定为 O(n log n)”，应该选哪个排序？
答：堆排序。空间 O(1)，三种情况都是 O(n log n)。与第 84 题连考。
【知识关联】
- 同库连考：与第 79/80/91 题（归并时间复杂度）、第 82/83 题（稳定性）、第 2 题（复杂度口径）；快排递归栈空间平均 O(log n)、最坏 O(n) 见第 86 题组成排序「时间-空间-稳定」三维表；与第 92 题（基数 O(n+r) 空间）对照。
- 工程实现：归并需辅助数组 O(n)，外部排序用多路归并控制内存缓冲；快排递归栈平均 O(log n)、最坏可到 O(n)；堆排原地 O(1) 常用于嵌入式/内存受限。JDK 对象 TimSort 空间也是 O(n) 量级。
- 408 / 国企真题：408「归并排序空间复杂度」O(n)；「下列排序空间 O(1) 的是」考堆/冒泡/插入/选择。国网喜欢把空间与稳定性交叉设选项。
- 面试追问:①「快排空间为何不是 O(1)？」（递归栈）；②「如何把归并做成 O(1) 额外空间？」（原地归并技巧复杂，实用少；链表归并改指针可 O(1)）；③「既要 O(1) 空间又要最坏 n log n？」（堆排序）。
【拓展延伸】
变式问法:①「归并空间？」（O(n)，本题）；②「快排平均空间？」（O(log n) 栈）；③「冒泡/堆排空间？」（都是 O(1)）。
工程映射：大数据 sort 磁盘多路归并、流式归并合并有序日志、嵌入式选堆排、JVM 栈深度限制与快排最坏。
易错提醒：「原地」≠ 空间严格 O(1)（快排有栈）；归并「稳定但费空间」是经典权衡。选项 C 堆排序空间 O(1)，不要误选。
87. 设一组初始记录关键字序列为 (45, 80, 55, 40, 42, 85)，以第一个记录关键字 45 为基准，按严蔚敏教材的挖坑填数法作一趟快速排序（升序），划分结果为( )
标签：【国企笔试超高频】
A. 42, 40, 45, 80, 85, 55 B. 40, 42, 45, 55, 80, 85 C. 42, 40, 45, 55, 80, 85 D. 42, 40, 45, 85, 55, 80
答案：C
【知识点】 「一趟划分」的不变量与实现差异：一趟划分只保证三件事:
- 基准元素到达最终有序位置；2. 左侧全部 ≤（或 <）基准；3. 右侧全部 ≥（或 >）基准。 不保证左右子段内部有序。
| 实现 | 特点 | 本题 |
|---|---|---|
| 挖坑填数法（严蔚敏） | 交替填坑 | 答案 C |
| Lomuto | 从左扫小的换到前部 | 中间序列可能不同 |
| Hoare | 双指针交换 | 中间序列可能不同 |
「基准归位 + 左小右大」只是必要条件，四个选项都满足它，因此真正决定答案的是题干指定的划分方法：挖坑法保持右侧相对次序为 55, 80, 85，得 C；而双指针交换法（Hoare 型）在同一输入上会得 B。验算方法：数基准下标，检查左右集合，再按指定算法逐步移动。
【分步模拟 · 挖坑填数法】 初始 [45, 80, 55, 40, 42, 85],pivot = 45
| 步骤 | 动作 | 数组状态 | 坑位 |
|---|---|---|---|
| 0 | 挖出 pivot = 45 | [__ , 80, 55, 40, 42, 85] | 0 |
| 1 | high 左移找 < 45：命中 42 | [42, 80, 55, 40, __ , 85] | 4 |
| 2 | low 右移找 > 45：命中 80 | [42, __ , 55, 40, 80, 85] | 1 |
| 3 | high 左移找 < 45：命中 40 | [42, 40, 55, __ , 80, 85] | 3 |
| 4 | low 右移找 > 45：命中 55 | [42, 40, __ , 55, 80, 85] | 2 |
| 5 | low 与 high 相遇于 2，填入 45 | [42, 40, 45, 55, 80, 85] | — |
【逐项辨析】 逐一对照挖坑法的实际移动结果（右侧相对次序应为 55, 80, 85）：
- A (42, 40, 45, 80, 85, 55)：右侧变成 80, 85, 55，与挖坑法的移动结果不符（high 侧是把 55 留在原地、80/85 依次后移，而非把 55 甩到末位）。
- B (40, 42, 45, 55, 80, 85)：这是双指针交换法在同一输入上作一趟划分的结果（实测：先 80↔42、再 55↔40，最后基准与 j 位互换 → 40,42,45,55,80,85）。它满足"基准归位 + 左小右大"，所以若题干不限定方法，本题就有 B、C 两个正确答案——题干已按挖坑法限定，故排除 B。注意：它恰好也是完全有序序列，但"看起来有序"不是排除它的理由。
- C (42, 40, 45, 55, 80, 85)：正确。 与上方逐步模拟一致。
- D (42, 40, 45, 85, 55, 80)：右侧 85, 55, 80 与挖坑法的移动结果不符。
【知识点】 “一趟划分”只保证三件事
① 基准元素归位(45 到了它的最终位置)
② 左侧所有元素 < 基准({42, 40} < 45)
③ 右侧所有元素 > 基准({55, 80, 85} > 45)
左右两侧内部是否有序,一趟划分不管!【易错提醒】 ①「一趟划分」只保证基准归位、左小右大，不保证左右两侧内部有序——看到「已完全有序」的选项不要条件反射地排除：本题的 B（40,42,45,55,80,85）恰好同时是双指针交换法一趟划分的结果；②正因如此，这类题的答案由题干指定的划分方法决定：挖坑填数法得 C、交换法得 B，所以严蔚敏系教材的卷面要按挖坑法做，题干若没写明方法就是命题不严谨；③验算方法：数基准的下标，再检查左右两个集合。国网真题库中此类“求一趟划分结果”的题目出现频率极高。
【记忆锚点】 “一趟划分只管基准归位、左小右大；左右内部乱不乱，不关它的事”。
【易混对比】 两种划分实现的差异
| 实现 | 教材 | 特点 |
|---|---|---|
| 挖坑填数法 | 严蔚敏《数据结构》 | 交替填坑，本题答案 |
| 交换法（左右交换） | 部分教材 / Lomuto 变体 | 结果可能不同 |
但判据不变：基准归位 + 左小右大。 答题时按你所用教材的实现模拟；若拿不准，优先选“基准归位且左右分组正确”的那个。
【自测】 序列 (49, 38, 65, 97, 76, 13, 27, 49)，以第一个元素 49 为基准，按挖坑填数法做一趟划分，结果是？
答：(27, 38, 13, 49, 76, 97, 65, 49)。这是严蔚敏教材的经典例题，国网与 408 均考过。
【知识关联】
- 同库连考：与第 81 题（最坏 O(n²) 的成因）、第 79 题（平均 O(n log n)）构成快排三连；国网真题库「一趟划分」高频。
- 工程实现:Lomuto/Hoare/挖坑三种划分中间序列不同，但「基准归位+左小右大」不变。
- 408 / 国企真题：国网超高频；408 也考。
- 面试追问:①「Hoare 与挖坑结果一定相同吗？」（不一定）；②「一趟后基准下标？」（最终正确位置）。
【拓展延伸】
完整验算（挖坑法，已在原解析逐步给出）：
[45,80,55,40,42,85] pivot=45
最终 [42,40,45,55,80,85]
验:左{42,40}<45,右{55,80,85}>45,基准下标2 ✓
不是完全有序(左右内部未排)变式：以中间元素为基准；三数取中；双轴快排一趟。
工程应用:quickselect 求第 k 大基于同一划分。
88. 冒泡排序在最好情况下的时间复杂度为( )
标签：【互联网/国企笔试高频】
A. O(n) B. O(n log n) C. O(n²) D. O(log n)
答案：A
【结论】 最好情况下时间复杂度为 O(n)，选 A。
【逐项辨析】
- A O(n)：正确。 数据已有序 → 第一趟没有任何交换 → 标志位判定“未发生交换” → 直接结束。只做了 n−1 次比较、0 次移动。
- B O(n log n)：这是快排 / 归并 / 堆排的平均复杂度，与冒泡无关。
- C O(n²)：这是冒泡最坏（逆序）与平均情况，不是“最好”。
- D O(log n)：排序至少要读一遍全部数据，下界是 O(n)，不可能到对数级。
【知识点】 冒泡排序三种情况
| 情况 | 比较次数 | 移动次数 | 复杂度 |
|---|---|---|---|
| 最好（已有序 + 标志位） | n − 1 | 0 | O(n) |
| 最坏（完全逆序） | n(n−1)/2 | n(n−1)/2 × 3 | O(n²) |
| 平均 | ≈ n²/2 | ≈ n²/4 | O(n²) |
「移动次数」两行的口径不同（比较前先统一单位）：最坏行按一次交换 = 3 次赋值计，故为 3 × n(n−1)/2；平均行的 ≈ n²/4 按交换次数计——冒泡只交换相邻逆序对，交换总次数恰等于逆序对数，随机排列的期望逆序对数为 n(n−1)/4（n=2…8 全排列实跑验证：0.5/1.5/3/5/7.5/10.5/14，与 n(n−1)/4 完全一致）。若把平均行也换算成赋值次数，应为 3n(n−1)/4 ≈ 0.75n²。
关键前提：“最好 O(n)”成立的条件是带标志位优化。若不加标志位，冒泡无论如何都要跑满 n−1 趟，最好情况也是 O(n²)。
// 带标志位的冒泡排序
for (i = 0; i < n - 1; i++) {
flag = 0; // 本趟是否发生交换
for (j = 0; j < n - 1 - i; j++)
if (a[j] > a[j+1]) {
swap(a[j], a[j+1]);
flag = 1;
}
if (flag == 0) break; // 无交换 → 已有序 → 提前结束
}【记忆锚点】 “有序表是冒泡的福星、快排的灾星”——冒泡遇到有序表最好 O(n)，快排遇到有序表（且取首元素为基准）最坏退化成 O(n²)。这一对反差是笔试最爱考的。
【易混对比】 常见排序算法的复杂度与稳定性（必背）：
| 算法 | 最好 | 平均 | 最坏 | 稳定性 |
|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n²) | O(n²) | ✅ 稳定 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | ✅ 稳定 |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | ❌ 不稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | ❌ 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | ❌ 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | ✅ 稳定 |
【自测】 下列排序算法中，最好情况时间复杂度为 O(n) 的是( ) A. 简单选择排序 B. 堆排序 C. 直接插入排序 D. 快速排序
答：C。直接插入排序在数据已有序时只需 n−1 次比较、0 次移动。与本题对照记忆。
【知识关联】
- 同库连考：与第 89 题（插入最好 O(n))同型；与第 81 题（快排最坏有序）反差。
- 工程实现：带 flag 的冒泡在已有序时 O(n)；工程几乎不用冒泡。
- 408 / 国企真题：必考。
- 面试追问:①「无 flag 冒泡最好？」（仍 O(n²) 因固定趟）;②「鸡尾酒排序？」（双向冒泡）。
【拓展延伸】
完整验算:flag 版一趟无交换即停。
变式：插入排序最好也是 O(n)。
工程应用：教学与小数据。
89. 插入排序在最好情况下的时间复杂度为( )
标签：【互联网/国企笔试高频】
A. O(n) B. O(n log n) C. O(n²) D. O(log n)
答案：A
【结论】 最好情况下时间复杂度为 O(n)，选 A。
【逐项辨析】
- A O(n)：正确。 数据已有序 → 每个元素只需与前一个比较一次，不需移动。
- B O(n log n)：插入排序达不到这个量级。
- C O(n²)：这是插入排序的最坏（逆序）与平均情况。
- D O(log n)：排序下界是 O(n)。
【知识点】 插入排序三种情况
| 情况 | 比较次数 | 移动次数 | 复杂度 |
|---|---|---|---|
| 最好（已有序） | n − 1 | 0 | O(n) |
| 最坏（完全逆序） | n(n−1)/2 | n(n−1)/2 | O(n²) |
| 平均 | ≈ n²/4 | ≈ n²/4 | O(n²) |
// 直接插入排序
for (i = 1; i < n; i++) {
tmp = a[i];
for (j = i - 1; j >= 0 && a[j] > tmp; j--)
a[j+1] = a[j]; // 元素后移
a[j+1] = tmp; // 插入到正确位置
}“数据基本有序”时插入排序效率非常高 —— 这正是希尔排序把插入排序作为子过程的原因（见第 90 题）。
【记忆锚点】 “插入排序越有序越快”——已有序时退化为“只比较不移动”。
【易混对比】 与第 88 题（冒泡最好 O(n))同型。最好情况能达到 O(n) 的比较排序：直接插入排序、带标志位的冒泡排序 —— 二者都利用了“数据已有序”这一条件。
【自测】 下列哪种排序在数据“基本有序”时效率最高？ A. 快速排序 B. 堆排序 C. 直接插入排序 D. 简单选择排序
答：C。插入排序在基本有序时接近 O(n)。与第 90 题连考。
【知识关联】
- 同库连考：与第 88 题（冒泡最好 O(n)）同属「最好情况 O(n)」家族；与第 81 题（快排已有序却是最坏 O(n²)）形成反直觉对照组，是排序章最爱连考的一对；与第 90 题（希尔排序以插入为子过程）、第 79/80 题（复杂度表）衔接。
- 工程实现：JDK TimSort / C++ introsort 在小规模 run（如 ≤32） 上切换到插入排序，因为「基本有序的短序列」上插入接近 O(n) 且常数极小；归并的合并段若一侧已耗尽，另一侧直接拷贝，也吃到了「有序」红利。工程混合排序的本质就是「分情况用最合适的算法」。
- 408 / 国企真题：408「直接插入排序最好时间复杂度」答案 O(n)；国网计算题常问「已有序时比较 n−1 次、移动 0 次」。干扰项 O(n log n) 来自误套排序下界——下界约束的是最坏/平均的比较排序全体，不否定特定算法在特定初态下的 O(n)。
- 面试追问:①「数据基本有序时用什么排序？」（插入排序，接近 O(n)）；②「二分插入排序？」（比较次数降为 O(n log n)，移动仍 O(n²)，总复杂度不变）；③「为什么有序时快排反而慢？」（首元/固定基准划分极度不平衡）。
【拓展延伸】
变式问法:①「插入排序最好？」（O(n)，本题）；②「最坏/平均？」（都是 O(n²)）；③「冒泡最好为何也是 O(n)？」（带标志位，一趟无交换即停）。
工程映射：自适应排序（adaptive sort）检测「近有序」输入；数据库对已索引小结果集做插入式重排；游戏存档增量排序、日志按时间戳追加后的最后一公里排序，都适合插入。
易错提醒：「最好 O(n)」≠「平均也快」；也不能据此说插入排序比归并「更好」。考点是初态敏感性：同一算法不同初态差一个数量级，呼应第 2 题总纲。
90. 希尔排序是( )的改进版本。
标签：【互联网/国企笔试高频】
A. 冒泡排序 B. 选择排序 C. 插入排序 D. 归并排序
答案：C
【结论】 希尔排序是插入排序的改进版本，选 C。
【逐项辨析】
- A 冒泡排序：希尔排序与冒泡无关。
- B 选择排序：希尔排序不是选择排序的改进。
- C 插入排序：正确。 希尔排序又称“缩小增量排序”，本质是分组插入排序。
- D 归并排序：希尔排序不涉及分治合并。
【知识点】 希尔排序的原理
1. 取一个增量 gap(如 n/2),把数组按下标间隔 gap 分成若干组
2. 对每组分别做插入排序
3. 缩小 gap(如 gap = gap/2),重复上述过程
4. 直到 gap = 1,做最后一次完整的插入排序示例:[49, 38, 65, 97, 76, 13, 27, 49],n = 8
第 1 趟 gap = 4:
分组:(49,76) (38,13) (65,27) (97,49)
组内插入排序后:[49, 13, 27, 49, 76, 38, 65, 97]
第 2 趟 gap = 2:
分组:(49,27,76,65) (13,49,38,97)
组内插入排序后:[27, 13, 49, 38, 65, 49, 76, 97]
第 3 趟 gap = 1:
完整插入排序 → 最终有序核心思想：先通过大增量让元素“大步跳跃”接近目标位置，使数组基本有序；最后 gap = 1 时的插入排序代价很低。
【记忆锚点】 “希尔排序：先分组插排，增量逐渐减半，最后一趟归位”。
【易错提醒】 ①希尔排序的时间复杂度取决于增量序列，通常为 O(n^1.3) 左右（取 n/2 序列时约为 O(n^1.5));②希尔排序不稳定 —— 分组插入会打乱相等元素的相对顺序；③增量序列的最后一个值必须是 1，否则不能保证最终有序。
【易混对比】 希尔排序与插入排序的关系
| 插入排序 | 希尔排序 | |
|---|---|---|
| 增量 | 固定为 1 | 由大到小（最后为 1） |
| 平均复杂度 | O(n²) | 约 O(n^1.3) |
| 稳定性 | ✅ | ❌ |
| 适用 | 数据量小 / 基本有序 | 数据量中等 |
【自测】 希尔排序的增量序列最后一项必须是多少？
答：1。只有 gap = 1 时做完整插入排序，才能保证整个数组有序。与第 89 题连考。
【知识关联】
- 同库连考：与第 89 题（直接插入最好 O(n)）是「改进前 vs 改进后」；与第 91 题（不退化的排序）、第 83 题（稳定性）、第 85 题（建堆 O(n)）同属排序选型族；与附录对比表连看。
- 工程实现：增量序列决定性能， Hibborn(Sedgewick) 增量经验上优于 n/2 折半；间隔子序列各自插入、最后 gap=1 收口。
- 408 / 国企真题:408 常考「下列排序中不稳定/时间复杂度与初态无关」的集合判断；国网考「最后一趟增量必须为 1」。
- 面试追问:①「希尔为什么不稳定？」（跨间隔交换会打乱等值元素相对次序）；②「和快排的取舍？」（希尔实现简单、无递归栈，但最坏仍可到 O(n²) 量级，视增量序列）。
【拓展延伸】
完整验算：以 8 个元素、增量序列 4→2→1 逐步跑一遍，gap=4 比较 4 次、gap=2 与 gap=1 各自完成本组插入，最终有序 —— 见本题【分步推导】。
变式：①「增量序列取 3,2,1 行不行？」（可以，但每轮必须是降序且最后为 1）；②「希尔排序能否做到 O(n log n)？」（取决于增量序列，Shell 原始 n/2 序列最坏 Θ(n²)，Sedgewick/Knuth 序列更好）。
工程应用：嵌入式或对代码体积敏感的场合用插入/希尔；大数据量不用希尔（缓存与最坏不友好），改用快排/归并。
91. 以下哪种排序算法在任何情况下时间复杂度都不会退化为O(n²)?
标签：【互联网/国企笔试高频】
A. 快速排序 B. 冒泡排序 C. 归并排序 D. 插入排序
答案：C
【结论】 归并排序在任何情况下都不退化为 O(n²)，选 C。
【逐项辨析】
- A 快速排序：最坏 O(n²)（数据已有序时）。
- B 冒泡排序：最坏 O(n²)（完全逆序时）。
- C 归并排序：正确。 无论数据初始状态如何，始终为 O(n log n)。
- D 插入排序：最坏 O(n²)（完全逆序时）。
【知识点】 归并排序为什么“不受数据初始状态影响”？
归并排序的结构:
把数组分成两半 → 递归排序左半 → 递归排序右半 → 合并
分治结构与数据内容无关:
无论数据是否有序,总是分到单个元素再逐层合并
递归树高度恒为 ⌈log₂n⌉,每层合并代价恒为 O(n)
→ 总复杂度恒为 O(n log n)| 排序算法 | 最坏复杂度 | 是否受数据初态影响 |
|---|---|---|
| 快速排序 | O(n²) | ✅ 受影响（有序 → 最坏） |
| 冒泡排序 | O(n²) | ✅ 受影响（逆序 → 最坏） |
| 插入排序 | O(n²) | ✅ 受影响（逆序 → 最坏） |
| 选择排序 | O(n²) | ❌ 不受影响（但恒为 O(n²)) |
| 归并排序 | O(n log n) | ❌ 不受影响 |
| 堆排序 | O(n log n) | ❌ 不受影响 |
【记忆锚点】 “归并、堆排序：三种情况一个数(n log n)；快排、冒泡、插入：怕有序 / 逆序”。
【易混对比】 注意本题问“任何情况下都不退化为 O(n²)” —— 堆排序也满足!所以严格说 C 正确（题目为单选，归并是标准答案），但堆排序同样是“最坏 O(n log n)”。两者的差别在稳定性（归并稳定，堆排不稳定）和空间（归并 O(n)，堆排 O(1))。
【自测】 哪些排序算法的最坏情况时间复杂度为 O(n log n)?
答：归并排序、堆排序（快排最坏 O(n²))。与第 80、84 题连考。
【知识关联】
- 同库连考：与第 80 题（最坏最优=归并）、第 79 题（平均 n log n=快排）、第 81 题（快排最坏 n²）、第 84 题（堆排）、第 86 题（归并空间 O(n)）构成排序性质矩阵；与第 2 题（初态影响）相连：归并/堆排/选择是与初态无关一族。
- 工程实现：实时/交易系统禁止最坏平方，选用归并或堆排；introsort=快排+深度监控+堆排兜底，保证最坏 O(n log n)；TimSort 最坏 n log n。「不退化」是高可靠系统的排序合同。
- 408 / 国企真题：408「下列哪种排序在任何情况下时间复杂度不会退化为 O(n²)」标准答案归并（堆排若出现也是对的，本题单选选 C）；常见错选快排（只记得平均快）。
- 面试追问:①「归并为何不退化？」（分治结构与数据内容无关，递归树高恒 ⌈log₂n⌉）；②「堆排也不退化，与归并差别？」（归并稳定但 O(n) 空间；堆排不稳定但 O(1) 空间）；③「选择排序初态影响吗？」（不影响比较次数结构，但恒 O(n²)，不是本题答案）。
【拓展延伸】
变式问法:①「不退化 O(n²) 的是？」（归并，本题；堆排同满足）；②「最坏 O(n log n) 且稳定？」（归并）；③「最坏 O(n log n) 且原地？」（堆排）。
工程映射：SLA 明确「排序延迟上界」的系统；库函数混合排序的兜底层；对抗性输入（故意构造最坏数据）的安全场景。
易错提醒：「任何情况下都不退化」比「平均很快」要求更高；快排有最坏路径。若多选题，归并与堆排都选；单选按题库标准选归并。
92. 基数排序的时间复杂度为( )，其中n为元素个数，d为关键字位数，r为基数。
标签：【互联网/国企笔试高频】
A. O(n log n) B. O(n) C. O(n²) D. O(d × (n + r))
答案：D
【结论】 时间复杂度为 O(d × (n + r))，选 D。
【逐项辨析】
- A O(n log n)：这是比较排序的下界，基数排序不比较。
- D O(d × (n + r))：正确。 d 趟，每趟 O(n + r)。
- C O(n²)：无依据。
- B O(n)：只有在 d 为常数且 r = O(n) 时才退化为线性。
【知识点】 基数排序的复杂度分析
基数排序(以最低位优先 LSD 为例):
对每个关键字位做一趟"分配 + 收集"
共 d 趟(d = 关键字的最大位数)
每趟:分配 O(n) + 收集 O(r)
总复杂度 = d × (n + r)
其中:n = 元素个数,d = 关键字位数,r = 基数(如十进制 r = 10)示例:对 [329, 457, 657, 839, 436, 720, 355] 排序
第 1 趟(个位):按个位分配到 0~9 号桶 → 收集
第 2 趟(十位):按十位分配到 0~9 号桶 → 收集
第 3 趟(百位):按百位分配到 0~9 号桶 → 收集 → 有序
共 d = 3 趟,r = 10当 d 为常数、r = O(n) 时，复杂度退化为 O(n) —— 这是非比较排序能突破 O(n log n) 下界的原因。
【记忆锚点】 “d 趟 × 每趟(n + r)”——趟数乘上“分配 n 个 + 收集 r 个”。
【易混对比】 基数排序的关键性质
| 性质 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(d(n+r)) | d 为常数时可视为 O(n) |
| 空间复杂度 | O(n + r) | 需要 r 个桶 |
| 稳定性 | ✅ 稳定 | 按位分配收集天然保持顺序 |
| 是否比较 | ❌ 不比较 | 属于非比较排序 |
【自测】 基数排序的空间复杂度是多少？
答：O(n + r)。需要 n 个元素的暂存空间和 r 个桶。与第 94 题连考。
【知识关联】
- 同库连考：与第 83 题（基数排序稳定）、第 79 题（比较排序下界 O(n log n)）对照——基数是非比较排序，可突破下界；与第 94 题（不需要进行元素比较的排序）同属非比较排序族；与第 2/3 题复杂度概念衔接：O(d(n+r)) 在 d、r 为常数时才是线性量级。
- 工程实现：Java 没有直接暴露的基数排序 API，但计数排序/基数排序用于 Android 某些路径、大数据整数排序库（如部分 radix sort 实现）；PostgreSQL 对定长短键、内存排序引擎在 d 很小时可选桶/基数思想；JSON/字符串按字典序分位处理也是基数展开。工程上「整数、位数少、范围可控」才用基数。
- 408 / 国企真题：408「基数排序时间复杂度」标准 O(d(n+r))；国网/银行常设「与 O(n log n) 比较」判断题——当 d 为常数且 r=O(n) 时可到 O(n)，故非比较排序不受比较下界限制，这是必背理论点。
- 面试追问:①「基数排序为何能突破 n log n？」（不基于关键字比较，而按位分配）；②「d 很大时还快吗？」（d 若随关键字长度线性增长，复杂度优势消失）；③「空间复杂度？」（O(n+r)，桶+暂存）；④「LSD 与 MSD 区别？」（最低位优先稳定逐位；最高位优先可分治但实现更复杂）。
【拓展延伸】
变式问法:①「基数排序复杂度？」（O(d(n+r))，本题）；②「十进制整数 d 位、r=10 时？」（约 O(d·n)）；③「何时退化为平方？」（题设若强行解释，通常不选 O(n²)；除非错误实现）。
工程映射：限流计数器按位排序、IP 地址分段、固定格式工号/卡号排序、多关键字「先按年再按月再按日」可用三次计数/基数完成，且天然稳定。
易错提醒：选项 B「O(n)」只在 d 常数且 r 规模适中时才「可视为」线性，严格按定义选 D；A 是比较排序下界，基数不属于比较排序，不要套用。
93. 数据流中不断有元素到达，需要实时维护当前最大的 K 个数(TopK)，最优的数据结构是( )
标签：【互联网面试高频】
A. 数组，每次插入后重新排序 B. 大小为 K 的堆 C. 二叉排序树 D. 哈希表
答案：B【结论】 数据流 TopK 最优结构是大小为 K 的堆，选 B。
【逐项辨析】
- A 数组，每次插入后重新排序：每次操作 O(n log n)，数据量大时不可接受。
- B 大小为 K 的堆：正确。 每次操作 O(log K)，可实时维护 TopK。
- C 二叉排序树：维护前 K 大不如堆直接，且需额外处理淘汰。
- D 哈希表：哈希表不维护顺序，无法得到 TopK。
【知识点】 数据流 TopK 的解法
维护一个大小为 K 的小顶堆(堆顶是当前第 K 大)
新元素到达时:
若堆未满 → 入堆
若 x > 堆顶 → 弹出堆顶,x 入堆
否则 → 丢弃
每次操作 O(log K),查询 TopK 时堆内即为答案| 方案 | 单次操作 | 是否适合数据流 |
|---|---|---|
| 每次重新排序 | O(n log n) | ❌ 太慢 |
| 大小为 K 的堆 | O(log K) | ✅ 最优 |
| 平衡二叉搜索树 | O(log n) | 可行但更重 |
【记忆锚点】 “数据流不停来，小顶堆实时守门”——门槛是堆顶，比它大就换人。
【易混对比】 与第 47 题（静态数据 TopK）同型
| 静态数据 | 数据流 | |
|---|---|---|
| 特点 | 数据一次性给定 | 元素不断到达 |
| 方案 | 整体建堆 / 快速选择 | 必须增量维护堆 |
| 复杂度 | 快速选择平均 O(n) | 每次 O(log K) |
“海量数据 TopK / 数据流 TopK”是互联网笔试最高频考点之一。
【自测】 数据流 TopK 为什么用小顶堆而不是大顶堆？
答：因为小顶堆的堆顶是“当前 K 个中的最小值”，也就是门槛；新元素比门槛大才有资格进入。大顶堆的堆顶是最大值，无法做淘汰判断。与第 47 题连考。
【知识关联】
- 同库连考：与第 47 题（静态数据 TopK）、第 14 题（单调队列窗口最值）、第 84 题（堆）同一「堆/选择」思维；与第 2 题（复杂度）呼应：每次 O(log K) 才能撑住数据流。
- 工程实现：Java
PriorityQueue做小顶堆门槛；海量日志 TopK=分治+堆；监控系统实时热点、推荐系统候选粗排、排行榜、限流热点 Key 统计。分布式场景：单机堆 + 汇总再堆。 - 408 / 国企真题：互联网面试/笔试「数据流 TopK 最优结构」标准答案大小为 K 的堆；国企若考「在数组中找第 k 大」也可用快速选择平均 O(n) 或小顶堆 O(n log k)。
- 面试追问:①「为何小顶堆不是大顶堆？」（堆顶是门槛=当前第 K 大，新元素比门槛大才替换）；②「全量数据可在内存时？」（快速选择/建大顶堆弹 K 次也可，但数据流必须增量堆）；③「复杂度？」（n 个流元素共 O(n log K)，空间 O(K)）。
【拓展延伸】
变式问法:①「数据流 TopK 最优？」（大小为 K 的堆，本题）；②「静态数组第 k 大？」（快速选择平均 O(n)）；③「求 TopK 且要按序输出？」（结束后对 K 个元素排序或用平衡结构）。
工程映射：热搜榜、监控告警 top 异常、安全审计高频 IP、数据库慢查询 TopN，都是流式或准流式 TopK。
易错提醒：数据流不能「每次全量重排」；BST 理论可行但淘汰语义不如堆直接；哈希表不维护顺序，无法直接出 TopK。
94. 以下排序算法中，不需要进行元素比较的是( )
标签：【互联网/国企笔试高频】
A. 快速排序 B. 冒泡排序 C. 归并排序 D. 基数排序
答案：D
【结论】 基数排序不需要元素比较，选 D。
【逐项辨析】
- A 快速排序：基于比较（比较 a[i] 与 pivot）。
- D 基数排序：正确。 按位数逐位分配和收集，不进行比较。
- C 归并排序：基于比较（合并时比较两子序列当前元素）。
- B 冒泡排序：基于比较（相邻元素比较）。
【知识点】 比较排序 vs 非比较排序
| 类别 | 算法 | 时间复杂度 | 下界 |
|---|---|---|---|
| 比较排序 | 冒泡、插入、选择、希尔、快排、归并、堆排 | 最坏 Ω(n log n) | O(n log n) |
| 非比较排序 | 基数排序、计数排序、桶排序 | 可达 O(n) | 无此下界 |
为什么比较排序有 O(n log n) 的下界？ 用决策树模型证明
n 个元素共有 n! 种排列,每次比较只有 2 个结果(是 / 否)
决策树至少需要 n! 个叶子 → 树高 ≥ log₂(n!)
由斯特林公式:log₂(n!) ≈ n log₂n
→ 任何比较排序至少需要 Ω(n log n) 次比较非比较排序绕开了“比较”这一操作，因此可以突破该下界 —— 但代价是需要额外的空间与对关键字形式的限制。
【记忆锚点】 “比较排序下界 n log n；不比较的基数 / 计数 / 桶排序能到 O(n)”。
【易混对比】 三种非比较排序的适用场景
| 算法 | 适用条件 | 复杂度 |
|---|---|---|
| 基数排序 | 关键字可分解为有限位数 | O(d(n+r)) |
| 计数排序 | 关键字范围小且为整数 | O(n + k) |
| 桶排序 | 数据均匀分布 | 平均 O(n) |
【自测】 为什么比较排序无法突破 O(n log n) 的下界？
答：因为用决策树模型可以证明：n 个元素有 n! 种排列，决策树至少有 n! 个叶子，树高至少为 log₂(n!) ≈ n log₂n。408 与互联网笔试高频。
【知识关联】
- 同库连考：与第 92 题（基数排序复杂度 O(d(n+r))）同一算法；与第 79/82/83/86/91 题（比较排序的复杂度、稳定性、空间）构成「比较 vs 非比较」对照；与第 2/3 题（复杂度下界概念）衔接。
- 工程实现：整数/定长短键可用计数、基数、桶排序突破 n log n；Java 对象排序因无法「按位拆」且要稳定，仍走 TimSort；数据库对小范围整数列、内存引擎 sort 会选计数/基数路径。
- 408 / 国企真题：408「下列排序中不基于比较的是」答案基数/计数/桶排序；「比较排序下界」Ω(n log n) 必背。国网判断题：「所有排序算法时间复杂度都不低于 O(n log n)」——错，非比较排序可以更低。
- 面试追问:①「基数为何不比较？」（按位分配+收集）；②「下界证明思路？」（决策树 n! 叶子，高 ≥ log₂(n!)）；③「非比较排序代价？」（额外空间 O(n+r)/O(n+k)，且对关键字形式有限制）。
【拓展延伸】
变式问法:①「不需要元素比较的是？」（基数排序，本题）；②「计数排序适合？」（关键字范围小的整数）；③「桶排序适合？」（近似均匀分布）。
工程映射：IP/工号/卡号按位排序、多关键字稳定分位处理、限流计数器、旧式打孔卡基数排序是该思想的历史原型。
易错提醒：「不比较」≠「不花时间」，是分配收集的代价；D 正确的同时要知道它稳定且复杂度含 d、r。比较排序下界不要套到基数上。