.给出一组关键字(12,2,16,30,8,28,4,10,20,6,18) (1)以该序列为输入序列构造二叉排序树 (2)按从小到大顺序,写出对其进行快速排序第一趟(轴元素为第一个元素)的排序过程。
时间: 2023-08-14 21:06:27 浏览: 116
(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 已经被放到了正确的位置上,原序列被划分成了两个子序列,左子序列中的元素均小于轴元素,右子序列中的元素均大于轴元素。下一步可以分别对左右子序列进行快速排序的第二趟排序。
相关问题
1.给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列; (1) 希尔排序(第一趟排序的增量为5) (2) 快速排序(选第一个记录为枢轴) (3) 基数排序(基数为10)
好的,我来回答你的问题。
1. 希尔排序第一趟结束时的序列:
初始序列:12 2 16 30 8 28 4 10 20 6 18
第一趟增量为5,将序列分成5组:
12 28
2 4
16 10
30 20
8 6
对每组进行插入排序,得到:
8 4 16 20 6 28 2 10 12 30 18
因此第一趟结束时的序列是:8 4 16 20 6 28 2 10 12 30 18
2. 快速排序第一趟结束时的序列:
初始序列:12 2 16 30 8 28 4 10 20 6 18
选第一个记录12作为枢轴,将序列分成两部分:
左部分:2 8 4 10 6
右部分:16 30 28 20 18
对左部分进行快速排序,得到:
2 4 6 8 10 12 16 30 28 20 18
因此第一趟结束时的序列是:2 4 6 8 10 12 16 30 28 20 18
3. 基数排序第一趟结束时的序列:
初始序列:12 2 16 30 8 28 4 10 20 6 18
第一趟按个位数字排序,得到:
10 12 2 4 6 8 20 28 16 30 18
因此第一趟结束时的序列是:10 12 2 4 6 8 20 28 16 30 18
希望我的回答能够帮助你解决问题!
给出一组关键字序列{12,2,16,30,8,28,4,10,20,6,18},当用快速排序,选第一个记录为基准点进行划分,从小到大进行排序,第一趟结束时的序列为
首先以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}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)