各种排序算法时间复杂度1
需积分: 0 75 浏览量
2022-08-03
15:38:40
上传
评论
收藏 364KB PDF 举报
2018/7/3 各种排序算法时间复杂度 - AmyAlisa - 博客园
https://www.cnblogs.com/xiaochun126/p/5086037.html 1/3
AmyAlisa
随笔 - 82 文章 - 0 评论 - 1 trackbacks - 0
各种排序算法时间复杂度
各种排序算法比较
各种常用排序算法
类别 排序方法
时间复杂度 空间复杂度 稳定性 复杂性 特点
最好 平均 最坏 辅助存储 简单
插入
排序
直接插入 O(N)
O(N
2
) O(N
2
)
O(1) 稳定 简单
希尔排序 O(N)
O(N
1.3
) O(N
2
)
O(1) 不稳定 复杂
选择
排序
直接选择 O(N)
O(N
2
) O(N
2
)
O(1) 不稳定
堆排序
O(N*log
2
N) O(N*log
2
N) O(N*log
2
N)
O(1) 不稳定 复杂
交换
排序
冒泡排序 O(N)
O(N
2
) O(N
2
)
O(1) 稳定 简单
1、冒泡排序是一种用时间换空间的排序方
2、最坏情况是把顺序的排列变成逆序，或
时间复杂度O(N^2)只是表示其操作次数的
3、最好的情况是数据本来就有序，复杂度
快速排序
O(N*log
2
N) O(N*log
2
N)
O(N
2
)
O(log
2
n)~O(n)
不稳定 复杂
1、n大时好，快速排序比较占用内存，内
高不稳定的排序算法。
2、划分之后一边是一个，一边是n-1个，
这种极端情况的时间复杂度就是O(N^2)
3、最好的情况是每次都能均匀的划分序列
归并排序
O(N*log
2
N) O(N*log
2
N) O(N*log
2
N)
O(n) 稳定 复杂
1、n大时好，归并比较占用内存，内存随
稳定的排序算法。
基数排序 O(d(r+n)) O(d(r+n)) O(d(r+n)) O(rd+n) 稳定 复杂
注：r代表关键字基数，d代表长度，n代表关键字个数
注：
1、归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助
空间，
2、快速排序空间复杂度只是在通常情况下才为O(log2n)，如果是最坏情况的话，很显然就要O(n)的空间了。当然，可以通过随机化选
择pivot来将空间复杂度降低到O(log2n)。
相关概念：
1、时间复杂度
时间复杂度可以认为是对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)
时间复杂度O(1)：算法中语句执行次数为一个常数，则时间复杂度为O(1),
2、空间复杂度
空间复杂度是指算法在计算机内执行时所需存储空间的度量，它也是问题规模n的函数
空间复杂度O(1)：当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)
空间复杂度O(log2N)：当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)
ax=N，则x=logaN，
空间复杂度O(n)：当一个算法的空间复杂度与n成线性比例关系时，可表示为0(n).
博客园 首页 新随笔 联系 订阅 管理
< 2018年7月 >
日 一 二 三 四 五 六
24 25 26 27 28 29 30
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 1 2 3 4
昵称：AmyAlisa
园龄：5年9个月
粉丝：0
关注：4
+加关注
搜索
找找看
谷歌搜索
常用链接
我的随笔
我的评论
我的参与
最新评论
我的标签
最新随笔
1. oracle expdp导入时 提示“OR
A-39002: 操作无效 ORA-3907
0: 无法打开日志文件 ”
2. PL/SQL 美化器不能解析文本
3. PL/SQL TOAD 不安装Oracle
客户端连接数据库的方法
4. oracle 某一字段取反
5. jqgrid 加按钮列
6. 扩展方法 DataTable的ToList
<T>
7. jquery ajax调用WCF，采用S
ystem.ServiceModel.WebHttpBi
nding
8. jquery ajax调用WCF，采用S
ystem.ServiceModel.WSHttpBi
nding协议
9. 学习WCF笔记之二
10. WCF学习之三， 寄宿方式
代码，配置文件
我的标签
wcf(6)
sql(4)
js(3)
IIS(2)
IIS Express(1)
jquery ajax WCF
WebHttpBinding(1)
jquery ajax WCF
WSHttpBinding(1)
sql CLR(1)
sql server2005 synonyms(1)
sql 多线程(1)
更多
随笔分类(67)
ASP(3)
吹狗螺的简柏承
- 粉丝: 11
- 资源: 313
最新资源
- 论文(最终)_20240430235101.pdf
- 基于python编写的Keras深度学习框架开发，利用卷积神经网络CNN,快速识别图片并进行分类
- 最全空间计量实证方法（空间杜宾模型和检验以及结果解释文档）.txt
- 5uonly.apk
- 蓝桥杯Python组的历年真题
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 前端开发技术实验报告：内含4四实验&实验报告
- Highlight Plus v20.0.1
- 林周瑜-论文.docx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0