对这个序列[12,2,16,30,28,10,16*,20,6,18]进行堆排序,要求给出每趟排序结束后序列的状态
时间: 2023-09-19 08:09:12 浏览: 68
初始序列:[12, 2, 16, 30, 28, 10, 16*, 20, 6, 18]
第一趟排序结束后序列状态:[30, 28, 16, 20, 18, 10, 16*, 2, 6, 12]
第二趟排序结束后序列状态:[30, 28, 16, 20, 18, 10, 16*, 2, 6, 12]
第三趟排序结束后序列状态:[30, 28, 20, 16, 18, 10, 16*, 2, 6, 12]
第四趟排序结束后序列状态:[30, 28, 20, 16, 18, 10, 16*, 2, 6, 12]
第五趟排序结束后序列状态:[30, 28, 20, 16, 18, 10, 16*, 2, 6, 12]
第六趟排序结束后序列状态:[30, 28, 20, 16, 18, 10, 16*, 2, 6, 12]
第七趟排序结束后序列状态:[30, 28, 20, 16, 18, 10, 16*, 2, 6, 12]
第八趟排序结束后序列状态:[20, 18, 16, 16*, 6, 10, 12, 2, 28, 30]
第九趟排序结束后序列状态:[18, 16, 12, 16*, 6, 10, 2, 20, 28, 30]
最终排序结果:[2, 6, 10, 12, 16, 18, 16*, 20, 28, 30]
其中,被标记为16*的元素表示当前堆顶元素,即每趟排序中需要和堆底元素进行交换的元素。
相关问题
12,2,16,30,28,10,16*,20,6,18进行堆排序,输出每一趟排序后的关键字序列
堆排序是一种树形选择排序,它利用了堆这种数据结构的特性来实现排序。
首先,将原始数组构建成一个最大堆。然后,将堆顶元素(即最大元素)与堆的最后一个元素交换,并将堆的大小减一。接着,对堆进行一次维护操作,使其重新成为一个最大堆。重复以上步骤,直到堆的大小减小到1为止。
下面是每一趟排序后的关键字序列:
1. 30, 28, 16*, 20, 18, 16, 10, 2, 6, 12
2. 28, 20, 16*, 18, 12, 16, 10, 2, 6, 30
3. 20, 18, 16*, 6, 12, 16, 10, 2, 28, 30
4. 18, 12, 16*, 6, 2, 16, 10, 20, 28, 30
5. 16, 12, 10*, 6, 2, 16, 18, 20, 28, 30
6. 12, 6, 10*, 16, 2, 16, 18, 20, 28, 30
7. 10, 6, 2*, 16, 12, 16, 18, 20, 28, 30
8. 6, 2*, 10, 16, 12, 16, 18, 20, 28, 30
9. 2*, 6, 10, 16, 12, 16, 18, 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
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)