各种排序算法的时间与空间复杂度
2019-03-29 本文已影响0人
椰果粒
各种排序算法的时间复杂度和空间复杂度
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) |
| 希尔排序 | O(n log n) | O(nlog2n) | O(n log2 n) | O(1) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 快速排序 | O(n log n) | O(n log n) | O(n2) | O(log n) |
