常用的排序算法和时间复杂度
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) |
首先先给出我们常用的算法的时间复杂度，后面会具体讲解每一个算法，以及在不同的场合下哪种时间复杂度很高效
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-05-31 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录