已阅读5页，还剩5页未读， 继续免费阅读
版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
1,第十章 内部排序,10.1 概述,10.2 插入排序,10.2.1 直接插入排序,10.2.2 其他插入排序,10.2.3 希尔排序,10.3 快速排序,10.4 选择排序,10.4.1 简单选择排序,10.4.2 树形选择排序,10.4.3 堆排序,10.5 归并排序,10.6 基数排序,10.6.1 多关键字的排序,10.6.2 链式基数排序,10.7 各种内部排序方法的比较讨论,2,10.2.3 希尔排序,希尔排序（Shells Sort）又称“缩小增量排序”(Diminishing Increment Sort)，它是一种属插入排序类的方法。,（1）主要思想 主要思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排 序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。,3,10.2.3 希尔排序,（2）算法实现,void ShellInsert (SqList /插入 / ShellInsert,4,算法10.5如下：void ShellSort (SqList /一趟增量为dltak的插入排序 / ShellSort,5,初始关键字序列如图10.5的第1行所示。首先将该序列分成5个子序列：R1, R6, R2, R7, , R5, R10，分别对每个子序列进行直接插入排序。然后将第1趟希尔排序的结果分成3个子序列：R1, R4, R7, R10, R2, R5, R8和R3, R6, R9，并对它们进行直接插入排序。最后对整个序列进行一趟直接插入排序。至此，希尔排序结束，整个序列的记录已按关键字非递减有序排列。,6,图10.5 希尔排序示例,7,例如，在上例中，第一趟排序时的增量为5，第二趟排序时的增量为3，最后一趟排序时为1。,（4）特点,希尔排序的特点是：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。,8,希尔排序中gap的取法,Shell最初的方案是 gap= n/2, gap=gap/2，直到gap=1.Knuth的方案是gap = gap/3+1其它方案有：都取奇数为好；或gap互质为好等等。,9,希尔排序的时间复杂度,对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学分析，目前还做不到。Knuth的统计结论是，平均比较次数和对象平均移动次数在n1.25
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 药店药品追回管理制度试题(3篇)
- 试验模型管理制度和流程(3篇)
- 金融市场管理制度(3篇)
- 食堂管理制度样式图片卡通(3篇)
- 2026年及未来5年市场数据中国在线餐饮外卖行业发展监测及发展趋势预测报告
- 养老院入住资格审查制度
- 企业员工培训与职业发展策略制度
- 企业内部审计制度
- 交通设施安全检测制度
- 2026湖南郴州市市直学校面向高校毕业生公开招聘教师25人备考题库附答案
- 集团债权诉讼管理办法
- 上海物业消防改造方案
- 钢结构施工进度计划及措施
- 供应商信息安全管理制度
- 智慧健康养老服务与管理专业教学标准（高等职业教育专科）2025修订
- 2025年农业机械化智能化技术在农业防灾减灾中的应用报告
- 发展与安全统筹策略研究
- 移动式压力容器安全技术监察规程（TSG R0005-2011）
- 2025年广东省惠州市惠城区中考一模英语试题（含答案无听力原文及音频）
- 征兵体检超声诊断
- 云南省大理白族自治州2025届高三上学期二模考试 英语 含解析
评论
0/150
提交评论