| 排序方法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 插入排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(n \log n)$ | $O(n^2)$ | $O(n \log n)$ | $O(1)$ | 不稳定 |
| 归并排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | 稳定 |
| 快速排序 | $O(n \log n)$ | $O(n^2)$ | $O(n \log n)$ | $O(\log 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(n + k)$ | 稳定 |
| 桶排序 | $O(n + k)$ | $O(n^2)$ | $O(n + k)$ | $O(n + k)$ | 稳定 |
| 基数排序 | $O(n \times k)$ | $O(n \times k)$ | $O(n \times k)$ | $O(n + k)$ | 稳定 |
注意：
-
$n$：数据规模
-
$k$：桶的数量（计数排序中为最大值范围，基数排序中为位数）
-
快速排序空间复杂度为递归造成的栈空间的使用，平均为 $O(\log n)$，最坏为 $O(n)$
-
希尔排序的时间复杂度依赖于增量序列，此处给出的是常见增量序列的复杂度
| 排序方法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | |||||
| 选择排序 | |||||
| 插入排序 | |||||
| 希尔排序 | |||||
| 归并排序 | |||||
| 快速排序 | |||||
| 堆排序 | |||||
| 计数排序 | |||||
| 桶排序 | |||||
| 基数排序 |