408 每日一题 Day5#

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

A. 快速排序
B. 冒泡排序
C. 归并排序
D. 希尔排序

正确答案：D#

解析： 第 1 趟排序中，$64 \rightarrow 10$、$84 \rightarrow 14$、$49 \rightarrow 65$，元素位置变化较大，观察不难发现，位置变化距离均为6于是将序列按间隔 $gap=6$ 分组： $(0,6)$，$(1,7)$，$(2,8)$，$(3,9)$，$(4,10)$，$(5,11)$，各组分别进行插入排序，可得到第 1 趟结果。

同理第 2 趟按 $gap=3$ 分组：
$(0,3,6,9)$，$(1,4,7,10)$，$(2,5,8,11)$，组内插入排序后得到对应序列，呈现局部有序。

同理第 3 趟 $gap=1$，得到有序序列。

符合间隔逐步缩小、分组插入排序的特征，因此为希尔排序。