排序 高频追问 Q&A

1. Q: 快排最坏为什么是 O(n^2)？

A: 每次分区极不均衡（如总选到最大/最小）会退化为链式递归。

2. Q: 归并排序为什么稳定？

A: 合并时相等元素按原先顺序先后写入。

3. Q: 什么是原地排序？

A: 除少量辅助变量外不依赖额外线性空间。

4. Q: 稳定性在业务里有意义吗？

A: 多关键字排序时非常重要，先按次关键字稳定排，再按主关键字排。

5. Q: 面试怎么选排序算法？

A: 先看规模、稳定性、内存限制，再说明工程常用混合策略。