八种常见的排序算法
（面试/考研/刷题最常考的8种）
以下是按照出现频率和重要性排序的8种经典排序算法的对比与核心要点：
| 排序算法 | 时间复杂度（最好/平均/最坏） | 空间复杂度 | 稳定排序？ | 原地排序？ | 适用场景 / 特点 | 是否必须掌握（面试/考研） |
|---|---|---|---|---|---|---|
| 冒泡排序 | 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 log n) ~ O(n^{1.3}) | O(1) | 否 | 是 | 插入排序的升级版，中等数据量实用 | ★★★☆☆ |
| 归并排序 | O(n log n) / O(n log n) / O(n log n) | O(n) | 是 | 否 | 稳定、外部排序、大数据分治思想代表 | ★★★★★ |
| 快速排序 | O(n log n) / O(n log n) / O(n²) | O(log n) ~ O(n) | 否 | 是 | 综合性能最强、实际最常用排序算法 | ★★★★★ |
| 堆排序 | O(n log n) / O(n log n) / O(n log n) | O(1) | 否 | 是 | 原地 + 最坏情况稳定 O(n log n) | ★★★★☆ |
| 计数排序 | O(n + k) | O(n + k) | 是 | 否（通常） | 整数范围有限时极快（桶排序基础） | ★★★★☆ |
快速记忆分类口诀
- O(n²) 家族（小学奥数级别）：冒泡、选择、插入、希尔
- O(n log n) 家族（大学算法课核心）：归并、快排、堆排
- 线性时间家族（特定条件神器）：计数、桶、基数
八大排序一句话核心思想
| 算法 | 一句话核心思想 | 优化方向 / 关键技巧 |
|---|---|---|
| 冒泡排序 | 相邻比较，不断把最大/最小元素“冒泡”到一端 | 提前终止（已排序标记） |
| 选择排序 | 每次从未排序部分选出最小/最大，放到已排序部分开头 | 无明显优化空间 |
| 插入排序 | 把元素插入到前面已排好序的部分（像打扑克理牌） | 二分插入、提前终止 |
| 希尔排序 | 插入排序的加强版，先大步长分组排序，再逐步减小步长 | 步长序列选择（关键影响性能） |
| 归并排序 | 分而治之：先递归分成两半，排好序后再合并 | 自底向上迭代版可节省空间 |
| 快速排序 | 选一个“枢轴”（pivot），把小于它的放左边，大于放右边 | 三数取中 / 随机化 / 双指针 / 小数组切换插入 |
| 堆排序 | 先建最大/最小堆，然后反复把堆顶放到末尾调整 | 原地、稳定O(n log n) |
| 计数排序 | 用一个计数数组统计每个值出现的次数，再按顺序输出 | 适用于整数、小范围、已知取值范围 |
常见面试/笔试对比题型（建议都手写实现）
- 写出快速排序（双指针 / 三数取中 / 随机化 pivot）
- 归并排序（递归版 + 迭代版都要会）
- 手写堆排序（建堆 + 调整堆）
- 插入排序 + 希尔排序（步长怎么选？）
- 计数排序（完整流程 + 稳定性证明）
- 哪几种排序是稳定的？哪几种是原地的？
- 快速排序最坏情况如何避免？（随机化 / 三数取中）
- 给定一个近乎有序的数组，哪种排序最快？
快速选择建议（背下来就能应对大部分场景）
| 数据规模 & 特性 | 首选算法 |
|---|---|
| n ≤ 50 | 插入排序 |
| n ≤ 1000，且近乎有序 | 插入排序 / 希尔排序 |
| n 较小，写操作代价很高 | 选择排序（极少） |
| 一般情况，追求平均最快 | 快速排序（随机化 pivot） |
| 必须稳定排序 | 归并排序 |
| 内存紧张，必须原地 | 快速排序 / 堆排序 |
| 数据是整数且范围有限 | 计数排序 / 基数排序 |
| 必须保证最坏情况 O(n log n) | 归并排序 / 堆排序 / TimSort（Python/Java用的） |
需要我帮你把其中某一个算法写出完整注释版代码（C++/Python 都可以），还是想看某几种算法的稳定性/原地性/时间空间复杂度推导过程？
直接告诉我具体想看哪一个～
