常见排序算法效率比较
常见排序算法效率比较
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) |
O(n) |
O(n^2) |
O(1) |
稳定 |
| 选择排序 | O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
不稳定 |
| 插入排序 | O(n^2) |
O(n) |
O(n^2) |
O(1) |
稳定 |
| 希尔排序 | O(n log n)~O(n^2) |
O(n^1.3) |
O(n^2) |
O(1) |
不稳定 |
| 堆排序 | O(n log n) |
O(n log n) |
O(n log n) |
O(1) |
不稳定 |
| 归并排序 | O(n log n) |
O(n log n) |
O(n log n) |
O(1) |
稳定 |
| 快速排序 | O(n log n) |
O(n log n) |
O(n^2) |
O(log n)~O(n) |
不稳定 |
常见排序算法效率比较
https://www.shaohang.xin/2018/11/28/technical/SortingAlgorithmsComparison/