{39,80,76,41,13,29,50,78,30,11,100,7,41,86}快速排序要排多少躺
时间: 2023-09-27 10:12:05 浏览: 51
在最坏情况下,即每次选择的基准数都是当前子数组中最大或最小的数,快速排序需要进行 n 次递归,其中 n 为待排序数组的长度。因此,在最坏情况下,{39,80,76,41,13,29,50,78,30,11,100,7,41,86} 快速排序需要递归 14 次。
但是,在平均情况下,快速排序的时间复杂度为 O(nlogn),比较快速,实际应用中表现良好。
相关问题
{39,80,76,41,13,29,50,78,30,11,100,7,41,86}快速排序过程
快速排序可以通过分治的思想进行实现,其基本步骤如下:
1. 选择一个基准数(pivot),通常选择第一个数作为基准数。
2. 将数组中小于等于基准数的元素放在基准数左边,大于基准数的元素放在基准数右边。
3. 对于左右两个子数组,重复以上步骤。
下面是 {39,80,76,41,13,29,50,78,30,11,100,7,41,86} 快速排序的过程:
1. 选择第一个数 39 作为基准数。
2. 将数组分为两个子数组,小于等于 39 的为 {13,29,30,11,7},大于 39 的为 {80,76,41,50,78,100,41,86}。
3. 对左边的子数组进行快速排序,选择第一个数 13 作为基准数。
4. 将左边的子数组分为两个子数组,小于等于 13 的为 {11,7},大于 13 的为 {29,30}。
5. 对左边的子数组进行快速排序,选择第一个数 11 作为基准数。
6. 将左边的子数组分为两个子数组,小于等于 11 的为 {7},大于 11 的为 {}。
7. 左边的子数组已经有序,返回。
8. 对右边的子数组进行快速排序,选择第一个数 80 作为基准数。
9. 将右边的子数组分为两个子数组,小于等于 80 的为 {76,41,50,78,41},大于 80 的为 {100,86}。
10. 对左边的子数组进行快速排序,选择第一个数 76 作为基准数。
11. 将左边的子数组分为两个子数组,小于等于 76 的为 {41,50,41},大于 76 的为 {78}。
12. 对左边的子数组进行快速排序,选择第一个数 41 作为基准数。
13. 将左边的子数组分为两个子数组,小于等于 41 的为 {41},大于 41 的为 {50}。
14. 左边的子数组已经有序,返回。
15. 对右边的子数组进行快速排序,选择第一个数 100 作为基准数。
16. 将右边的子数组分为两个子数组,小于等于 100 的为 {86},大于 100 的为 {}。
17. 右边的子数组已经有序,返回。
18. 整个数组已经有序,排序完成。
最终的有序数组为 {7,11,13,29,30,39,41,41,50,76,78,80,86,100}。
{39,80,76,41,13,29,50,78,30,11,100,7,41,86}快序排序过程
快速排序的过程如下:
1. 选择一个基准元素(可以是任意一个元素),例如选择第一个元素39作为基准元素。
2. 将序列中比基准元素小的元素放在基准元素前面,比基准元素大的元素放在基准元素后面,相等的元素可以放在任意一边。具体做法是维护两个指针i和j,初始时i指向第一个元素,j指向最后一个元素,然后从j开始向前搜索第一个小于等于基准元素的元素,找到后将其与i指向的元素交换,然后从i开始向后搜索第一个大于等于基准元素的元素,找到后将其与j指向的元素交换,重复这个过程直到i>=j,此时将基准元素放在i指向的位置即可。
3. 对基准元素左右两边的子序列分别重复上述过程,直到所有子序列的长度都为1。
根据上述过程,给出{39,80,76,41,13,29,50,78,30,11,100,7,41,86}的快速排序过程如下:
第一趟排序:基准元素为39,序列为{39,80,76,41,13,29,50,78,30,11,100,7,41,86},交换后得到{7,11,29,30,13,39,50,78,41,76,100,80,41,86},此时基准元素39已经放到了正确的位置上。
第二趟排序:基准元素为7,序列为{7,11,29,30,13},交换后得到{7,11,29,30,13},此时基准元素7已经放到了正确的位置上。
第三趟排序:基准元素为11,序列为{11,29,30},交换后得到{11,29,30},此时基准元素11已经放到了正确的位置上。
第四趟排序:基准元素为29,序列为{29,30},交换后得到{29,30},此时基准元素29已经放到了正确的位置上。
第五趟排序:基准元素为13,序列为{13},交换后得到{13},此时基准元素13已经放到了正确的位置上。
第六趟排序:基准元素为50,序列为{50,78,41,76,100,80,41,86},交换后得到{41,41,13,29,39,50,78,76,100,80,86},此时基准元素50已经放到了正确的位置上。
第七趟排序:基准元素为41,序列为{41,13,29,39},交换后得到{13,29,39,41},此时基准元素41已经放到了正确的位置上。
第八趟排序:基准元素为76,序列为{76,100,80,86},交换后得到{76,100,80,86},此时基准元素76已经放到了正确的位置上。
第九趟排序:基准元素为100,序列为{100,80,86},交换后得到{80,86,100},此时基准元素100已经放到了正确的位置上。
第十趟排序:基准元素为86,序列为{86,80},交换后得到{80,86},此时基准元素86已经放到了正确的位置上。
最终得到的有序序列为{7,11,13,29,39,41,50,76,80,86,100}。
相关推荐
![torrent](https://img-home.csdnimg.cn/images/20210720083646.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)