排序算法比较 · 融合风（象牙 + Obsidian 入口）

速查

平均最快快速排序 $O(n\log n)$；最坏仍 $O(n\log n)$ 的只有堆 / 归并；唯一 $O(n\log n)$ 且稳定的是归并；不基于比较的基数 / 计数 / 桶可突破 $O(n\log n)$。稳定性口诀：选快希堆不稳定。

内部排序算法总览 ▾

算法	平均时间	最好	最坏	空间	稳定
直接插入	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	✅
折半插入	$O(n^2)$	$O(n\log n)$	$O(n^2)$	$O(1)$	✅
希尔排序	$O(n^{1.3})$	—	$O(n^2)$	$O(1)$	❌
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	✅
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	❌
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	❌
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	❌
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	✅
基数排序	$O(d(n+r))$	—	$O(d(n+r))$	$O(n+r)$	✅

算法分类：插入（直接 / 折半 / 希尔）、交换（冒泡 / 快速）、选择（简单选择 / 堆）、归并、基数。

关键性质 ▾

比较维度	最优算法
平均时间最快	快速排序
最坏时间保证	堆排序、归并排序
空间最少	插入 / 冒泡 / 选择 / 希尔 / 堆（$O(1)$）
必须稳定	归并排序（$O(n\log n)$ 稳定）
数据量小 $(n\leq50)$	直接插入排序
基本有序	直接插入或冒泡
数据量大	快速 / 归并 / 堆
关键字范围小	基数或计数排序

稳定性记忆口诀 ▾

必背口诀「选快希堆不稳定」（选择、快速、希尔、堆排序不稳定）。其余都稳定：插入、冒泡、归并、基数。

易错点 ▾

注意

快速排序平均最快，但最坏 $O(n^2)$；堆排序最坏也 $O(n\log n)$ 但平均略慢
归并排序是唯一 $O(n\log n)$ 且稳定的排序（需 $O(n)$ 额外空间）
基数排序时间不含比较，是 $O(d(n+r))$
希尔排序时间复杂度与增量序列有关，最坏 $O(n^2)$

核心结论 ▾

必背基于比较的排序时间下界 $O(n\log n)$（决策树模型）。平均性能快排最优；最坏保证堆 / 归并；稳定且 $O(n\log n)$ 只有归并；基数 / 计数 / 桶可突破下界；需综合时间、空间、稳定性、数据特征选择。

记忆卡片 ▾

哪些排序不稳定？

选快希堆（选择、快速、希尔、堆）。

最坏仍 $O(n\log n)$ 的排序？

堆排序、归并排序。

平均性能最好？

快速排序。

唯一 $O(n\log n)$ 且稳定？

归并排序（需 $O(n)$ 辅助空间）。

交互动画 · 稳定性分类 ▾

点击按钮筛选：稳定的有插/冒/归/基，不稳定的有选/快/希/堆

相关知识点

sorting-algorithm-applications heap-sort quick-sort

↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。