常用数据结构和算法操作效率的对比总结

傷城~ 2022-09-23 12:00 32阅读 0赞

前面介绍了经典的数据结构和算法，这一节我们对这些数据结构和算法做一个总结，具体细节，请参见各个章节的详细介绍，这里我们用表格来呈现它们的效率。

# 1. 数据结构部分 #

**数据结构中常用的操作的效率表**

<table style="width:594px;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> 通用数据结构 </td> 
 <td style="vertical-align:top;"> 查找&nbsp; </td> 
 <td style="vertical-align:top;"> 插入&nbsp; </td> 
 <td style="vertical-align:top;"> &nbsp;删除 </td> 
 <td style="vertical-align:top;"> 遍历&nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51126182" rel="nofollow">数组</a> </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> — </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51126182" rel="nofollow">有序数组</a> </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51136653" rel="nofollow">链表</a> </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(1) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> — </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 有序链表 </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51138663" rel="nofollow">二叉树</a> </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 二叉树（最坏） </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51144079" rel="nofollow">红黑树</a> </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51140009" rel="nofollow">2-3-4树</a> </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51138588" rel="nofollow">哈希表</a> </td> 
 <td style="vertical-align:top;"> O(1) </td> 
 <td style="vertical-align:top;"> O(1) </td> 
 <td style="vertical-align:top;"> O(1) </td> 
 <td style="vertical-align:top;"> — </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 专用数据结构 </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51126638" rel="nofollow">栈</a> </td> 
 <td style="vertical-align:top;"> — </td> 
 <td style="vertical-align:top;"> O(1) </td> 
 <td style="vertical-align:top;"> O(1) </td> 
 <td style="vertical-align:top;"> — </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51126638" rel="nofollow">队列</a> </td> 
 <td style="vertical-align:top;"> — </td> 
 <td style="vertical-align:top;"> O(1) </td> 
 <td style="vertical-align:top;"> O(1) </td> 
 <td style="vertical-align:top;"> — </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> 优先级队列 </td> 
 <td style="vertical-align:top;"> — </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(1) </td> 
 <td style="vertical-align:top;"> — </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51105955" rel="nofollow">优先级队列（堆）</a> </td> 
 <td style="vertical-align:top;"> — </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 <td style="vertical-align:top;"> &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

# 2. 排序算法 #

**常见的排序算法比较表**

<table style="width:589px;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> 排序 </td> 
 <td style="vertical-align:top;"> 平均情况 </td> 
 <td style="vertical-align:top;"> 最好情况 </td> 
 <td style="vertical-align:top;"> 最坏情况 </td> 
 <td style="vertical-align:top;"> 稳定与否 </td> 
 <td style="vertical-align:top;"> 空间复杂度 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51154989" rel="nofollow">冒泡排序</a> </td> 
 <td style="vertical-align:top;"> O(N2) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N2) </td> 
 <td style="vertical-align:top;"> 稳定 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51154989" rel="nofollow">选择排序</a> </td> 
 <td style="vertical-align:top;"> O(N2) </td> 
 <td style="vertical-align:top;"> O(N2) </td> 
 <td style="vertical-align:top;"> O(N2) </td> 
 <td style="vertical-align:top;"> 不稳定 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51154989" rel="nofollow">插入排序</a> </td> 
 <td style="vertical-align:top;"> O(N2) </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 <td style="vertical-align:top;"> O(N2) </td> 
 <td style="vertical-align:top;"> 稳定 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51168467" rel="nofollow">希尔排序</a> </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td colspan="2" style="vertical-align:top;"> （依赖于增量序列） </td> 
 <td style="vertical-align:top;"> 不稳定 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51169679" rel="nofollow">快速排序</a> </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> O(N2) </td> 
 <td style="vertical-align:top;"> 不稳定 </td> 
 <td style="vertical-align:top;"> O(logN) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51193139" rel="nofollow">归并排序</a> </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> 稳定 </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51193330" rel="nofollow">二叉树排序</a> </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> O(N2) </td> 
 <td style="vertical-align:top;"> 稳定 </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51193399" rel="nofollow">堆排序</a> </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> O(NlogN) </td> 
 <td style="vertical-align:top;"> 不稳定 </td> 
 <td style="vertical-align:top;"> 1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> <a href="http://blog.csdn.net/eson_15/article/details/51194219" rel="nofollow">拓扑排序</a> </td> 
 <td style="vertical-align:top;"> O(N+E) </td> 
 <td style="vertical-align:top;"> — </td> 
 <td style="vertical-align:top;"> — </td> 
 <td style="vertical-align:top;"> — </td> 
 <td style="vertical-align:top;"> O(N) </td> 
 </tr> 
 </tbody> 
</table>

以上是对经典数据结构和算法部分的一个总结，如有错误之处，欢迎留言指正~

欢迎大家关注我的公众号：“武哥聊编程”，一个有温度的公众号~

关注回复：**资源**，可以领取海量优质视频资料

![程序员私房菜][70]

**\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_****\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_**

\-----乐于分享，共同进步！

\-----更多文章请看：[http://blog.csdn.net/eson\_15][http_blog.csdn.net_eson_15]

[70]: /images/20220720/cb0ced41d4bc4ca999ccadd70a6e2656.png
[http_blog.csdn.net_eson_15]: http://blog.csdn.net/eson_15