十种常见排序算法：复杂度、适用场景与核心逻辑
十种常见排序算法：复杂度、适用场景与核心逻辑
排序算法没有绝对的“最强者”。快速排序很适合通用的内存排序，归并排序能够稳定地保证 O(n log n)，而计数排序、桶排序和基数排序则可以利用数据特征，在特定场景下接近 O(n)。
本文按照这些算法在实际开发中的常见程度大致排序。这个顺序不是严格排名：不同语言的标准库和不同业务场景会采用不同方案，而且实际排序函数通常会组合多种算法，而不是只使用一种纯算法。
文中的符号含义如下：
- n：待排序元素的数量。
- k：取值范围大小、桶数量，或单个位上的可能取值数。
- d：基数排序需要处理的位数。
## 一、复杂度总览
| 排序算法 | 最好时间 | 平均时间 | 最坏时间 | 额外空间 | 稳定性 |
|---|---😐---😐---😐---😐---|
| 快速排序 | O(n log n) | O(n log n) | O(n²) | 平均 O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 可以稳定 |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 |
| 桶排序 | O(n + k) | O(n + k) | O(n²) | O(n + k) | 取决于桶内排序 |
| 希尔排序 | 取决于间隔序列 | 常见约 O(n^1.3) 至 O(n^1.5) | 简单间隔下 O(n²) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
> 说明：计数排序若只对整数值进行原地回写，额外空间可以写作 O(k)；为了稳定地排序带有附属信息的记录，通常还需要 O(n) 的输出数组，因此表中写作 O(n + k)。
## 二、适用场景总览
| 排序算法 | 适用场景 | 主要限制 |
|---|---|---|
| 快速排序 | 通用内存排序；不要求稳定；追求平均性能 | 极端划分时会退化为 O(n²) |
| 归并排序 | 要求稳定；链表排序；外部排序；需要可靠的最坏复杂度 | 数组排序通常需要 O(n) 额外空间 |
| 插入排序 | 小数组；数据基本有序；作为高级排序的小区间优化 | 数据量大且无序时是 O(n²) |
| 堆排序 | 内存受限，同时要求最坏时间为 O(n log n) | 缓存局部性较差，通常没有快排快 |
| 计数排序 | 年龄、成绩、等级等取值范围较小的整数 | 取值范围 k 很大时浪费时间和内存 |
| 基数排序 | 固定长度整数、手机号、邮编或定长字符串 | 需要能拆分成有限的“位” |
| 桶排序 | 数值范围已知且分布比较均匀 | 数据集中到少数桶时可能退化 |
| 希尔排序 | 中小规模数组；内存有限；实现需保持原地 | 复杂度依赖间隔序列，且不稳定 |
| 冒泡排序 | 教学；极小规模数据；检测数组是否已经有序 | 大多数实际场景效率较低 |
| 选择排序 | 教学；数据很少；写入或交换成本明显高于比较成本 | 即使数组已有序也需要 O(n²) 次比较 |
## 三、算法逻辑与例子
### 1. 快速排序
核心逻辑： 选择一个基准值 pivot，把小于基准值的元素放到左边，把大于基准值的元素放到右边，然后递归排序左右两部分。
例如：
```text
[5, 3, 8, 1, 6]
基准值选择 5
左边：[3, 1]
基准：[5]
右边：[8, 6]
左右分别排序后：[1, 3, 5, 6, 8]
```
快速排序的平均性能很好，并且数组版本通常可以原地完成。若每次选到的基准值都让划分严重失衡，例如划分成 0 个和 n - 1 个元素，时间复杂度就会退化为 O(n²)。
### 2. 归并排序
核心逻辑： 不断把数组分成两半，分别排好序，再把两个有序部分合并起来。
例如：
```text
[5, 3, 8, 1]
拆分
[5, 3] [8, 1]
[5] [3] [8] [1]
合并
[3, 5] [1, 8]
[1, 3, 5, 8]
```
归并排序无论输入顺序如何，时间复杂度都是 O(n log n)。它的代价是数组合并时通常需要额外的 O(n) 空间。
### 3. 插入排序
核心逻辑： 把左边看成已经排好序的部分，每次拿出一个新元素，将它插入左边的正确位置，类似整理手中的扑克牌。
例如：
```text
[5, 3, 8, 1]
[3, 5, 8, 1] 插入 3
[3, 5, 8, 1] 插入 8
[1, 3, 5, 8] 插入 1
```