设待排序的关键字序列为{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次关键字。

设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。

### 回答1：
所给定的待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，请分别写出使用以下排序方法，每趟排序结束后关键字序列的状态：

1. 冒泡排序法
第一趟排序后序列：2，12，16，28，10，16*，20，6，18，30
第二趟排序后序列：2，12，16，10，16*，20，6，18，28，30
第三趟排序后序列：2，12，10，16*，20，6，16，18，28，30
第四趟排序后序列：2，10，12，16*，6，16，18，20，28，30
第五趟排序后序列：2，10，12，6，16*，16，18，20，28，30
第六趟排序后序列：2，10，6，12，16，16*，18，20，28，30
第七趟排序后序列：2，6，10，12，16，18，16*，20，28，30
第八趟排序后序列：2，6，10，12，16，16*，18，20，28，30
第九趟排序后序列：2，6，10，12，16，16*，18，20，28，30

2. 插入排序法
第一趟排序后序列：2，12，16，30，28，10，16*，20，6，18
第二趟排序后序列：2，12，16，30，28，10，16*，20，6，18
第三趟排序后序列：2，12，16，28，30，10，16*，20，6，18
第四趟排序后序列：2，10，12，16，28，30，16*，20，6，18
第五趟排序后序列：2，10，12，16，16*，28，30，20，6，18
第六趟排序后序列：2，6，10，12，16，16*，20，28，30，18
第七趟排序后序列：2，6，10，12，16，16*，18，20，28，30

3. 选择排序法
第一趟排序后序列：2，12，16，30，28，10，16*，20，6，18
第二趟排序后序列：2，6，16，30，28，10，16*，20，12，18
第三趟排序后序列：2，6，10，30，28，16*，16，20，12，18
第四趟排序后序列：2，6，10，12，28，16*，16，20，30，18
第五趟排序后序列：2，6，10，12，16*，28，16，20，30，18
第六趟排序后序列：2，6，10，12，16*，16，28，20，30，18
第七趟排序后序列：2，6，10，12，16*，16，18，20，30，28

4. 希尔排序法
第一趟排序后序列：10，2，16*，6，12，16，18，30，28，20
第二趟排序后序列：2，10，6，12，16，16*，18，20，28，30
第三趟排序后序列：2，6，10，12，16，16*，18，20，28，30

5. 快速排序法
第一趟排序后序列：10，2，6，12，16，16*，18，30，28，20
第二趟排序后序列：2，6，10，12，16，16*，18，20，28，30

6. 归并排序法
第一趟排序后序列：2，10，16*，6，12，16，18，30，28，20
第二趟排序后序列：2，6，10，12，16，16*，18，20，28，30

### 回答2：
本题要求使用不同的排序方法对给定的关键字序列进行排序，并在每趟排序结束后记录关键字序列的状态。

基本排序方法有冒泡排序、插入排序和选择排序。这些排序方法的时间复杂度都为O(n²)，适用于小规模数据的排序。高级排序方法有快速排序、归并排序、堆排序等，它们的时间复杂度为O(nlogn)，适用于大规模数据的排序。

一、冒泡排序：比较相邻的元素，如果前一个大于后一个，则交换它们。

第一趟排序：{2, 12, 16, 28, 10, 16*, 20, 6, 18, 30}
第二趟排序：{2, 12, 16, 10, 16*, 20, 6, 18, 28, 30}
第三趟排序：{2, 12, 10, 16*, 16, 6, 18, 20, 28, 30}
第四趟排序：{2, 10, 12, 16*, 6, 16, 18, 20, 28, 30}
第五趟排序：{2, 10, 12, 6, 16*, 16, 18, 20, 28, 30}
第六趟排序：{2, 10, 6, 12, 16*, 16, 18, 20, 28, 30}
第七趟排序：{2, 6, 10, 12, 16*, 16, 18, 20, 28, 30}
第八趟排序：{2, 6, 10, 12, 16*, 16, 18, 20, 28, 30}
第九趟排序：{2, 6, 10, 12, 16*, 16, 18, 20, 28, 30}

二、插入排序：将未排序的元素插入已排序的元素中，直到所有元素都被插入为止。

第一趟排序：{2, 12, 16, 30, 28, 10, 16*, 20, 6, 18}
第二趟排序：{2, 12, 16, 30, 28, 10, 16*, 20, 6, 18}
第三趟排序：{2, 12, 16, 28, 30, 10, 16*, 20, 6, 18}
第四趟排序：{2, 10, 12, 16, 28, 30, 16*, 20, 6, 18}
第五趟排序：{2, 10, 12, 16, 16*, 28, 30, 20, 6, 18}
第六趟排序：{2, 10, 12, 16, 16*, 20, 28, 30, 6, 18}
第七趟排序：{2, 6, 10, 12, 16, 16*, 20, 28, 30, 18}
第八趟排序：{2, 6, 10, 12, 16, 16*, 18, 20, 28, 30}
第九趟排序：{2, 6, 10, 12, 16, 16*, 18, 20, 28, 30}

三、选择排序：每一趟从未排序的序列中选出一个最小的元素放到已排序的序列的末尾。

第一趟排序：{2, 12, 16, 30, 28, 10, 16*, 20, 6, 18}
第二趟排序：{2, 6, 16, 30, 28, 10, 16*, 20, 12, 18}
第三趟排序：{2, 6, 10, 30, 28, 16*, 16, 20, 12, 18}
第四趟排序：{2, 6, 10, 12, 28, 16*, 16, 20, 30, 18}
第五趟排序：{2, 6, 10, 12, 16*, 28, 16, 20, 30, 18}
第六趟排序：{2, 6, 10, 12, 16*, 16, 28, 20, 30, 18}
第七趟排序：{2, 6, 10, 12, 16*, 16, 18, 20, 30, 28}
第八趟排序：{2, 6, 10, 12, 16*, 16, 18, 20, 30, 28}
第九趟排序：{2, 6, 10, 12, 16*, 16, 18, 20, 28, 30}

以上就是根据题目要求，对给定序列进行排序的过程。从中可以看出，冒泡排序、插入排序、选择排序虽然实现简单，但是时间复杂度较高，对于大规模数据的排序并不适用，而快速排序、归并排序、堆排序等高级排序方法则具有更高的效率。

### 回答3：
1. 冒泡排序：
第一趟排序后：2，12，16，28，10，16*，20，6，18，30
第二趟排序后：2，12，16，10，16*，20，6，18，28，30
第三趟排序后：2，12，10，16*，6，18，16，20，28，30
第四趟排序后：2，10，12，6，16*，16，18，20，28，30
第五趟排序后：2，10，6，12，16*，16，18，20，28，30
第六趟排序后：2，6，10，12，16*，16，18，20，28，30
经过六趟排序后，关键字序列有序。

2. 选择排序：
第一趟排序后：2，12，16，30，28，10，16*，20，6，18
第二趟排序后：2，6，16，30，28，10，16*，20，12，18
第三趟排序后：2，6，10，30，28，16*，16，20，12，18
第四趟排序后：2，6，10，12，28，16*，16，20，30，18
第五趟排序后：2，6，10，12，16*，28，16，20，30，18
第六趟排序后：2，6，10，12，16*，16，28，20，30，18
第七趟排序后：2，6，10，12，16*，16，18，20，30，28
经过七趟排序后，关键字序列有序。

3. 插入排序：
第一趟排序后：2，12，16，30，28，10，16*，20，6，18
第二趟排序后：2，12，16，30，28，10，16*，20，6，18
第三趟排序后：2，12，16，28，30，10，16*，20，6，18
第四趟排序后：2，10，12，16*，16，20，28，30，6，18
第五趟排序后：2，6，10，12，16*，16，18，20，28，30
经过五趟排序后，关键字序列有序。

4. 希尔排序：
第一趟排序后：10，2，16，6，12，18，16*，20，28，30
第二趟排序后：2，6，10，12，16，16*，18，20，28，30
经过两趟排序后，关键字序列有序。

5. 快速排序：
第一趟排序后：10，2，6，12，16，18，16*，20，28，30
第二趟排序后：6，2，10，12，16，18，16*，20，28，30
第三趟排序后：2，6，10，12，16，16*，18，20，28，30
经过三趟排序后，关键字序列有序。