题目

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

错因

B

折半插入排序的优势是比较次数少（用二分定位插入位置），但移动次数与直插一样，且要求对象在内存里随机访问下标方便。希尔排序的"组"是按增量 d 跳跃取的元素（如 a[0], a[d], a[2d], ...），跳着比较时用直插的"逐个后移、找到位置插入"模型最直接——不需要在跳跃下标上额外做二分定位。教科书一致采用直插。

C

快速排序需要 pivot、递归划分，对小段、近乎有序的数据反而是劣势（递归开销 + 最坏 ）。希尔排序的核心思想恰恰是"通过大增量先粗调、小增量再细调，让每趟数据接近有序"——对接近有序的数据，直插效率非常高（接近 ）。组内用快速排序与希尔的设计哲学相反。

D

归并排序需要 辅助空间和明显的合并开销，对小数组反而比直插慢（常数大）。希尔排序按增量分组后，每组规模很小，归并的合并代价不划算。而且希尔本质是原地排序，组内引入归并就破坏了原地特性。

总解析

希尔排序（缩小增量排序）的结构：

1. 选定一个增量序列 。
2. 对每个增量 ，把数组按下标差 分成若干"组"（如 为一组）。
3. 每组内做一次"直接插入排序"。
4. 增量缩小到 1 时，相当于对整个数组做一次直插——但此时数组已经"基本有序"，直插非常快。

为什么组内非直插不可：

原因	说明
小数据量	每组元素少（ 个），简单算法（直插）最快
数据基本有序	经过前几轮粗调，每组数据接近有序，直插表现接近
原地、稳定的局部性	直插不需要额外空间，符合希尔"in-place + 跳跃下标访问"的设计
跳跃下标天然适配	直插的"前向比较 + 后移"模式可以无缝改成"跳 步比较、跳 步后移"

希尔的本质洞察：直插对已基本有序的序列效率很高（接近 ），但对乱序大数组很慢（）。希尔通过"先粗后细"的多轮直插，把"大范围乱序"逐步消化成"小范围微调"——既继承了直插的简单与原地，又规避了它在大乱序下的性能崩溃。

送分题提示：这一题考的是希尔排序最经典的定义。教材原文："希尔排序又称缩小增量排序，是对直接插入排序的改进。" 记牢即可。

最终答案是 A（直接插入排序）。