希尔排序(shell sort)
标签: 数据结构
学习人数: 24.9k

前言

希尔(Shell)排序又称为缩小增量排序,它是一种插入排序。它是直接插入排序算法的一种威力加强版。

希尔排序,也称递减增量排序算法,以其设计者希尔(Donald Shell)的名字命名,该算法由 1959 年公布。

 

算法思想

如何对原始数组进行预处理呢?聪明的科学家想到了一种分组排序的方法,以此对数组进行一定的“粗略调整”。

所谓分组,就是让元素两两一组,同组两个元素之间的跨度,都是数组总长度的一半,也就是跨度为4。

如图所示,元素5和元素9一组,元素8和元素2一组,元素6和元素1一组,元素3和元素7一组,一共4组。

接下来,我们让每组元素进行独立排序,排序方式用直接插入排序即可。由于每一组的元素数量很少,只有两个,所以插入排序的工作量很少。每组排序完成后的数组如下:

这样一来,仅仅经过几次简单的交换,数组整体的有序程度得到了显著提高,使得后续再进行直接插入排序的工作量大大减少。这种做法,可以理解为对原始数组的“粗略调整”。

但是这样还不算完,我们可以进一步缩小分组跨度,重复上述工作。把跨度缩小为原先的一半,也就是跨度为2,重新对元素进行分组:

如图所示,元素5,1,9,6一组,元素2,3,8,7一组,一共两组。

接下来,我们继续让每组元素进行独立排序,排序方式用直接插入排序即可。每组排序完成后的数组如下:

此时,数组的有序程度进一步提高,为后续将要进行的排序铺平了道路。

最后,我们把分组跨度进一步减小,让跨度为1,也就等同于做直接插入排序。经过之前的一系列粗略调整,直接插入排序的工作量减少了很多,排序结果如下:

让我们重新梳理一下分组排序的整个过程:

像这样逐步分组进行粗调,再进行直接插入排序的思想,就是希尔排序,根据该算法的发明者,计算机科学家Donald Shell的名字所命名。

上面示例中所使用的分组跨度(4,2,1),被称为希尔排序的增量,增量的选择可以有很多种,我们在示例中所用的逐步折半的增量方法,是Donald Shell在发明希尔排序时提出的一种朴素方法,被称为希尔增量。

可想而知,步长的选择是希尔排序的重要部分。算法最开始以一定的步长进行排序,然后会继续以更小的步长进行排序,最终算法以步长为 1 进行排序。当步长为 1 时,算法变为直接插入排序,这就保证了数据一定会被全部排序。

 

算法分析

希尔排序的算法性能

排序(3):希尔排序

1、时间复杂度
步长的选择是希尔排序的重要部分,只要最终步长为1任何步长序列都可以工作。

算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序,最终算法以步长为1进行排序。当步长为1时,算法变为插入排序,这就保证了数据一定会被排序。

步长序列的不同,会导致最坏的时间复杂度情况的不同。

本文中,以N/2为步长的最坏时间复杂度为N^2。

Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1。虽然这样取可以比O(N^2)类的算法(插入排序)更好,但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后,以前用的较大步长仍然是有序的。比如,如果一个数列以步长5进行了排序然后再以步长3进行排序,那么该数列不仅是以步长3有序,而且是以步长5有序。如果不是这样,那么算法...

登录查看完整内容


课后作业

课后习题

 

【2018年真题】对初始数据序列(8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 )进行希尔排序。若第一趟排序结果为(1,3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ),第二趟排序结果为(1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9  ),则两趟排序采用的增量(间隔)依次是    。
A.3, 1    B. 3,2    C. 5,2    D. 5,3

参考答案:D

 

【2015年真题】希尔排序的组内排序采用的是()。

A.直接插入排序    B.折半插入排序    C.快速排序    D.归并排序

参考答案:A

 

【2014年真题】用希尔排序方法对一个数据序列进行排序时,若第1趟排序结果为9,1,4,13,7,8,20,23,15,则该趟排序采用的增量(间隔)可能是()
A.2 
B.3 
C.4 
D.5

参考答案:B
答案解析:首先,第二个元素为1,是整个序列中的最小元素,所以可知该希尔排序为从小到大排序。然后考虑增量问题,若增量为2,第 1+2 个元素4明显比第1个元素9要大,A 排除;若增量为3,第 i、i+3、i+6 个元素都为有序序列(i=1,2,3),符合希尔排序的定义;若增量为4,第1个元素9比第1+4个元素7要大,C排除;若增量为5,第1个元素9比第1+5个元素8要大,D排除,选B。 


登录后开始许愿

暂无评论,来抢沙发