极高 进阶
排序算法总结#
一句话答案#
快排 O(nlogn) 平均最快但不稳定，归并 O(nlogn) 稳定但需额外空间，堆排 O(nlogn) 原地但不稳定。
核心要点
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 快排 | O(nlogn) | O(n²) | O(logn) | ❌ |
| 归并 | O(nlogn) | O(nlogn) | O(n) | ✅ |
| 堆排 | O(nlogn) | O(nlogn) | O(1) | ❌ |
| 冒泡 | O(n²) | O(n²) | O(1) | ✅ |
| 插入 | O(n²) | O(n²) | O(1) | ✅ |
快排核心： 选 pivot → partition → 递归 场景选择： 大数据快排，需稳定归并，TopK 用堆
面试回答（2分钟版）
排序算法面试重点关注三个O(nlogn)算法。快速排序平均性能最好，核心是选pivot做partition把数组分成两半然后递归，空间O(logn)递归栈开销，但不稳定且最坏情况O(n2)，比如数组已有序时每次pivot选到最小值。避免退化的方法是随机选pivot或者三数取中法。归并排序时间复杂度稳定O(nlogn)不会退化，而且是稳定排序，缺点是需要O(n)额外空间做合并。堆排序也是O(nlogn)且空间O(1)原地排序，但不稳定且对缓存不友好因为数组访问跳跃性大。实际场景选择：大数据量通用排序优先快排，Java的Arrays.sort对基本类型用双轴快排对对象用TimSort即归并排序的优化版保证稳定性。TopK问题用堆排最合适，建一个大小为K的小顶堆时间O(nlogK)。手写快排的关键点是partition函数的实现和递归终止条件。
追问与易错
追问方向：
- “快排最坏情况 O(n2) 怎么避免？”→ 三数取中选 pivot + 随机化 pivot + 小数组切换插入排序；Java 的 DualPivotQuicksort 还用了双轴优化
- “稳定性为什么重要？”→ 多关键字排序时，稳定排序能保持前一轮排序的相对顺序；例如先按价格排再按销量排，稳定排序可保证同销量商品仍按价格有序
- “面试手写快排关键点？”→ partition 函数要写对：选 pivot、双指针交换、返回分界下标；注意处理等于 pivot 的元素（随机分到两边避免退化）和递归终止条件
易错点：
- ❌ 快排在所有场景最快——有序数组退化到 O(n2)
- ❌ 所有 O(nlogn) 排序效果一样——稳定性和空间不同