对关键字序列(26, 18, 60, 14, 7, 45, 13, 32) 进行降序的堆排序,写出构建的初始堆及前两趟排序重建堆之后序列状态。
时间: 2023-09-12 18:07:59 浏览: 87
构建初始堆的过程如下:
```
26
/ \
18 60
/ \ / \
14 7 45 13
/ \
32 ...
```
第一趟排序,将堆顶元素 26 与最后一个叶子节点 32 交换位置,然后将剩余元素重新构建成一个最大堆:
```
32
/ \
18 60
/ \ / \
14 7 45 13
/
26
```
第二趟排序,将堆顶元素 32 与最后一个叶子节点 13 交换位置,然后将剩余元素重新构建成一个最大堆:
```
60
/ \
18 45
/ \ / \
14 7 26 13
```
因此,排序后的关键字序列为:(60, 45, 26, 18, 14, 13, 7, 32)。
相关问题
3.对关键字序列(26, 18, 60, 14, 7, 45, 13, 32) 进行降序的堆排序,写出构建的初始堆及前两趟排序重建堆之后序列状态。
首先,构建初始堆的过程如下:
1. 将关键字序列依次插入到一个空堆中,得到一个初始堆。
2. 从最后一个非叶子节点开始,依次向上调整堆,使得每个节点的关键字都大于等于其子节点的关键字,直到根节点。
在这个过程中,最后一个非叶子节点的下标为3(从0开始计数),其关键字为14。进行调整后,得到以下初始堆:
```
60 18 45 14 7 26 13 32
```
接下来,进行堆排序的过程如下:
1. 将堆顶元素60与最后一个元素32交换位置,得到以下序列:`32 18 45 14 7 26 13 60`。
2. 将堆顶元素32向下调整堆,得到以下序列:`60 18 45 14 7 26 13 32`。
3. 将堆顶元素60与最后一个元素13交换位置,得到以下序列:`13 18 45 14 7 26 60 32`。
4. 将堆顶元素13向下调整堆,得到以下序列:`60 18 45 14 7 26 32 13`。
经过以上两趟排序和重建堆,得到的序列状态为:`60 18 45 14 7 26 32 13`。
对关键字序列{42,13,91,23,24,16,5,88}采用快速排序进行升序排序写出第一趟排序结果
首先,选择一个枢纽元素(pivot element),可以是序列中的任意一个元素。假设我们选择第一个元素42作为枢纽元素。
然后,根据枢纽元素将序列分为两部分,一部分是小于枢纽元素的元素,另一部分是大于枢纽元素的元素。在第一趟排序中,我们需要将序列调整为以下形式:
{13, 23, 24, 16, 5, 42, 91, 88}
在这个调整过程中,我们从序列的右端开始,找到第一个小于枢纽元素的元素,然后从序列的左端开始,找到第一个大于枢纽元素的元素。将这两个元素交换位置。重复这个过程,直到左指针和右指针相遇。
最后,将枢纽元素与相遇点的元素交换位置。这样,枢纽元素左边的元素都小于枢纽元素,右边的元素都大于枢纽元素。
在这个例子中,第一趟排序结果为:
{13, 23, 24, 16, 5, 42, 91, 88}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)