python 快速排序
时间: 2023-10-14 18:28:46 浏览: 35
快速排序是一种常用的排序算法,它的核心思想是分治法,通过不断地分割和排序来达到排序的目的。下面是 Python 实现快速排序的示例代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
```
在这个实现中,我们首先检查数组的长度是否小于等于 1,如果是,则直接返回原数组。然后选择一个 pivot(基准值),将数组分成三个部分:小于 pivot 的元素、等于 pivot 的元素和大于 pivot 的元素。最后,将三部分分别递归地排序,并将它们连接在一起。这样就实现了快速排序。
示例用法:
```python
arr = [3, 6, 2, 9, 8, 1, 5, 4, 7]
print(quick_sort(arr)) # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
```
注意:快速排序的时间复杂度为 O(nlogn),但在最坏情况下(即数组已经有序或近乎有序),时间复杂度会退化为 O(n^2)。为了避免这种情况,可以采用随机化选择 pivot 的方式。