给出一组关键字序列{12,2,16,30,8,28,4,10,20,6,18},当用快速排序,选第一个记录为基准点进行划分,从小到大进行排序,第一趟结束时的序列为
时间: 2023-10-08 20:04:58 浏览: 140
首先以12作为基准点,将序列划分为左右两部分:
左部分:{2,8,4,10,6}
右部分:{16,30,28,20,18}
接下来,分别对左右两部分重复以上步骤,直至排序完成。
左部分:
以2作为基准点,将序列划分为左右两部分:
左部分:空
右部分:{8,4,10,6}
以8作为基准点,将右部分划分为左右两部分:
左部分:{4,6}
右部分:{10}
以4作为基准点,将左部分划分为左右两部分:
左部分:空
右部分:{6}
右部分已经有序,左部分再次递归后也为空,此时左部分排序完成。
右部分:
以16作为基准点,将序列划分为左右两部分:
左部分:空
右部分:{30,28,20,18}
以30作为基准点,将右部分划分为左右两部分:
左部分:{28,20,18}
右部分:空
以28作为基准点,将左部分划分为左右两部分:
左部分:{20,18}
右部分:空
以20作为基准点,将左部分划分为左右两部分:
左部分:{18}
右部分:空
左部分已经有序,右部分再次递归后也为空,此时右部分排序完成。
最终序列为:{2,4,6,8,10,12,16,18,20,28,30}
相关问题
给出一组关键字序列{12,2,16,30,8,28,4,10,20,6,18},当用快速排序(选第一个记录为基准点进行划分,采用教材P336-337描述的算法)从小到大进行排序第一趟结束时的序列为
我们先以12作为基准点,进行划分:
划分前的序列:12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18
划分后的序列:6, 2, 4, 10, 8, 12, 28, 30, 20, 16, 18
此时,基准点12已经到达了序列的中间位置,左边的数都比它小,右边的数都比它大。
接下来,我们需要对左右两个子序列分别进行快速排序。
左子序列:6, 2, 4, 10, 8
右子序列:28, 30, 20, 16, 18
以左子序列为例,选取第一个元素6作为基准点,进行划分:
划分前的序列:6, 2, 4, 10, 8
划分后的序列:4, 2, 6, 10, 8
此时,基准点6已经到达了左子序列的中间位置,左边的数都比它小,右边的数都比它大。
接下来,我们需要对左右两个子序列分别进行快速排序。
左子序列:4, 2
右子序列:10, 8
左子序列已经有序,不需要再排序。对右子序列进行划分。
划分前的序列:10, 8
划分后的序列:8, 10
此时,基准点10已经到达了右子序列的中间位置,左边的数都比它小,右边的数都比它大。
右子序列已经有序,不需要再排序。
最终的排序结果为:2, 4, 6, 8, 10, 12, 16, 18, 20, 28, 30
.给出一组关键字(12,2,16,30,8,28,4,10,20,6,18) (1)以该序列为输入序列构造二叉排序树 (2)按从小到大顺序,写出对其进行快速排序第一趟(轴元素为第一个元素)的排序过程。
(1) 构造二叉排序树的过程如下:
```
12
/ \
2 16
\ / \
8 10 30
/ \ / \
4 6 20 28
\
18
```
(2) 进行快速排序的第一趟时,选择第一个元素 12 作为轴元素(pivot),排序过程如下:
```
原始序列:12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18
轴元素:12
第一趟排序过程:
12, 2, 8, 4, 10, 6, 16, 30, 28, 20, 18
左子序列:2, 8, 4, 10, 6
右子序列:16, 30, 28, 20, 18
```
经过第一趟排序后,轴元素 12 已经被放到了正确的位置上,原序列被划分成了两个子序列,左子序列中的元素均小于轴元素,右子序列中的元素均大于轴元素。下一步可以分别对左右子序列进行快速排序的第二趟排序。
相关推荐
![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)