当前课程知识点：数据结构 > 第8章 排序 > 8.2 插入排序 > 讲解（下）
我们来看第二种插入排序，希尔排序
希尔是这个算法的发明者的名字
希尔排序对直接插入排序做了一定的改进
它让元素呈跳跃式移动
我们之前讲的直接插入排序，元素是向后移动一个位置
而希尔排序让元素向后移动多个位置
我们将待排元素按照一定的间隔，分成若干组
然后，分别对每一组做插入排序
比如，我们第一次选取的间隔，假设是5
那么，第1、第6个元素分成同一组
第2、第7个元素分成同一组
我们对每一组进行插入排序，重复刚才的过程
我们再选一个间隔
比如是3
那么，第1、第4、第7
这三个元素会分成同一组
对它进行插入排序
然后，再对第2、第5、第8，这样的元素进行插入排序
经过若干趟插入排序之后
整个序列是基本有序的
所谓基本有序
就是，序列当中，绝大多数的值
它们是正序的
少量的值不是正序的，根据我们前面讲的，直接插入排序，最好情况下
也就是元素呈正序的情况下，时间复杂度是O(n)，最坏的情况，元素呈逆序，时间复杂度是O(n^2)
现在，待排序列基本有序
它的时间复杂度
应该是比较靠近O(n)的
从而降低时间复杂度
最后一次
我们必须做一次直接插入排序
以保证整个序列是正序
这时候
可以认为间隔是1，间隔是1，那所有的元素分成同一组
我们来看具体的过程
这里以10个关键字为例
其中有两个6，为了以示区别
第二个6
我们加了下划线
现在，我们做第一趟希尔排序
我们选取的间隔，假设是5
那么第1、第6，这两个元素会分成同一组
我们对它做插入排序，排成2和6
第2和第7，这两个元素分成同一组
一直往后
经过第一趟希尔排序之后
我们会发现，原来的两个6的先后位置，发生了变化
带下划线的这个6，跑到了前面去了
说明，希尔排序是不稳定的
因为，我们选取的间隔比较大
那么，在对每一组进行插入排序的时候
元素实际上是挪动了多个位置
它可能跳过与之相同的关键字
所以，先后位置可能发生变化
我们再看第二趟，第二趟
我们选取的间隔是3，比之前的5，要小一些
那么第1
第4
第7
第10
这四个元素会分成同一组
然后，对这四个元素做插入
排序，排成2、3、5、9
同样，再对下一组
以及第三组，进行插入排序
经过两趟插入排序之后
我们会发现，这个序列是基本有序的
在这个序列当中，只有少量的元素
比如2
6
这个6
除了这三个元素不是正序之外
剩下的1、3、4、5、7、8、9，都是正序的
刚才，我们分析过了
我们现在对这个序列，做一趟
间隔为1的希尔排序，也就是，退化为直接插入排序的希尔排序
会让整个排序的比较次数和移动次数，要少一些
这也是希尔排序对直接插入排序所做的优化
现在，我们来回顾一下整个的排序过程
如果我们要写成算法
要经过几轮的循环呢
首先
我们选取了
多个增量
这是最外层的循环
然后
一趟希尔排序过程当中
首先有三组(我们以第二条为例)
它有三组，每一组
又有多个元素
刚才我们介绍了，对多个元素做插入排序
只不过这里间隔不是1
而是3
它一样也是插入排序
我们对这四个元素构成的序列，做插入排序
它要是一个双重循环
然后，有多组
这是三重循环
然后，有多个间隔
这是第四重循环
所以，看起来
我们要用四重循环，来实现希尔排序
但我们编程都有一个原则
尽量地不要写出四重及以上的循环
这会使你的算法难以理解
并且代码难以调试
我们要么优化成三重或以下的
要么将内层的循环，把它封装一下
封装成一个独立的函数或方法
现在，我们是否要用四层的循环，来实现希尔排序呢
我们可以优化一下
比如，我们对2、5、3、9这四个元素，做插入排序的时候
我们第一次要排的元素，肯定是这一组的第2个元素
因为，我们前面讲直接插入排序的时候说过
一个元素
它永远是有序的
所以，我们先排第一组的第2个
按照我们刚才讲的，下一个要排的是谁呢
下一个要排的，我们按照刚才讲的，应该是第一组的第3个元素
正是因为这样
所以才是四重循环
现在，我们来优化一下，第一组的第2个元素
排完之后
我们要排的，是第二组的第2个元素
第三个要排的，是第三组的第2个元素
也就是，从第一组的第2个元素开始
一直往后，这些元素，我们依次去排，就可以了
这样，我们可以减少一层循环
用三层的循环，来实现希尔排序
在后面的算法实现当中
我们也会看到这样一个特点
现在，我们来总结一下刚才希尔排序的过程
分组的时候，这个间隔d，称为增量
比如，刚才的5、3、1
对各组进行插入排序的过程，称为一趟增量为d的希尔排序
增量为d，会把整个序列分成d组
然后，对这d组
分别作插入排序
这叫一趟增量为d的希尔排序
各个增量组成了一个递减序列，逐渐减小
比如5、3、1
所以，希尔排序也称为缩小增量排序
那增量序列如何来选取呢
通常，各个增量之间，没有除了1之外的公因子
比如5、3、1
最后一个增量，一定是1
因为，最终你要排成正序
你一定要做一趟直接插入排序，或者说，增量为1的希尔排序
现在，我们给出完整的算法实现
我们对以顺序表存储的待排序列L
做增量为d的希尔排序
这个d，是一个数组
它的长度是m
像5、3、1这些增量的值，我们就放到d这个数组当中
外层循环
0到m-1
我们一共要做m趟希尔排序
因为有m个增量
内层循环
i从d[k]+1开始
我们刚才说了，要排的第一个元素
应该是第一组的第2个元素
第一组的第2个元素
它的下标就是1加上d[k]
因为，这时候的增量就是d[k]
一直排到最后一个元素
i小于等于n
大家注意到，这里是i++
是自增了1，而不是自增了d[k]
也就验证了我们刚才(说的)，要排的第二个元素
不是第一组的第3个元素
而是第二组的第2个元素
这样，可以减少一层循环
跟前面的直接插入排序类似
如果ri是小于有序区的最后一个元素的
这里不是i-1了
而是i-d[k]
因为，前一个元素跟当前的ri
相差了d[k]个位置
我们暂存要插入的ri
放到r[0]里面
然后，从有序区的最后一个元素开始向前
这里是自减d[k]，前一个元素
相对于当前的rj，在前面d[k]个位置
如果j>0
这里为什么要加上一个j>0的限制呢
我们刚才的直接插入为什么没有呢
这是因为，每次j不是自减1
如果j自减1，j最终减到0的时候
会让循环退出
而这里，j很有可能从一个正数，直接减到了负数
它没有机会到达0
所以，我们这里要判断一下，j是否大于0
并且，rj是大于ri的
只有在这个前提成立的情况下
我们才有必要将rj后移
这里，后移rj
我们不是后移1个位置
而是后移d[k]个位置，元素是呈跳跃式移动的
内层循环结束之后
我们将ri放到j+d[k]的位置
而不是j+1的位置
现在，回过头看一下，内层的两重循环
其实跟我们刚才讲的直接插入排序，非常地像
只不过，是把1换成了d[k]
这个算法
它的时间复杂度，是依赖于你所选取的增量序列的
不光依赖于表长
还依赖于增量序列的选取
一般认为，希尔排序
它的时间复杂度是n^1.3
这个是介于线性的(n)和平方的(n^2)之间的
它的空间复杂度
跟直接插入排序一样
只用了一个r[0](临时的空间)
所以是O(1)
这个算法，它是不稳定的
刚才我们已经分析过了
原因是，元素呈跳跃式运动
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
