蓄力待时，不争首功。
部分排序算法的性能比较结果如下所示：
| 类别 | 名称 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|---|
| 插入排序 | 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | 希尔排序 | O(nlogn) | O(n(logn)^2) | O(n(logn)^2) | O(1) | 不稳定 |
| 选择排序 | 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 选择排序 | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 交换排序 | 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 交换排序 | 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 不稳定 |
| 其他 | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 其他 | 基数排序 | O(nk) | O(nk) | O(nk) | O(n+k) | 稳定 |
欲了解更多信息请移步此处。
堆的各个操作的时间复杂度如下所示：
| 名称 | 时间复杂度 |
|---|---|
| 建堆 | O(n) |
| 插入 | O(logn) |
| 查找 | ? |
| 删除 | O(logn) |
| 排序 | O(nlogn) |