写一个快速排序python程序
时间: 2023-12-04 16:04:07 浏览: 23
快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
下面是一个 Python 程序实现快速排序的示例:
```
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# 测试
arr = [5, 7, 3, 8, 4, 1, 2, 9, 6]
print(quick_sort(arr)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
```
快速排序是一种非常高效的排序算法,它的平均时间复杂度为 O(nlogn),最坏情况下的时间复杂度为 O(n^2)。
相关问题
用python写一个快速排序的程序
下面是一个使用 Python 语言的快速排序的程序:
```
def quick_sort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
print(quick_sort([10, 5, 2, 3]))
```
程序的流程是:
1. 如果数组的长度小于 2,那么就直接返回这个数组;
2. 否则,选取数组的第一个元素作为基准值 pivot;
3. 创建两个列表 less 和 greater,分别存储数组中小于等于 pivot 的值和大于 pivot 的值;
4. 对 less 和 greater 分别使用快速排序;
5. 最后,将排好序的 less 和 pivot 和排好序的 greater 合并在一起并返回。
希望这个程序能帮到你!
用Python写一个快速排序的程序
好的,以下是使用Python实现快速排序的示例代码:
```python
def quicksort(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 quicksort(left) + [pivot] + quicksort(right)
```
在上述代码中,我们定义了一个名为 `quicksort` 的函数,该函数接受一个列表作为输入,并返回一个已排序的列表。
首先,我们判断列表的长度是否小于或等于1,如果是,则说明列表已经是有序的或为空列表,因此直接返回。
否则,我们选择列表的第一个元素作为“枢轴”(pivot),并将其从列表中删除。然后,我们迭代列表中的每个元素,如果元素小于枢轴,则将其添加到 `left` 列表中,否则添加到 `right` 列表中。
最后,我们将左半部分、枢轴和右半部分分别递归调用 `quicksort` 函数进行排序,并将它们拼接在一起,返回一个已排序的列表。