Video在线视频

大家好

接下来这节课中

我们将学习到一种

性能比较好的排序算法

希尔排序 Shell Sort

希尔排序是对插入排序的一种改进

前面我们已经学习过了

这个插入排序

它在最好的情况下

也就是序列有序的情况下

算法复杂度是O(n)的

而在平均情况

以及最差的情况下

它是O(n^2)的平方

这也就告诉我们

和所有的排序算法一样

在插入排序的过程中

需要排序的序列它越短

那么排序的速度也就越快

另外插入排序

它有一个特色

排序的序列越是接近有序的状态

那么这个排序它就会越快

越接近O(n)

所以我们说插入排序

它的性能和它的长度

以及序列的有序程度都相关

基于前面对插入排序的观察

那么研究者们

就提出了插入排序的一种改进

希尔排序算法

希尔排序的主要步骤是

首先它会把整个序列

划分成为一些比较短的子序列

然后对每一个子序列

分别进行插入排序

因为长度相对来说比较短

所以可以在比较小的时间内来完成

当完成各个子序列的排序之后

然后在对整一个序列

进行插入排序

那么这个时候进行插入排序

是否会比以前更加高效呢

关键就在于当我们对每个子序列

完成排序的时候

如果能够使得整个序列

也更加有序

那么根据插入排序的性质

我们对这个整个序列

来进行插入排序的时候

就可以比较高效的进行

所以希尔排序它的关键问题是

我们如何去划分这些子序列

才能够使得当子序列有序的时候

整个序列也比较有序

下面我们来看一些划分的方案

第一种划分的方案

是简单地把序列按照先后顺序

均匀地分成几段

在这个例子中

我们用不同的颜色来去区分不同的子序列

当我们对这两个字序列

分别进行排序的之后

我们发现整个序列

还是处于一个比较无序的状态

前半部分的元素

和后半部分的元素之间

没有必然的大小关系

这显然不是一种好的方案

现在我们再来看第二个方案

我们将序列交错地划分成两个系列

每一个子序列中的元素

它的增量为2的等差数列

当我们对这两个子序列

分别进行排序之后

这两个有序的序列

就像麻绳一样

交错地拧在了一起

那么整个序列

也处于一个比较有序的状态

序列的前面部分的元素

要小于后面部分的元素

希尔排序所采用的

就是后面这种交错划分的方案

我们再来仔细分析一下

这种交错划分的方案

当我们要划分两个子序列的时候

我们让这些序列中

位置的增量等于2的元素

放到同一个序列里边去

当然我们可以划分出更多的子序列

比如如果我们要划分4个子序列

那么我们就让位置的增量

等于4的元素

放到同一个子序列里面去

所以我们要划分多少个子序列

那么同一个子序列中

相邻元素它的位置增量就等于多少

希尔排序就是一个

不断去划分子序列

然后对每个子序列

来进行排序的过程

它通常会将原来这个序列

划分成为比较多的子序列

比如在这个例子中

序列有16个元素

那么第一步我们将这个序列

划分成为8个子序列

每个子序列里面

包含两个元素

子序列内部相邻的元素

它们位置的增量是等于8的

然后我们分别对这8个子序列

进行插入排序

接着我们继续

再将整个序列划分成为四个子序列

子序列中相邻元素的位置

它的增量是等于4的

然后我们同样对每一个子序列

进行插入排序

接着我们继续把整个序列

划分成为两个子序列

子序列的数目越来越小

子序列的长度也就越来越长

然后我们在对每个子序列

也是同样地进行插入排序

最后一次我们将会对整个序列

进行插入排序

最终完成这个排序的过程

我们可以看出来

我们每完成一次子序列的划分

以及子序列的排序

都会使得整个序列

接近更加有序的状态

子序列的数目越少

那么子序列的元素

也就分布也就越密集

在子序列排好序之后

就会更加接近有序

我们可以看到

在最后的一次排序的过程中

整个序列

已经接近非常有序的状态了

