9.2 希尔排序在线视频

同学们，大家好

我是云南大学信息学院教师孔兵

这节课，我们讨论希尔排序

在分析直接插入排序时间效率时

我们注意到，如果待排序的序列已经有序

那么直接插入排序算法只需要进行n-1次比较

不需要移动，应该说效率非常高

我们降低一点要求，待排序记录按关键字并不是有序

而是基本有序

如果自小到大排序的话

基本有序简单的说就是，关键字小的记录基本在序列的前面

关键字大的记录基本在序列的后面

序列基本有序的话

直接插入排序的效率实际上是非常高的

观察图中两个序列

图1的序列中

关键字小的基本在序列前面

关键字大的基本在序列后面

图2的序列没有这样的性质

所以，相对而言可以说图1当中的序列是基本有序

希尔排序正是基于这样一个思想来设计的

希尔排序的思路是

先将整个待排序记录序列分割成若干子序列

分别进行直接插入排序

待整个序列中的记录“基本有序”时

再对全体记录进行一次直接插入排序

希尔排序需要进行多趟，每趟排序中

基于一个跨度dk，把待排序记录序列分割成若干子序列

随后在每个子序列中分别进行直接插入排序

通过一个例子来说明希尔排序的过程

图1中的待排序序列包含10个记录

首先以dk=5，也就是基于跨度为5进行一趟希尔排序

跨度为5的含义就是

这趟排序

把序列中间隔为5的记录分在同一个子序列中

那么序列被分为5个子序列

图1当中我们用不同的颜色表示不同的子序列

比如说第1个子序列

它包含1号单元的49和6号单元的13

两者的跨度为5

子序列的的下一个记录应该是11号单元的记录

不过例子中只有10个记录

子序列没有下一个记录了

同理，2和7,3和8,4和9,5和10组成了另外4个子序列

因为1到5号单元中是各个子序列的第1个记录

所以从i=dk+1，第6个单元的记录开始插入

用for循环从6到L.length插入记录

注意，插入第i个记录的方法和直接插入排序是一样的

只是插入仅在自己的子序列中完成

和其它子序列的记录无关

以第6号单元的关键字13为例

和同一系列的前一个记录，1号单元的49比较

比49小，把13暂存在0号单元

从后向前，在子序列中确定插入位置

从j=i-dk开始，这里j=1

暂存在0号单元13和1号单元49比较

小于j的关键字

把数组第j号单元的记录后移到同一子序列的下一个位置j+dk

随后，j=j-dk继续考察同一子序列的前一个记录

这里j=-4，超出了序列的存储位置

那么j+dk的位置1号单元就是13存储的位置

第6个记录插入后

我们注意到第1个子序列1和6的关键字已经有序

同样方式插入后续记录，结果如图2所示

我们注意到

以不同颜色表示的5个子序列内部都是有序的

并且，关键字小的记录向前移动

关键字大的记录向后移动

随后以跨度dk=3进行一趟希尔排序

跨度为3时

序列被分为3个子序列

如图3所示，不同颜色表示3个不同的子序列

从i=4开始，在子序列中进行直接插入排序

完成这趟排序后，结果如图4所示

每个子序列的内部是有序的

图4和图3比较而言

关键字小的记录基本在序列前面

关键字大的记录基本在序列的后面

也就是说它基本有序了

在此基础上，以跨度dk=1进行一趟希尔排序

如图5所示。所谓跨度为1

就是把所有记录划作为一个序列

实际上就是直接插入排序

最终通过这一趟直接插入排序，使整个序列有序

请同学们观察一下

希尔排序是稳定的吗？为什么？

看一下希尔排序的实现

实现一趟希尔排序的函数是ShellInsert，涉及到的参数有两个

一个是存储待排序记录的结构体L

一个是这一趟希尔排序的跨度dk

一趟希尔排序的函数和直接插入排序的函数是雷同的

差异有两点：一是插入的记录从dk+1开始

二是比较和寻找插入位置是在一个子序列的内部

如果参数dk=1的话，和直接插入排序完全相同

希尔排序的函数是ShellSort，有三个参数

一个是存储待排序序列的结构体L

一个是整型数组dlta，dlta中存储每趟希尔排序的跨度

最后一个参数整形t，是给出希尔排序要进行的趟数

函数体中只有一个for循环

每次循环调用ShellInsert进行一趟希尔排序，共循环t次

就前面的例子来说

dlta和t的情况如图所示

dlta中三个单元分别存储5，3，1三个跨度

t=3，表示要按照这3个跨度，进行3趟希尔排序

希尔排序的时间复杂度为：O(n3/2)，就是n的1.5次方

有人在实验基础上得出：

当N在某个特定范围内

希尔排序所需的比较和移动次数约为n1.3

当n→∞时，可减少到n(log2n)2

应该说希尔排序的时间效率是不错的

特别是当待排序序列基本有序时，效率更好

好同学们，这节课我们就介绍到这儿

下次课再见