排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
选择排序 | O(n^2) | O(n^2) | O(n) | O(1) | 不稳定 |
插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
希尔排序 | O(n^1.3) | O(n^2) | O(n) | O(1) | 不稳定 |
归并排序 | O(nlogN) | O(nlogN) | O(nlogN) | O(n) | 稳定 |
快速排序 | O(nlogN) | O(n^2) | O(nlogN) | O(logN) | 不稳定 |
堆排序 | O(nlogN) | O(nlogN) | O(nlogN) | O(1) | 不稳定 |
在有序数组中查询
1.查找特定值
2.查找小于某个值得最大值
3.查找大于某个值得最小值
连通性
最短路径(广度优先遍历)
连通分量
是否有环
是否二分图
深度优先排序
拓扑排序
强连通分量
顶点对的可达性