给定一组整数: { 47, 25, 87, 36, 90, 18, 65, 31, 79, 58 } 采用快速排序法,请写出经过一趟排序后的结果:和解析过程:
时间: 2023-09-15 11:17:33 浏览: 90
快速排序是一种基于分治思想的排序算法,它将原始数组划分成两个子数组,其中一个子数组的所有元素都比另一个子数组的所有元素小,然后递归地对两个子数组进行排序,直到整个数组都有序。
给定一组整数:{ 47, 25, 87, 36, 90, 18, 65, 31, 79, 58 },第一趟快速排序的结果如下:
```
31, 25, 18, 36, 47, 90, 65, 87, 79, 58
```
解析:在第一趟快速排序中,我们选择数组的第一个元素47作为枢纽元素(pivot)。然后,我们将数组中小于等于枢纽元素的元素放在枢纽元素的左边,将大于枢纽元素的元素放在枢纽元素的右边。在这个过程中,我们使用两个指针i和j,分别从左往右和从右往左扫描数组,找到需要交换位置的元素。
具体地,我们首先从左往右扫描数组,找到第一个大于枢纽元素的元素36(i=3)。然后,从右往左扫描数组,找到第一个小于枢纽元素的元素31(j=7)。接下来,交换元素36和31的位置,此时数组变成了{ 47, 25, 87, 31, 90, 18, 65, 36, 79, 58 }。然后,继续从左往右扫描数组,找到第一个大于枢纽元素的元素90(i=4)。然后,从右往左扫描数组,找到第一个小于枢纽元素的元素58(j=9)。接下来,交换元素90和58的位置,此时数组变成了{ 47, 25, 87, 31, 58, 18, 65, 36, 79, 90 }。
最后,枢纽元素47和元素58交换位置,此时数组变成了{ 36, 25, 18, 31, 47, 58, 65, 87, 79, 90 }。现在,枢纽元素的位置已经确定了,小于枢纽元素的元素都在枢纽元素的左边,大于枢纽元素的元素都在枢纽元素的右边。接下来,我们递归地对枢纽元素的左边和右边的子数组进行快速排序。因此,第一趟快速排序后,数组的结果是31, 25, 18, 36, 47, 90, 65, 87, 79, 58。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)