首页 > 代码库 > 常用的排序算法和时间复杂度
常用的排序算法和时间复杂度
1. 数据结构部分
数据结构中常用的操作的效率表
通用数据结构 | 查找 | 插入 | 删除 | 遍历 |
数组 | O(N) | O(1) | O(N) | — |
有序数组 | O(logN) | O(N) | O(N) | O(N) |
链表 | O(N) | O(1) | O(N) | — |
有序链表 | O(N) | O(N) | O(N) | O(N) |
二叉树 | O(logN) | O(logN) | O(logN) | O(N) |
二叉树（最坏） | O(N) | O(N) | O(N) | O(N) |
红黑树 | O(logN) | O(logN) | O(logN) | O(N) |
2-3-4树 | O(logN) | O(logN) | O(logN) | O(N) |
哈希表 | O(1) | O(1) | O(1) | — |
专用数据结构 |
|
|
|
|
栈 | — | O(1) | O(1) | — |
队列 | — | O(1) | O(1) | — |
优先级队列 | — | O(N) | O(1) | — |
优先级队列（堆） | — | O(logN) | O(logN) |
|
2. 排序算法
常见的排序算法比较表
排序 | 平均情况 | 最好情况 | 最坏情况 | 稳定与否 | 空间复杂度 |
冒泡排序 | O(N2) | O(N) | O(N2) | 稳定 | 1 |
选择排序 | O(N2) | O(N2) | O(N2) | 不稳定 | 1 |
插入排序 | O(N2) | O(N) | O(N2) | 稳定 | 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(NlogN) | O(NlogN) | O(NlogN) | 不稳定 | 1 |
拓扑排序 | O(N+E) | — | — | — | O(N) |
常用的排序算法和时间复杂度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。