设待排序的关键字序列为{12，22，116，30，28，10，160，20，6，18}，试写出使用希尔排序（增量为5，2，1）排序方法每趟排序后的结果，并说明做了多少次关键字比较。

使用希尔排序，增量为5，2，1，对于给定的序列{12，22，116，30，28，10，160，20，6，18}，排序过程如下：

1. 当增量为5时，将序列分为5组，分别进行插入排序：

第一轮排序结果：{10，6}，{22，20}，{116，18}，{30}，{28，12}，{160}

比较次数：6

第二轮排序结果：{10，6，116，30，28}，{22，20，160}，{18，12}

比较次数：7

2. 当增量为2时，将序列分为2组，分别进行插入排序：

第一轮排序结果：{6，18，10，20，28，12}，{116，22，160，30}

比较次数：11

3. 当增量为1时，进行插入排序：

最终排序结果：{6，10，12，18，20，22，28，30，116，160}

比较次数：15

因此，总共进行了6+7+11+15=39次关键字的比较。

相关问题

数据结构c语言实现 设待排序的关键字序列为{12，22，116，30，28，10，160，20，6，18}，试写出使用希尔排序（增量为5，2，1）排序方法每趟排序后的结果，并说明做了多少次关键字比较。

希尔排序是一种插入排序的改进版，通过将数组分成若干个子序列并对每个子序列进行插入排序，从而逐渐减小子序列的长度，直到子序列长度为1时，整个数组就已经被排好序了。

根据题目给出的增量，我们可以先将待排序序列按照增量分成多个子序列，然后对每个子序列进行插入排序。具体步骤如下：

第一趟排序，增量为5：

子序列1：12 10

子序列2：22 160

子序列3：116 20

子序列4：30 6

子序列5：28 18

对每个子序列进行插入排序后，得到以下结果：

子序列1：10 12

子序列2：22 160

子序列3：20 116

子序列4：6 30

子序列5：18 28

第一趟排序后的序列为：{10，22，20，6，18，12，160，116，30，28}

共比较了10次关键字。

第二趟排序，增量为2：

子序列1：10 20 18 160 28

子序列2：22 6 12 116 30

对每个子序列进行插入排序后，得到以下结果：

子序列1：10 18 28 160 20

子序列2：6 12 22 30 116

第二趟排序后的序列为：{10，6，18，12，22，28，160，30，116，20}

共比较了13次关键字。

第三趟排序，增量为1：

对整个序列进行插入排序，得到最终排序结果：

{6，10，12，18，20，22，28，30，116，160}

共比较了14次关键字。

因此，使用希尔排序方法对{12，22，116，30，28，10，160，20，6，18}进行排序后，得到的每趟排序结果分别是：

第一趟排序：{10，22，20，6，18，12，160，116，30，28}

第二趟排序：{10，6，18，12，22，28，160，30，116，20}

第三趟排序：{6，10，12，18，20，22，28，30，116，160}

共比较了37次关键字。