排序 高频追问 Q&A

排序 高频追问 Q&A

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

A: 每次分区极不均衡（如总选到最大/最小）会退化为链式递归。（深入阅读：快排与归并排序对比）

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

A: 合并时相等元素按原先顺序先后写入。（深入阅读：快排与归并排序对比）

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

A: 除少量辅助变量外不依赖额外线性空间。（深入阅读：排序基础知识速览、基础排序）

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

A: 多关键字排序时非常重要，先按次关键字稳定排，再按主关键字排。（深入阅读：排序基础知识速览、快排与归并排序对比）

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

A: 先看规模、稳定性、内存限制，再说明工程常用混合策略。（深入阅读：排序基础知识速览、堆排与希尔排序速览）