【正确答案】 C

【答案解析】希尔排序又称“缩小增量排序”，是一种改进的插入排序，在时间效率上有了较大的改进。对直接插入排序来说．比较的步长为1。这种情况下，如果较小的数在序列的较后面部分，则需要一步一步地向前移动，无疑是比较慢的。如果采用步长＞1的方法，则可以使较小的数向前推进是“跳跃式”进行，故可以提高排序效率。
方法：将整个序列分成若干子序列，对各个子序列进行直接插入排序，得到一趟希尔排序序列；然后缩短步长，重复以上动作，直到步长为1。
具体步骤如下：
(1)先取一正整数d(d＜n，一般可取d= )．把所有距离为d的倍数的记录编在一组，组成一个子序列，这样将整个待排序序列分成若干组；
(2)在各个子序列中进行直接插入排序；
(3)取一个新的d(比原来的要小，一般取原来的1/2)，(1)、(2)直到d=1为止(此时，整个序列变成直接插入排序)。
例如：利用希尔排序对下序列进行排序。
(72，73，71，23，94，16，15，68)，n=8
过程：1＞第一次分组，取d= =4，则对序列分组为：

对每个子序列直接插入排序得(4组)：
72 16 1 5 23 94 73 71 68
2＞第二次分组，取d===2(原来的一半)，对序列分组为：