给定关键字序列{50,12,31,100,81,40,63,18,72,4,28,120,66,38},写出采用快速排序时第一趟排序过程中的数据移动情况。
时间: 2023-09-17 10:11:06 浏览: 33
以第一个元素50为基准,进行一趟快速排序的过程如下:
1. 从右往左扫描序列,找到第一个小于50的元素,将其与50交换位置,序列变为{28,12,31,4,81,40,63,18,72,100,50,120,66,38};
2. 从左往右扫描序列,找到第一个大于50的元素,将其与50交换位置,序列变为{28,12,31,4,38,40,63,18,72,100,81,120,66,50};
3. 继续从右往左扫描序列,找到第一个小于50的元素,将其与50交换位置,序列变为{28,12,31,4,38,40,18,63,72,100,81,120,66,50};
4. 继续从左往右扫描序列,找到第一个大于50的元素,将其与50交换位置,序列变为{28,12,31,4,38,40,18,50,72,100,81,120,66,63}。
经过这一趟快速排序后,50被放在了序列的中间位置,比50小的元素都在50左边,比50大的元素都在50右边。
相关问题
1.给定关键字序列(12,13,14,15,16,17,18,19,20,21,22),叙述采用折半查找关键字 12、28的过程,并计算平均查找长度。
好的,我来回答你的问题。
首先,折半查找也叫二分查找,它是一种高效的查找算法。在使用折半查找之前,需要先将待查找的序列按照关键字递增(或递减)的顺序排列。
对于给定的关键字序列(12,13,14,15,16,17,18,19,20,21,22),如果我们要查找关键字12和28,具体过程如下:
1. 初始化查找范围的左右端点left和right,分别指向序列的第一个和最后一个元素。
初始时,left=0,right=10。
2. 计算中间位置mid,mid=(left+right)/2,即mid=5。
3. 比较待查找的关键字12和序列中间位置的关键字17,由于12<17,所以应该在序列的左半部分继续查找。
4. 更新右端点right,right=mid-1,此时right=4。
5. 重新计算中间位置mid,mid=(left+right)/2,即mid=2。
6. 比较待查找的关键字12和序列中间位置的关键字14,由于12>14,所以应该在序列的左半部分继续查找。
7. 更新右端点right,right=mid-1,此时right=1。
8. 重新计算中间位置mid,mid=(left+right)/2,即mid=0。
9. 比较待查找的关键字12和序列中间位置的关键字12,由于二者相等,查找成功,返回元素下标0。
对于关键字28,在第6步比较待查找的关键字12和序列中间位置的关键字14时,由于12<14,所以应该在序列的右半部分查找。更新左端点left,left=mid+1,此时left=3;重新计算中间位置mid,mid=(left+right)/2,即mid=6。在第9步比较待查找的关键字28和序列中间位置的关键字18时,由于28>18,应该在序列的右半部分继续查找。更新左端点left,left=mid+1,此时left=7;重新计算中间位置mid,mid=(left+right)/2,即mid=8。在第9步比较待查找的关键字28和序列中间位置的关键字20时,由于28<20,应该在序列的左半部分继续查找。更新右端点right,right=mid-1,此时right=7;重新计算中间位置mid,mid=(left+right)/2,即mid=7。在第9步比较待查找的关键字28和序列中间位置的关键字19时,由于28>19,应该在序列的右半部分继续查找。更新左端点left,left=mid+1,此时left=8;重新计算中间位置mid,mid=(left+right)/2,即mid=9。在第9步比较待查找的关键字28和序列中间位置的关键字21时,由于28<21,应该在序列的左半部分继续查找。更新右端点right,right=mid-1,此时right=8;重新计算中间位置mid,mid=(left+right)/2,即mid=8。此时left=right=8,查找失败。
平均查找长度ASL是指平均查找一个元素所需的比较次数,公式为ASL=(log2n+1)/2,其中n为序列长度。对于本题中的序列,n=11,所以ASL=(log2(11)+1)/2≈1.5。
给定关键字序列{55,25,6,95,76,12,124,32}构造一棵二叉排序树
好的,我可以回答这个问题。首先,我们需要找出这些关键字的排列顺序,以便将它们插入到二叉排序树中。从最小的关键字开始,我们可以将6插入到树的根节点,然后按照以下顺序插入其余的关键字:12,25,32,55,76,95和124。这样,我们就得到了如下的二叉排序树:
6
/ \
12 25
\ / \
55 76 95
\
124
希望我的回答对您有帮助。
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)