排序算法

1. 一句话总结

排序面试重点是时间、空间、稳定性、是否原地和适用场景，快排、归并、堆排是核心。

2. 通俗解释

快排按基准分区，归并先拆再合，堆排每次取堆顶，插入排序适合小规模或几乎有序数据。

3. 核心概念

• 稳定性：相等元素相对顺序是否保持。
• 原地排序：是否只用很少额外空间。
• 快排：分区后递归排序左右部分。
• 归并：分治拆分，再有序合并。
• 堆排：建堆后反复取堆顶。
• 非比较排序：计数、桶、基数排序。

4. 底层原理

• 比较排序下界是 O(nlogn)。
• 快排平均 O(nlogn)，基准差时最坏 O(n²)。
• 归并稳定且时间稳定 O(nlogn)，但需要 O(n) 空间。
• 堆排序原地 O(nlogn)，但不稳定。
• 稳定性在多关键字排序中有价值。

5. 面试标准回答

排序算法要从复杂度、稳定性、空间和场景回答。快速排序通过基准分区实现，平均 O(nlogn)，常数小，但基准选择差时可能退化 O(n²)。归并排序通过分治和合并实现，时间稳定 O(nlogn)，并且稳定，但需要 O(n) 额外空间。堆排序利用堆顶最值反复调整，时间 O(nlogn)，空间 O(1)，但不稳定。稳定排序在多字段排序中有意义，Top K 场景通常不需要全量排序。

6. 高频追问

追问 1：排序算法面试第一句话怎么答？

先给结论：稳定性：相等元素相对顺序是否保持。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

比较排序下界是 O(nlogn)。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：快排平均 O(nlogn)，基准差时最坏 O(n²)。

追问 5：实际开发中怎么体现？

数据库 order by 可能涉及内存排序和外部排序。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• 数据库 order by 可能涉及内存排序和外部排序。
• 多个有序日志文件合并适合归并思想。
• Top K 应优先考虑堆而不是全排序。

9. 背诵速记

排序记五维：时间、空间、稳定性、原地、场景。快排平均快但可能退化，归并稳定但用空间，堆排原地但不稳定。Top K 常用堆。