题9

题9

题目

Q:对序列 采用希尔排序，经一趟后序列变为 ，则该次采用的增量是 ( ).
A. 1
B. 4
C. 3
D. 2

分析

A:希尔排序是按照下标进行的逻辑分组
1. 第一次排序后的形态：
希尔排序第一次分组排序后，得到的序列并不是完全有序的，而是一种“局部有序”的状态。也就是说，每个子序列内部是有序的，但整体上不一定有序。
举例说明：
还是用之前的例子：{9, 1, 4, 13, 7, 8, 20, 23, 15}，增量为 4。
第一次排序后，各个子序列内部有序：

• {7, 9, 20}
• {1, 8, 15}
• {4, 23}
• {13}
  但整体上，序列变成了 {7, 1, 4, 13, 9, 8, 20, 23, 15}， 并不是完全有序的。
  2. 逐步解决问题的过程：
  希尔排序的核心思想就是利用这种局部有序性，逐步减小增量，不断地对序列进行调整，最终达到全局有序。
• 缩小增量： 第一次排序后，我们会减小增量（例如从 4 变为 2）。
• 重新分组： 使用新的增量对序列重新分组，这时候，一些原本不属于同一个子序列的元素会被划分到一起。
• 再次排序： 对新的子序列进行直接插入排序，由于之前的排序已经使得序列局部有序，所以这次排序的效率会更高。
  重复以上步骤，直到增量为 1，此时整个序列就是一个子序列，最后一次直接插入排序就完成了最终的排序。
  形象比喻：
  可以把希尔排序想象成拼图的过程：
• 最初，我们把拼图打乱，就像无序的序列。
• 希尔排序先将拼图分成几大块（大增量），每块内部先拼好（子序列排序），这就像先拼出几个局部图形。
• 然后逐渐减小拼图块的大小（减小增量），把之前拼好的局部图形再组合起来，直到最后拼成完整的图（全局有序）。

解

B
希尔排序将序列分成若干组, 记录只在组内进行交换。由观察可知, 经过一趟后 9 和-1 交换, 7 和 4 交换, 可知增量为 4 。