用快速排序中的划分函数partition,对划分段“20,18,29,16,34,65,14,19,37”进行划分,请画出一次划分过程及结果。
时间: 2024-04-15 21:25:51 浏览: 28
好的,请等一下,我来为你画出划分过程及结果。
首先,我们选择最后一个元素37作为划分基准。然后,我们定义两个指针,i指向划分段的头部,j指向划分段的尾部。
初始状态:
20,18,29,16,34,65,14,19,[37]
接下来,我们开始进行划分过程。首先,移动指针i向右,直到找到一个大于等于基准值的元素。然后,移动指针j向左,直到找到一个小于基准值的元素。如果i和j没有相遇,则交换它们指向的元素。
第一次交换:
20,18,29,16,34,65,14,19,[37]
i j
由于i指向的元素19小于基准值37,而j指向的元素14大于等于基准值37,所以我们交换它们。
交换后的状态:
20,18,29,16,34,65,[14],19,[37]
i j
接下来,继续移动指针i和j,并重复上述过程。
第二次交换:
20,18,29,16,34,[14],65,19,[37]
i j
第三次交换:
20,18,29,16,[14],34,65,19,[37]
i j
第四次交换:
20,18,[14],16,29,34,65,19,[37]
i j
第五次交换:
20,[14],18,16,29,34,65,19,[37]
i j
第六次交换:
[14],20,18,16,29,34,65,19,[37]
i j
现在i和j相遇了,我们将基准值37与i指向的元素14进行交换。
最终结果:
[14],20,18,16,29,34,19,[37],65
划分过程结束。划分后的结果是基准值37被正确地放置在了它的最终位置上,并且划分段被分成了两个子段:左边的子段中的元素都小于基准值37,右边的子段中的元素都大于等于基准值37。
希望这个示例能够帮助你理解快速排序中的划分过程。如果还有其他问题,请随时提问!
相关推荐
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)