设一个关键字序列为{3, 17, 12, 61, 8, 70, 97, 75, 53, 26, 54, 61*},写出快速排序的排序过程。
时间: 2023-09-27 10:12:48 浏览: 46
好的,我可以为您详细介绍快速排序的排序过程。下面是对所提到的快速排序算法的排序过程:
首先选择一个基准值,本例中选择第一个元素3作为基准值。将序列分为两部分,左边部分全部小于基准值,右边部分全部大于基准值。具体过程如下:
{3, 17, 12, 61, 8, 70, 97, 75, 53, 26, 54, 61*}
{3, 17, 12, 8, 26, 54, 53} 61 {70, 97, 75, 61*}
对左边部分{3, 17, 12, 8, 26, 54, 53}重复上述过程,选择第一个元素3作为基准值。分为两部分:
{3, 17, 12, 8} 26 {54, 53}
{3, 12, 8} 17 {} 26 {54, 53}
{3, 8} 12 {} 17 {} 26 {54, 53}
最终得到左边部分的有序序列{3, 8, 12, 17, 26, 53, 54}。对右边部分{70, 97, 75, 61*}重复上述过程,选择第一个元素70作为基准值。分为两部分:
{70, 97, 75} 61* {}
{70, 75} 97 {} 61*
最终得到右边部分的有序序列{61, 70, 75, 97}。将左右两部分合并得到的有序序列为{3, 8, 12, 17, 26, 53, 54, 61, 70, 75, 97, 61*},其中61*是原序列中的重复元素。
需要注意的是,在实际实现快速排序时,选择基准值的方法有很多种,比如可以选择中间值、随机值等等。还需要注意的是,快速排序的时间复杂度为O(nlogn),但在最坏情况下可能会退化到O(n^2)。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)