请编写python代码:快速排序
时间: 2024-03-02 12:37:26 浏览: 24
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
# 测试
arr = [4, 2, 1, 5, 3]
print(quicksort(arr)) # [1, 2, 3, 4, 5]
相关问题
编写一段快速排序的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)
arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr)) # 输出 [1, 1, 2, 3, 6, 8, 10]
```
这段代码使用了递归,对于列表中的元素,每次选择一个元素作为"枢轴"(pivot),将小于它的元素放在左边,等于它的元素放在中间,大于它的元素放在右边。然后,对于左右两边的子列表递归地调用快速排序,最终得到排好序的列表。
请写一段python快速排序代码
### 回答1:
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
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)
### 回答2:
快速排序是一种常见的排序算法,它通过选择一个基准元素,将待排序的序列分为两个子序列,左边的序列中的元素都小于基准元素,右边的序列中的元素都大于基准元素,然后对两个子序列进行递归排序,最终得到有序序列。
下面是一段用Python实现的快速排序代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
# 测试代码
arr = [5, 3, 8, 2, 1, 9, 7, 6, 4]
sorted_arr = quick_sort(arr)
print(sorted_arr)
```
上面的代码中,`quick_sort`函数实现了快速排序的逻辑。首先判断待排序的序列长度是否小于等于1,如果是,则直接返回。否则,选择第一个元素作为基准元素,并将序列分为两个子序列:`less`中元素小于等于基准元素,`greater`中元素大于基准元素。然后对两个子序列进行递归排序,并将排序结果和基准元素合并返回。
最后,我们可以通过测试代码检验快速排序的效果。例如,给定序列`arr = [5, 3, 8, 2, 1, 9, 7, 6, 4]`,使用`quick_sort`函数对其进行排序,并打印排序结果。运行结果为`[1, 2, 3, 4, 5, 6, 7, 8, 9]`,证明快速排序算法是正确的。
### 回答3:
快速排序是一种常用的排序算法,它通过选择一个基准元素,将数组分成两个子数组,较小的元素放在基准元素的左边,较大的元素放在基准元素的右边,然后对这两个子数组进行递归排序,最终得到有序数组。
下面是一个使用Python编写的快速排序代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0] # 选择第一个元素作为基准元素
less = [x for x in arr[1:] if x <= pivot] # 小于等于基准元素的子数组
greater = [x for x in arr[1:] if x > pivot] # 大于基准元素的子数组
return quick_sort(less) + [pivot] + quick_sort(greater) # 递归排序并合并子数组
# 测试代码
arr = [5, 2, 8, 4, 1, 9, 6, 3, 7]
sorted_arr = quick_sort(arr)
print(sorted_arr)
```
以上代码中,定义了一个`quick_sort`函数来实现快速排序。首先判断输入的数组长度是否小于等于1,如果是,则直接返回该数组。否则,选择数组的第一个元素作为基准元素,对剩余的元素进行划分。通过列表推导式,将小于等于基准元素的元素放在一个子数组`less`中,大于基准元素的元素放在另一个子数组`greater`中。接着,对两个子数组分别进行递归排序,并将排序后的结果与基准元素合并,最终得到排序好的数组。
以上的示例代码会输出`[1, 2, 3, 4, 5, 6, 7, 8, 9]`,证明快速排序算法的正确性。
相关推荐
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)