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

前言

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

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

 

算法思想

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

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

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

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

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

但是...

登录查看完整内容


课后作业

课后习题

 

【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。 


登录后发布评论

暂无评论,来抢沙发