排序算法比较

把本部分算法放在同一张表里对照，便于复习与选型。

对照表（常见教材结论）

算法	平均	最坏	空间	稳定
直接插入	$O(n^2)$	$O(n^2)$	$O(1)$	是
希尔	依赖增量	依赖增量	$O(1)$	否
冒泡	$O(n^2)$	$O(n^2)$	$O(1)$	是
快速	$O(n \log n)$	$O(n^2)$	$O(\log n)$～	否
简单选择	$O(n^2)$	$O(n^2)$	$O(1)$	否
堆排序	$O(n \log n)$	$O(n \log n)$	$O(1)$	否
归并	$O(n \log n)$	$O(n \log n)$	$O(n)$	是
基数	$O(d(n+r))$	同左	$O(n+r)$	是

具体实现细节会导致细微差别；以你的代码与教材证明为准。

选型直觉

需求	更合适
小数组 / 基本有序	插入
平均性能、内存紧	快排（注意最坏）
要最坏保证且原地	堆排序
要稳定	归并（或仔细实现的插入/冒泡）
特殊整数关键字	考虑基数
工程默认	std::sort；要稳定用 std::stable_sort

复习检查清单

• 能默写插入、快排分区、归并合并
• 能说明稳定性定义并各举一例
• 能解释快排最坏与改进思路

小结

没有「永远最好」的排序。按规模、稳定性、空间与是否最坏敏感来选。

全部排序专题结束后，可回到 学习资源 扩展阅读。