设待排序的关键字序列为{12,22,116,30,28,10,160,20,6,18},试写出使用希尔排序(增量为5,2,1)排序方法每趟排序后的结果,并说明做了多少次关键字比较。
时间: 2024-05-27 22:09:23 浏览: 18
首先,希尔排序是一种插入排序的改进版,它通过将原序列分成若干个子序列,对每个子序列进行插入排序,使得整个序列变得越来越有序。具体步骤如下:
1. 选择一个增量序列,本例中为5、2、1。
2. 对于每个增量,分别对子序列进行插入排序,即对距离为增量的元素进行排序。例如增量为5时,将序列分为{12,10},{22,160},{116,20},{30,6},{28,18},每个子序列都进行插入排序。
3. 重复步骤2,直到增量为1时,进行最后一次插入排序。
根据上述步骤,我们可以得出以下每趟排序后的结果:
第1趟排序:{10,18,6,20,12,22,116,30,28,160}
第2趟排序:{6,18,10,20,12,22,28,30,116,160}
第3趟排序:{6,10,12,18,20,22,28,30,116,160}
根据插入排序的算法,每比较一对关键字就需要进行一次交换或移动,因此我们需要统计每趟排序中的关键字比较次数。
第1趟排序需要比较10次关键字;
第2趟排序需要比较15次关键字;
第3趟排序需要比较12次关键字。
因此,希尔排序总共需要比较37次关键字。
相关问题
数据结构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
经过三趟排序后,关键字序列有序。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)