所以再进行最后一次插入排序

就可以很快地完成

这个排序的过程

下面我们来看一下

希尔排序它的具体实现

这里的Shellsort函数

它有两个参数

第一个数据元素的数组A

第二个是数据元素的个数n

因为希尔排序

它需要多趟子序列的划分

然后再排序

所以我们这里采用一个

for循环来实现

其中循环变量incr用来

去记录子序列的数目

这里首先我们会把序列

划分成为二分之n个子序列

然后每循环一次

划分子循环的个数

将会除以2

在最后一次循环的时候

子循环的数目将会等于1

也就是整个序列放在一起

一起排序

那么变量incr的另外一个含义

是子序列中相邻元素位置的增量

位置的增量为incr的元素

将会被划分到同一个子序列里面去

接下来我们需要对incr两个

子序列分别进行插入排序

所以我们使用一个for循环

循环变量k

表示子序列的序号

k从0取值到incr-1

一共是incr个子序列

在循环体中

我们对第k个子序列

进行插入排序

我们定义第k个子序列

是从k号位置开始 一个子序列

例如在图中这个例子中

当incr等于4的时候

有4个子序列

其中第0个子序列

是从0号位置开始的

而且位置增量等于4的这个子序列

那么第一个子序列

是从1号位置开始的一个子序列

后面的子序列

依此类推

第k的子序列进行插入排序的过程

我们单独实现为

另外一个函数inssort2

下面我们来看一下inssort2

这个函数的实现

这个函数是对数组A中

第k的子序列来进行排序的

其中n是表示数组元素的总数

incr是表示

这个子序列的相邻元素的位置的增量

第k的子序列所在的元素

所在的位置也是k

所以我们定义变量 from

来去记录第1个元素它的位置

接下来我们对这个子序列

进行一个插入排序

这里的实现代码

和我们前面所学习到的

插入排序是类似的

都是从第二个元素开始

把所有的元素

插入到序列前面中的

一个合适的位置中去

插入的过程是一个

和前面的位置的元素

进行比较和交换的过程

唯一不同的是

我们这里的子序列中的元素

它的位置不是相连的

相邻的元素它的位置增量等于incr

那么代码的细节

这里就不再细讲了

同学们可以对照

前面的插入排序算法来进行学习

在图中这个例子中

我们是要对第0个子序列

来进行插入排序

这个序列中的元素

分别是36 28 59和65

它们位置的增量等于4

插入排序的时候

我们先把28往前面插入

然后我们插入59

最后是插入65

这个过程和我们所学习到的

插入排序是一致的

希尔排序它的算法复杂度

和划分子序列的时候

我们划分的增量很大的关系

哪种增量的选择方法

它是最优的呢

目前还没有定论

但是我们已经可以证明

当我们采用某些增量的时候

希尔排序它的具体性能

是可以得到的

比如如果我们第k次迭代的过程中

选择的增量是2^(t-k+1)-1

那么我们知道希尔排序

它的算法复杂度是O(n^3/2)

这里的t表示

希尔排序的迭代总次数

例如我们依次选择

15 7 3 1作为增量

就会得到这样的排序性能

因此我们可以看到

在这种情况下希尔排序

还是优胜于前面所介绍的

简单插入排序算法的

这也是划分带来的好处

最后我们来分析一下

希尔排序它的稳定性

希尔它是一种不稳定排序

我们通过一个具体的例子来进行说明

在这个序列里面

有两个关键字的值

都是等于49

我们用不同的颜色来进行区分

排序之前红色的49

是排在黑色49的后面

经过第一趟希尔排序之后

我们选择5作为增量

划分了5个子序列

分别进行插入排序

排序的结果是红色的49

被交换到黑色49的前面去了

我们再来看一下

最终的排序结果

红色的49

是处于黑色49的前面

这就和初始化的时候是不一样的

所以希尔排序

它是一种不稳定的排序

好的

这节课我们就讲到这里

下节课我们再见