| 算法 |
时间复杂度 |
空间复杂度 |
|
最佳 |
平均 |
最差 |
最差 |
| 快速排序 |
Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(log(n)) |
| 归并排序 |
Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Timsort（归并优化） |
Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| 堆排序 |
Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(1) |
| 冒泡排序 |
Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| 插入排序 |
Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| 选择排序 |
Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
| 树排序 |
Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(n) |
| 希尔排序 |
Ω(n log(n)) |
Θ(n(log(n))^2) |
O(n(log(n))^2) |
O(1) |
| 桶排序 |
Ω(n+k) |
Θ(n+k) |
O(n^2) |
O(n) |
| 基数排序 |
Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
| 计数排序 |
Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
| Cubesort |
Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
大仙帅啊说道：
