排序
排序按比较规则重排元素。本文负责分区、归并、稳定性和排序边界。
1. 面试核心
先记住这几条，再读正文- 稳定性。 稳定排序保留比较结果相等项的原始相对顺序。因此，先按次要字段排序，再按主要字段稳定排序，可以保留两层顺序。卡 · 稳定性与多字段排序
- 比较排序下界。 比较排序最坏比较次数下界为 Ω(n log n)。
- 快速排序复杂度。 随机化快排期望 O(n log n)，最坏仍为 O(n²)。卡 · 分区与合并
- 重复键处理。 三路快排把键分成小于、等于和大于枢轴三组，递归只处理两侧。大量重复键由此不再反复参与分区。卡 · 重复值与三路分区
2. 分区与合并
快速排序选取枢轴，分区后递归处理两侧。两侧均衡时有 O(log n) 层。若每次只排除一项，总比较量为 n+(n-1)+…，达到 O(n²)。随机化减少持续坏划分的概率。
归并排序递归排好两半，再按较小者依次合并。每层处理 O(n) 项，共 O(log n) 层。标准数组实现时间 O(n log n)，辅助数组空间 O(n)。调用栈另占 O(log n)。
3. 性质比较
| 方法 | 最坏时间 | 典型辅助空间 | 常见实现稳定性 |
|---|---|---|---|
| 插入排序 | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n²) | 栈最坏 O(n) | 不稳定 |
| 归并排序 | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(1) | 不稳定 |
插入排序只移动严格更大的项，可保留相等项顺序。归并遇到相等项时优先取左侧，也能保持稳定。比较次数下界来自 n! 种排列的决策树高度。计数排序利用值域 U，可做到 O(n+U)，另需值域空间。
3.1 稳定性与多字段排序
若员工先按入职时间排序，再按部门稳定排序，同部门仍按入职时间排列。稳定性相对比较器的相等关系定义。Java 21 的 Arrays 对象数组排序保证稳定。
3.2 重复值与三路分区
将区间分成小于、等于、大于枢轴的三段。相等段已就位，只递归处理两侧。全部值相等时，一轮线性分区即可结束。
递归处理较短一侧，再循环处理较长一侧，可将栈深度限制为 O(log n)。这项优化控制栈空间，最坏比较次数仍可为 O(n²)。
4. 使用边界
小数组或接近有序的数组可考虑插入排序。选择算法还需确认是否允许修改输入。
只取部分极值时，可使用堆。
比较器使用 Integer.compare，避免减法溢出。它还需满足反对称符号关系与传递性。测试排序应同时检查非递减顺序和元素多重集。
5 · 面试题卡片
本页题目与参考回答
5.1 快速排序为何会退化到 O(n²)？
考察重点：分区平衡性与最坏上界。
相关内容：分区与合并。
参考回答
每次只排除一个元素时，比较总量为 O(n²)。
其余元素反复参与分区，规模只减少一项。随机枢轴改善期望成本，最坏上界仍为 O(n²)。
5.2 稳定排序如何支持多字段排序？
考察重点：比较相等与原始顺序。
相关内容：稳定性与多字段排序。
参考回答
先按次要字段排序，再按主要字段稳定排序即可。
主要字段相同的项会保留次要字段的顺序。归并时相等优先取左项，就是稳定性的具体实现。
5.3 大量相等键时，三路快排有什么作用？
考察重点：相等区间与递归范围。
相关内容：重复值与三路分区。
参考回答
三路分区把相等键集中，后续只处理两侧。
全相等输入只需一次 O(n) 扫描。比较器需正确表达相等关系，分区后两侧也要严格缩小。