对于给定的一组关键字 46,58,15,45,90,18,10, 62, 46',58',15',45',90',18',10',62'(4)写出快速排序过程(自选主元并说明选择的原因)
时间: 2023-08-30 08:12:21 浏览: 69
好的,我来解答这个问题。
快速排序是一种常用的排序算法,它的基本思想是分治法。具体的实现过程如下:
1. 选择一个主元(pivot)。
2. 将数组分为左右两部分,使得左边部分所有元素都小于等于主元,右边部分所有元素都大于等于主元。
3. 对左右两部分分别递归执行步骤1和步骤2。
4. 递归结束的条件是只剩下一个元素或者没有元素。
在选择主元的时候,一般有三种方法:随机选择、选取第一个元素或者最后一个元素、三数取中法。这里我们选择三数取中法作为主元,因为这种方法可以避免最坏情况的发生。
下面是快速排序的详细过程:
1. 选取主元。我们从数组的第一个元素、中间一个元素、最后一个元素分别取出一个数,把它们排序,然后选取中间的元素46作为主元。
2. 进行分区。我们从数组的两端开始向中间扫描,如果左端的元素小于等于主元,就继续向右移动,直到找到大于主元的元素。同样地,如果右端的元素大于等于主元,就继续向左移动,直到找到小于主元的元素。当左端的元素大于主元并且右端的元素小于主元时,交换这两个元素。重复这个过程,直到左右两端相遇。
3. 递归排序左右两部分。递归地对左右两部分分别进行快速排序。
下面是排序的过程:
首先,我们选取主元46。
初始数组:46, 58, 15, 45, 90, 18, 10, 62, 46', 58', 15', 45', 90', 18', 10', 62'
第一次分区:10, 15, 18, 45, 46, 46', 58, 62, 90, 10', 15', 18', 45', 58', 62', 90'
第一次递归:10, 15, 18, 45, 46, 46', 58, 62, 90
第二次分区:10, 15, 18, 45, 46, 46', 58, 62, 90
第二次递归:10, 15, 18, 45
第三次分区:10, 15, 18, 45
第三次递归:已经排好序,不需要再排序了。
第四次分区:46, 46', 58, 62, 90
第四次递归:46, 46', 58, 62, 90
第五次分区:46, 46', 58, 62, 90
第五次递归:46, 46', 58, 62, 90
最终结果:10, 15, 18, 45, 46, 46', 58, 62, 90, 10', 15', 18', 45', 58', 62', 90'
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)