快速排序
时间: 2023-06-22 19:17:32 浏览: 36
快速排序(QuickSort)是一种常用的排序算法,也是一种分治算法。它将一个数组分成两个子数组,然后递归地排序两个子数组。具体实现步骤如下:
1. 选择一个基准元素(pivot),一般选择第一个元素或者最后一个元素。
2. 将所有小于基准元素的元素移到基准元素的左边,将所有大于基准元素的元素移到基准元素的右边,这个过程称为分区(partition)。
3. 递归地对基准元素左边的子数组和右边的子数组进行快速排序。
具体的实现代码如下(以升序排序为例):
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
```
快速排序的时间复杂度为O(nlogn),空间复杂度为O(logn)。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)