设待排序的关键字序列为{43, 12, 56, 70, 18, 101, 12*, 20, 69, 38}, 试分别写出使用以下排序方法, 每趟排序结束后关键字序列的状态。 (1) 简单选择排序 (2) 二路归并排序
时间: 2023-10-07 15:07:19 浏览: 40
(1) 简单选择排序:
第1趟排序后: {12, 43, 56, 70, 18, 101, 12*, 20, 69, 38}
第2趟排序后: {12, 12*, 56, 70, 18, 101, 43, 20, 69, 38}
第3趟排序后: {12, 12*, 18, 70, 56, 101, 43, 20, 69, 38}
第4趟排序后: {12, 12*, 18, 20, 56, 101, 43, 70, 69, 38}
第5趟排序后: {12, 12*, 18, 20, 38, 101, 43, 70, 69, 56}
第6趟排序后: {12, 12*, 18, 20, 38, 43, 101, 70, 69, 56}
第7趟排序后: {12, 12*, 18, 20, 38, 43, 56, 70, 69, 101}
第8趟排序后: {12, 12*, 18, 20, 38, 43, 56, 69, 70, 101}
第9趟排序后: {12, 12*, 18, 20, 38, 43, 56, 69, 70, 101}
(2) 二路归并排序:
第1趟排序后: {12, 43, 56, 70, 18, 101, 12*, 20, 69, 38}
第2趟排序后: {12, 18, 43, 56, 70, 101, 12*, 20, 38, 69}
第3趟排序后: {12, 18, 20, 38, 43, 56, 69, 70, 101, 12*}
第4趟排序后: {12, 12*, 18, 20, 38, 43, 56, 69, 70, 101}
相关问题
设待排序的关键字序列为{43, 12, 56, 70, 18, 101, 12*, 20, 56, 18*}, 试分别写出使用以下排序方法, 每趟排序结束后关键字序列的状态。 (1)冒泡排序 (2)快速排序
### 回答1:
好的,我明白了。下面是使用冒泡排序和快速排序对序列进行排序的过程:
(1) 冒泡排序:
第1趟排序后序列状态: {12, 43, 56, 18, 70, 12*, 20, 56, 18*, 101}
第2趟排序后序列状态: {12, 43, 18, 56, 12*, 20, 56, 18*, 70, 101}
第3趟排序后序列状态: {12, 18, 43, 12*, 20, 56, 18*, 56, 70, 101}
第4趟排序后序列状态: {12, 18, 12*, 20, 43, 18*, 56, 56, 70, 101}
第5趟排序后序列状态: {12, 12*, 18, 20, 18*, 43, 56, 56, 70, 101}
第6趟排序后序列状态: {12*, 12, 18, 18*, 20, 43, 56, 56, 70, 101}
序列已经排好序了。
(2) 快速排序:
第1趟排序后序列状态: {20, 12, 18, 18*, 12*, 43, 56, 56, 70, 101}
序列已经排好序了。
注意: * 代表有相同关键字的元素。
### 回答2:
冒泡排序每一趟比较相邻的两个关键字,如果前一个关键字大于后一个关键字,则交换它们的位置。一趟比较结束后,最大的关键字就会冒泡到序列的末尾。下面是每趟排序结束后关键字序列的状态:
第1趟:{12, 43, 56, 18, 70, 12*, 20, 56, 18*, 101}
第2趟:{12, 43, 18, 56, 12*, 20, 56, 18*, 70, 101}
第3趟:{12, 18, 43, 12*, 20, 56, 18*, 56, 70, 101}
第4趟:{12, 18, 12*, 20, 43, 18*, 56, 56, 70, 101}
第5趟:{12, 12*, 18, 20, 18*, 43, 56, 56, 70, 101}
第6趟:{12, 12*, 18, 18*, 20, 43, 56, 56, 70, 101}
第7趟:{12, 12*, 18, 18*, 20, 43, 56, 56, 70, 101}
第8趟:{12, 12*, 18, 18*, 20, 43, 56, 56, 70, 101}
第9趟:{12, 12*, 18, 18*, 20, 43, 56, 56, 70, 101}
第10趟:{12, 12*, 18, 18*, 20, 43, 56, 56, 70, 101}
快速排序选取一个关键字作为枢纽元,将序列分成两个子序列,小于枢纽元的放在左边,大于枢纽元的放在右边,然后对子序列进行递归排序。下面是每趟排序结束后关键字序列的状态:
第1趟:{18*, 12, 56, 70, 18, 101, 12*, 20, 56, 43}
第2趟:{12*, 12, 18, 20, 18*, 101, 70, 56, 56, 43}
第3趟:{18*, 12, 18, 20, 12*, 101, 70, 56, 56, 43}
第4趟:{12*, 12, 18, 20, 18*, 43, 70, 56, 56, 101}
第5趟:{12*, 12, 18, 20, 18*, 43, 70, 56, 56, 101}
第6趟:{12*, 12, 18, 18*, 20, 43, 70, 56, 56, 101}
第7趟:{12*, 12, 18, 18*, 20, 43, 56, 56, 70, 101}
第8趟:{12*, 12, 18, 18*, 20, 43, 56, 56, 70, 101}
第9趟:{12*, 12, 18, 18*, 20, 43, 56, 56, 70, 101}
第10趟:{12*, 12, 18, 18*, 20, 43, 56, 56, 70, 101}
### 回答3:
(1) 冒泡排序:
第一趟排序:
43, 12, 56, 70, 18, 101, 12*, 20, 56, 18* (比较12和43,交换位置)
12, 43, 56, 70, 18, 101, 12*, 20, 56, 18* (比较43和56,不交换位置)
12, 43, 56, 70, 18, 101, 12*, 20, 56, 18* (比较56和70,不交换位置)
12, 43, 56, 70, 18, 101, 12*, 20, 56, 18* (比较70和18,交换位置)
12, 43, 56, 18, 70, 101, 12*, 20, 56, 18* (比较70和101,不交换位置)
12, 43, 56, 18, 70, 101, 12*, 20, 56, 18* (比较101和12*,交换位置)
12, 43, 56, 18, 70, 12*, 101, 20, 56, 18* (比较101和20,交换位置)
12, 43, 56, 18, 70, 12*, 20, 101, 56, 18* (比较101和56,交换位置)
12, 43, 56, 18, 70, 12*, 20, 56, 101, 18* (比较101和18*,不交换位置)
第二趟排序:
12, 43, 56, 18, 70, 12*, 20, 56, 56, 18*
12, 43, 18, 56, 70, 12*, 20, 56, 56, 18*
12, 43, 18, 56, 70, 12*, 20, 56, 56, 18*
12, 43, 18, 56, 70, 12*, 20, 56, 56, 18*
12, 43, 18, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
第三趟排序:
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
12, 18, 43, 56, 70, 12*, 20, 56, 56, 18*
(2) 快速排序:
第一次划分:
18, 12, 18*, 20, 43, 56, 70, 101, 12*, 56
第二次划分:
12, 18*, 18, 20, 43, 56, 70, 101, 12*, 56
第三次划分:
12, 12*, 18, 18*, 43, 56, 70, 101, 20, 56
第四次划分:
12, 12*, 18, 18*, 20, 43, 56, 70, 56, 101
第五次划分:
12, 12*, 18, 18*, 20, 43, 56, 56, 70, 101
第六次划分:
12, 12*, 18, 18*, 20, 43, 56, 56, 70, 101
最终排序结果为:12, 12*, 18, 18*, 20, 43, 56, 56, 70, 101
设待排序的关键字序列为{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
经过三趟排序后,关键字序列有序。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://img-home.csdnimg.cn/images/20210720083646.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)