| 排序算法 | 平均情况 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定与否 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(n2) | 1 | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | 1 | 不稳定 |
| 插入排序 | O(n2) | O(n) | O(n) | 1 | 稳定 |
| 希尔排序 | O(nlogn) | 依赖增量序列 | 依赖增量序列 | 1 | 不稳定 |
| 快速排列 | O(nlogn) | O(nlogn) | O(n2) | O(logn) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 二叉树排序 | O(nlogn) | O(nlogn) | O(n2) | O(n) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n2) | O(n) | O(n+k) | 稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | 1 | 不稳定 |
| 拓扑排序 | O(N+E) | - | - | O(n) | - |
算法动图演示请看 📃 附录1
拓扑排序步骤：
- 删除1或2输出
- 删除2或3以及对应边
- 删除3或者4以及对应边
- 重复以上规则步骤
