常见的排序算法有哪些？它们的时间复杂度和稳定性如何对比？
简化版
排序分比较排序和非比较排序两大类。比较排序（冒泡、选择、插入、希尔、快排、归并、堆排）的时间下界是 O(n log n)；其中快排、归并、堆排达到这个下界。非比较排序（计数、桶、基数）利用值域信息，能做到 O(n) 级，但有使用限制。选型看：数据量、是否要稳定、内存是否受限、数据是否近乎有序、值域大小。
详细版
| 算法 | 平均 | 最坏 | 最好 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n)* | O(1) | ✅ 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | ❌ 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | ✅ 稳定 |
| 希尔排序 | O(n^1.3)~ | O(n²) | O(n) | O(1) | ❌ 不稳定 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | ❌ 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ 稳定 |
| 桶排序 | O(n+k) | O(n²) | O(n) | O(n+k) | ✅ 稳定 |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | ✅ 稳定 |
（*冒泡最好 O(n) 需加「一轮无交换就退出」的优化；k 为值域大小，d 为最大位数。）
稳定性口诀：稳定的是「冒插归，计桶基」（冒泡、插入、归并、计数、桶、基数）；不稳定的是「选希快堆」（选择、希尔、快速、堆排）。
完整版教学
一、两大类：比较排序 vs 非比较排序
排序算法按「是否通过元素间比较来决定顺序」分成两类，这是理解排序全景的第一刀：
- 比较排序：只靠「谁比谁大」来排。冒泡、选择、插入、希尔、快排、归并、堆排都是。它们的通用性最强（只要元素可比较就能排），但受一个理论下界约束。
- 非比较排序：不比较元素，而是利用「元素的值本身」当索引或分组依据（计数、桶、基数）。它们能突破比较排序的下界、达到线性，但要求元素能映射到有限值域（通常是整数或定长串）。
二、为什么比较排序的下界是 Ω(n log n)
这是排序里最重要的理论结论。任何基于比较的排序，都可以画成一棵决策树：每个内部节点是一次「a 和 b 比较」，每个叶子对应一种可能的排列结果。n 个元素有 n! 种排列，所以决策树至少有 n! 个叶子。一棵二叉树有 L 个叶子，高度至少 log₂L。于是树高 ≥ log₂(n!)，而由斯特林公式 log₂(n!) = Θ(n log n)。
树高就是「最坏情况下要做的比较次数」，所以任何比较排序最坏至少 Ω(n log n)。快排、归并、堆排达到了这个下界，已是比较排序的理论最优。这也解释了为什么非比较排序能更快——它们根本不做比较，不受这个下界限制。
三、O(n²) 家族：简单排序
冒泡、选择、插入是三个「平方级」的简单排序，它们代码短、原地、适合小数据或教学：
- 冒泡：相邻比较交换，大的往后冒。稳定，可优化到近乎有序时 O(n)。
- 选择：每轮选最小的放前面。不稳定，且不管数据如何都是 O(n²)（即使已排序也要扫）。
- 插入：把元素插到前面有序部分。稳定，近乎有序时接近 O(n)，实际中小数组表现很好。
它们的共同点是平均 O(n²)，数据一大就不够看。希尔排序是插入排序的改进，用分组突破了 O(n²)。
四、O(n log n) 家族：高效排序（重点）
快排、归并、堆排是三大主力，都达到 O(n log n)，但特性差异很大，是面试对比的核心：
- 快速排序：分治 + 基准 partition。平均最快（常数小、缓存友好、原地），但最坏 O(n²)（基准选得差、数据已排序），不稳定。是实际应用最广的排序。
- 归并排序：分治 + 合并。任何情况都稳定 O(n log n)、且稳定排序，但需要 O(n) 辅助空间。适合要求稳定、或链表排序、或外部排序。
- 堆排序：建堆 + 反复取堆顶。最坏也 O(n log n)、且原地 O(1) 空间，但缓存不友好（跳跃访问），实际常比快排慢，不稳定。适合「要保证最坏性能又要省内存」。
一句话对比：快排平均最快，归并稳定但费空间，堆排省空间且最坏有保证但实际较慢。
五、O(n) 家族：非比较排序
计数、桶、基数利用值域信息达到线性，但有前提：
- 计数排序：统计每个值出现次数。O(n+k)，适合值域 k 不大的整数（如年龄、分数）。k 很大时空间爆炸。
- 桶排序：分到若干桶、桶内排序再合并。数据均匀分布时接近 O(n)。
- 基数排序：按位（个、十、百…）逐位用稳定排序。适合整数或定长字符串。
它们都稳定，但通用性不如比较排序（依赖数据形态/值域）。
六、工程中怎么选
- 通用、追求平均速度 → 快速排序（多数标准库的默认，如 C 的
qsort、Java 基本类型的Arrays.sort）。 - 要稳定 / 对象排序 → 归并排序（Java 对象
Arrays.sort用 TimSort，是归并+插入的混合稳定排序）。 - 要最坏性能保证 + 省内存 → 堆排序。
- 数据量小 / 近乎有序 → 插入排序（很多库在小数组时切到插入）。
- 整数、值域小 → 计数 / 基数排序。
实际标准库多是混合排序：如 TimSort（归并+插入）、introsort（快排+堆排+插入），取各家所长、规避各家最坏。
七、把不变量、推演与工程边界落到代码上
算法正确性的核心不是记住某个 while，而是始终维护这个不变量：选择算法要同时满足输入规模、分布、稳定性、空间和最坏延迟要求。
对应的状态推进是：先区分比较排序与利用值域结构的非比较排序，再按约束选择实现。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。
初始化边界与状态
while 尚未结束:
根据当前状态作出唯一可证明安全的选择
更新边界、计数或局部结构
断言不变量仍然成立
返回不变量在终止状态下推出的答案复杂度不能只背一个符号。比较排序决策树至少有 n! 个叶子，高度 Ω(log(n!))=Ω(n log n)。
带数字走一遍：n=10⁶ 时 n² 约 10¹² 次操作，而 n log₂n 约 2×10⁷，量级差异巨大。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。
| 核对项 | 结论 |
|---|---|
| 前提 | 通用工程代码应优先使用标准库并理解其对象/基本类型策略 |
| 时间复杂度 | 平方级、n log n 或带参数的线性复杂度 |
| 额外空间 | 从 O(1) 到 O(n)，视算法而定 |
| 关键边界 | 不能只看平均复杂度；还要检查稳定性、辅助空间、最坏情况和数据分布 |
| 替代方案 | 标准库排序通常比手写单一算法更可靠 |
易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。
实现完成后至少检查五类用例：
- 空输入或题目允许的最小规模，验证初始化不会越界。
- 单元素与两个元素，验证循环条件和最后一次推进。
- 大量重复值，验证相等分支、稳定性或去重语义。
- 已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
- 上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。
八、常见误区与追问
- 误区：只要记住模板就适用于所有输入。 本题成立的前提是“通用工程代码应优先使用标准库并理解其对象/基本类型策略”，前提被破坏后必须换算法或重新证明。
- 误区：复杂度只写 平方级、n log n 或带参数的线性复杂度 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“比较排序决策树至少有 n! 个叶子，高度 Ω(log(n!))=Ω(n log n)”。
- 误区：重复值和边界值不会改变代码。 不能只看平均复杂度；还要检查稳定性、辅助空间、最坏情况和数据分布。
- 追问：为什么每次推进不会漏掉答案？ 因为始终维护“选择算法要同时满足输入规模、分布、稳定性、空间和最坏延迟要求”，被舍弃区域已由顺序或状态关系证明不可能更优。
- 追问：用一个数字例子怎么讲？ 可以从“n=10⁶ 时 n² 约 10¹² 次操作，而 n log₂n 约 2×10⁷，量级差异巨大”开始，逐轮写出状态与被排除区间。
- 追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“标准库排序通常比手写单一算法更可靠”。
- 追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。
九、加强记忆
排序分比较排序（下界 Ω(n log n)，由 n! 种排列的决策树高度推出）和非比较排序（利用值域达 O(n)）。三大高效排序：快排平均最快但最坏 O(n²)、不稳定、原地;归并全场景 O(n log n)、稳定、费 O(n) 空间;堆排最坏 O(n log n)、原地、但缓存差实际慢、不稳定。稳定的记「冒插归+计桶基」,不稳定记「选希快堆」。选型看数据量、稳定性、内存、有序度、值域。