🏷️ 知识点：希尔排序

共 5 道相关题目

模拟卷年第 9 题数据结构选择题

对一组数据（25,84,21,47,15,27,68,35,20）进行排序，前三趟的排序结果如下：

A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序

[tag_link]

正确答案：D

观察初始序列（25,84,21,47,15,27,68,35,20）和前三趟结果：第一趟后25位于序列中间，其左侧元素（20,15,21）均小于25，右侧元素（47,27,68,35,84）均大于25，这表明25在第一趟后已到达其最终排序位置，符合快速排序“选取基准并分区”的特点。第二趟和第三趟继续对左右子序列进行类似分区操作，逐步使整个序列有序。选择排序每趟应将最小元素置于前端，但第一趟结果中最小元素15不在首位，故排除；希尔排序基于增量分组排序，结果通常不每趟使基准元素就位；归并排序通过合并有序子序列实现，早期阶段元素不会快速定位到最终位置。因此，所给过程与快速排序一致。

2014 年第 10 题数据结构选择题

用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15,则该趟排序采用的增量(间隔)可能是()。

A.2

B.3

C.4

D.5

[tag_link]

正确答案：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。

2018 年第 10 题数据结构选择题

对初始数据序列 (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

[tag_link]

正确答案：D

参考希尔排序，可以观察到，第一次排序后的数组沿 gap=5 有序，第二次排序后数组沿 gap=3 有序，所以答案选择 D。

2015 年第 11 题数据结构选择题

希尔排序的组内排序采用的是（）。

排序算法希尔排序

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

[tag_link] 正确答案：A 希尔排序的思想是：先将待排元素序列分割成若干子序列（由相隔某个“增量”的元素组成），分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

2025 年第 11 题数据结构选择题

对含 9 个关键字的初始序列进行排序，若序列的变化情况如下表所示，则下列排序算法中，采用的是（）。