归并排序 vs 快排 vs 堆排：一张表看懂差异

面试高频题：三种 O(n log n) 排序到底怎么选？

图：归并/快排/堆排的核心差异速查

# 经验法则：
# - 要稳定 + 不怕额外空间 → 归并排序（外部排序首选）
# - 要原地 + 平均最快 → 快排（记得随机化 pivot 防退化）
# - 要原地 + 最坏也有保证 + 实时系统 → 堆排序

归并排序是唯一同时“稳定 + 最坏 O(n log n)”的，但代价是 O(n) 辅助空间；快排平均最快却最坏 O(n²) 且不稳定；堆排原地且最坏有保证但不稳定。

相关推荐：主定理 · 归并为什么稳 · 分治思想