假设一组待排序的记录的关键字序列为(45,53,18,36,72,30,48,93,15,16),以排序码36进行划分的过程
时间: 2023-06-17 18:07:27 浏览: 52
划分过程是将待排序的记录分成两部分:左边的记录的关键字序列都小于等于排序码,右边的记录的关键字序列都大于排序码。以排序码36进行划分的过程如下:
1. 选择排序码36作为划分依据。
2. 从序列的左端开始扫描,找到第一个大于36的记录,将其位置记为i。
3. 从序列的右端开始扫描,找到第一个小于等于36的记录,将其位置记为j。
4. 如果i<j,则交换位置i和位置j的记录。
5. 重复步骤2-4,直到i>=j为止。
6. 最后将排序码36所在的位置k与位置j交换,即完成划分过程。
对于序列(45,53,18,36,72,30,48,93,15,16),以排序码36进行划分的过程如下:
1. 选择排序码36作为划分依据。
2. 从左端开始扫描,找到第一个大于36的记录,即记录45,将其位置记为i=1。
3. 从右端开始扫描,找到第一个小于等于36的记录,即记录30,将其位置记为j=6。
4. 交换位置i和位置j的记录,得到序列(30,53,18,36,72,45,48,93,15,16)。
5. 继续扫描,找到第二个大于36的记录,即记录53,将其位置记为i=2。
6. 找到第二个小于等于36的记录,即记录18,将其位置记为j=3。
7. 交换位置i和位置j的记录,得到序列(30,18,53,36,72,45,48,93,15,16)。
8. 继续扫描,找到第三个大于36的记录,即记录53,将其位置记为i=3。
9. 找到第三个小于等于36的记录,即记录15,将其位置记为j=9。
10. 交换位置i和位置j的记录,得到序列(30,18,15,36,72,45,48,93,53,16)。
11. 扫描结束,将排序码36所在的位置4与位置j=2交换,得到序列(30,18,15,16,72,45,48,93,53,36)。此时,序列被划分成了左边的序列(30,18,15,16),右边的序列(72,45,48,93,53,36)。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)