排序
排序按比较规则重新组织元素，为二分查找、去重和区间处理建立顺序。选择排序方法需要同时考虑时间上界、稳定性、额外空间和数据规模。
1. 面试核心
先记住这几条，再读正文- 稳定排序保留相等键的原始相对顺序。
- 比较排序的最坏比较次数下界为 Ω(n log n)，非比较排序依赖额外输入约束。
- 快速排序平均 O(n log n)、最坏 O(n²)；归并排序保证 O(n log n)。
2. 分区与合并
快速排序选定枢轴，把元素分到两侧，再分别排序。若每次划分均衡，层数接近 log n；若每次只排除一个元素，总比较量变成 n+(n-1)+…，达到 O(n²)。随机化降低持续坏划分的概率，但不改变最坏上界。
归并排序先把两个子区间排好，再用双指针取较小元素合并。每层合并总共处理 O(n) 个元素，共 O(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) | 不稳定 |
归并时相等键优先取左半区元素，才能保留原顺序。稳定性属于具体实现的保证，不能只看算法名称。计数排序可以达到 O(n+U)，但需要键范围 U 足够小，并付出相应空间。
4. 使用边界
面试先确认是否允许修改输入、是否要保留重复元素顺序，再选择实现。几乎有序的小数组可能适合插入排序；只取 Top K 时，排序全部数据未必划算，可以考虑堆。
比较器必须保持一致的大小关系。不要用 a-b 比较任意 int，差值溢出会颠倒顺序；使用 Integer.compare(a,b)。验证排序时，除了检查输出有序，还应检查元素多重集合没有变化。
5 · 面试题卡片
先想答案，再翻面题目来自公开面经。点任意一张进入翻卡，可左右切换，看完回到这里。
逐张翻看 1 张 →5.1 快速排序最坏的时间复杂度是多少，为什么会退化？
出现公司：美团
考察重点：合并相等键的顺序，以及分区平衡性对快速排序复杂度的影响。
参考回答
快速排序依赖分区平衡性，若每次枢轴都是极值，剩余子问题只缩小一个元素，总工作达到 O(n²)。随机枢轴改善发生概率，不能把最坏情况直接改写为 O(n log n)。