没有合适的资源?快使用搜索试试~ 我知道了~
首页数据结构算法详解:快速排序与插入排序比较
数据结构算法详解:快速排序与插入排序比较
需积分: 10 4 下载量 187 浏览量
更新于2024-07-19
收藏 162KB DOC 举报
本文档深入探讨了数据结构中的各种排序算法及其特性,主要包括插入排序、合并排序、冒泡排序、选择排序、希尔排序、堆排序、快速排序、计数排序、基数排序以及桶排序(未实现)。作者首先提到对这些算法时间复杂度的理解尚存困惑,尽管知道快速排序以n*log(n)的速度著称,因其分治策略和原地排序的特点受到青睐,但其在最坏情况下的时间复杂度为n*n,需要通过随机化改进。快速排序以其直观的名字和高效性成为作者心中的首选。 稳定性和原地排序是介绍的两个关键概念。稳定排序如插入排序,保持相等元素的原始顺序,对于需要保持原有关联的数据尤其重要。原地排序指的是排序过程中不需要额外空间,如快速排序和堆排序,而合并排序和计数排序则不然,它们需要额外空间辅助。 插入排序作为初学者接触的第一种排序方法,具有n*n的时间复杂度,但在部分有序的数据中表现优秀,插入操作简单,移动元素少,适合处理大量数据接近有序的情况。 文章还提到了其他排序算法,如冒泡排序、选择排序和希尔排序,它们各有特点,但作者并未详细对比它们的时间复杂度,只是强调了快速排序的优势。此外,计数排序和基数排序是非比较排序,适用于特定类型的输入,如整数计数和固定位数的数字。 总结来说,本篇文档帮助读者了解了排序算法的基本分类、特性以及适用场景,提供了对快速排序等常见算法更深入的理解,同时也揭示了在实际应用中选择排序算法时需要考虑的因素。通过阅读,读者不仅能够掌握排序算法的理论知识,还能根据数据特性和性能需求做出明智的选择。
资源详情
资源推荐
"##*4+410,.!!创建 4 个数据,测试
? )'"##4.!!调用冒泡排序
-'4.4.//
3'89:9"##*+.
3'89;9.
<%93#9.
''4.
我这里用了一个哨兵做标记,就是如果在已经是排好序的情况下我们能检测出来并退出。
随便说一下,冒泡排序是稳定的排序。
选择排序, 的时间复杂度,稳定排序,原地排序。选择排序就是冒泡的基本思想,
从小的定位,一个一个选择,直到选择结束。他和插入排序是一个相反的过程,插入是确
定一个元素的位置,而选择是确定这个位置的元素。他的好处就是每次只选择确定的元素
不会对很多数据进行交换。所以在数据交换量上应该比冒泡小。
选择排序和冒泡排序思路上有一点相似,都是先确定最小元素,再确定第二笑元素,最后
确定最大元素。他的主要流程如下:
加入一个数组 ,,我们对他进行排序
确定最小的元素放在 *4+位置,我们怎么确定呢,首先默认最小元素为 他的索引为 4
然后用它跟 比较,比他打,则认为最小元素为 他的索引为 ,然后用 跟 比,发现比
他小,最小元素还是 ,然后跟 比,最小元素变成了 ,索引为 ,然后跟 比,跟 , 比。
当比较结束之后,最小元素也尘埃落定了。就是 ,索引为 ,然后我们把他放在 *4+处。
为了使 *4+原有数据部丢失,我们使 *4+要放的位置与 *+(最小数据的位置)交换。这
样就不可以了吗?
然后我们在来找第二小元素,放在 *+,第三小元素,放在 *+。。当寻找完毕,我们
排序也就结束了。
不过,在找的时候要注意其实位置,不能在找 *+的时候,还用 *+的数据跟已经排好
的 *4+*+比,一定要跟还没有确定位置的元素比。还有一个技巧就是我们不能每次都存
元素值和索引,我们只存索引就可以了,通过索引就能找到元素了。呵呵。
他和冒泡的相似和区别,冒泡和他最大的区别是他发现比他小就交换,把小的放上面,
而选择是选择到最小的在直接放在确定的位置。选择也是稳定的排序。
基本思路就这样了,奉上源代码:
!!选择排序3"## 要排序的数据, > 数据的个数
))'3"##>
!! 从*4>7开始选择,确定第 个元素
剩余18页未读,继续阅读
bianyamei
- 粉丝: 37
- 资源: 9
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- zlib-1.2.12压缩包解析与技术要点
- 微信小程序滑动选项卡源码模版发布
- Unity虚拟人物唇同步插件Oculus Lipsync介绍
- Nginx 1.18.0版本WinSW自动安装与管理指南
- Java Swing和JDBC实现的ATM系统源码解析
- 掌握Spark Streaming与Maven集成的分布式大数据处理
- 深入学习推荐系统:教程、案例与项目实践
- Web开发者必备的取色工具软件介绍
- C语言实现李春葆数据结构实验程序
- 超市管理系统开发:asp+SQL Server 2005实战
- Redis伪集群搭建教程与实践
- 掌握网络活动细节:Wireshark v3.6.3网络嗅探工具详解
- 全面掌握美赛:建模、分析与编程实现教程
- Java图书馆系统完整项目源码及SQL文件解析
- PCtoLCD2002软件:高效图片和字符取模转换
- Java开发的体育赛事在线购票系统源码分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功