算法 |
时间复杂度 |
空间复杂度 |
|
最佳 |
平均 |
最差 |
最差 |
快速排序 |
Ω(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) |