待排序的关键字序列为{12,2,16,30,28,10,16,20,6,18},写出希尔排序每一趟的结果,增量序列为5,3,1
时间: 2023-05-15 13:05:55 浏览: 127
第一趟排序结果:{10, 2, 6, 20, 18, 12, 16, 30, 28, 16}
第二趟排序结果:{6, 2, 10, 16, 16, 12, 18, 30, 28, 20}
第三趟排序结果:{2, 6, 10, 12, 16, 16, 18, 20, 28, 30}
相关问题
设待排序的关键字序列为{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
经过三趟排序后,关键字序列有序。
所给定的待排序的关键字序列为{12,2,16,30,28,10,16*,20,6,18},采用堆排序的方法,每趟排序结束后关键字序列的状态:
所给定的待排序的关键字序列为{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
相关推荐
![](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)