《数据结构》-第十章b希尔排序_第1页
《数据结构》-第十章b希尔排序_第2页
《数据结构》-第十章b希尔排序_第3页
《数据结构》-第十章b希尔排序_第4页
《数据结构》-第十章b希尔排序_第5页
已阅读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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论