




已阅读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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 【正版授权】 ISO/IEC 40500:2012 EN Information technology - W3C Web Content Accessibility Guidelines (WCAG) 2.0
- 甘肃省线上线下知识培训课件
- 瓷砖产品基础知识培训班课件
- 基于分解集成框架的石油价格精准预测:模态重构与分量预测技术的深度探索
- 父亲节课件教学课件
- 诗经北门课件
- 爱耳日宣传知识课件
- 诗歌理想课件
- 爱洗碗课件教学课件
- 5月光纤通信基础习题及参考答案
- 2025年大学生就业指导课程试题库(附含答案)
- 2025年肿瘤放射治疗学科综合知识测试答案及解析
- 山西建设工程施工合同(标准版)
- 2025重庆千信外经贸集团有限公司数字贸易部副部长招聘1人笔试历年参考题库附带答案详解
- 河南天一大联考2025-2026学年(上)高一上学期9月检测语文试卷
- 2025年职业病诊断医师资格考试(职业性放射性疾病)历年参考题库含答案详解(5卷)
- 23G409先张法预应力混凝土管桩
- 动火许可证(模板)
- 《透视与解剖》教学大纲
- 库仑滴定法测定硫含量知识点解说
- 地铁试验监理细则
评论
0/150
提交评论