python 实现快速排序
时间: 2023-09-12 09:02:50 浏览: 40
快速排序是一种常见的排序算法,其基本思想是通过将待排序序列分成两个子序列,其中一个子序列的所有元素都比另一个子序列的所有元素小,然后对这两个子序列递归地进行排序,最终将整个序列排序完成。
下面是 Python 实现快速排序的代码:
```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)
```
在这个代码中,我们首先判断待排序序列的长度是否小于等于 1,如果是,则直接返回原序列。然后选择序列中的第一个元素作为枢纽元素(pivot),并将序列分成两个子序列:左子序列中的元素都比枢纽元素小,右子序列中的元素都比枢纽元素大。接着对左右子序列递归地进行快速排序,最后将左子序列、枢纽元素和右子序列合并起来得到排序后的序列。
快速排序的时间复杂度为 O(nlogn)。
相关问题
python实现快速排序
好的,以下是Python实现快速排序的代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
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)
```
这个实现使用了递归来进行排序,首先选择列表中的第一个元素作为基准点(pivot),然后将列表中其他元素分为两部分,小于基准点的放在左边,大于等于基准点的放在右边。然后递归地对左右两部分分别进行快速排序,最后再将左、基准点、右三部分合并起来。
Python实现快速排序
好的,以下是Python实现快速排序的代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
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)
```
这个实现使用了递归来进行排序,首先选择列表中的第一个元素作为基准点(pivot),然后将列表中其他元素分为两部分,小于基准点的放在左边,大于等于基准点的放在右边。然后递归地对左右两部分分别进行快速排序,最后再将左、基准点、右三部分合并起来。