Python 快速排序(列表元素自定)
时间: 2024-02-02 20:10:01 浏览: 17
快速排序是一种常用的排序算法,它的基本思想是通过递归地将数组分成较小和较大的两个子数组,然后对这两个子数组进行排序。具体实现如下:
```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 = [5, 2, 8, 9, 1, 3]
sorted_arr = quick_sort(arr)
print(sorted_arr) # 输出:[1, 2, 3, 5, 8, 9]
```
快速排序的时间复杂度为O(nlogn),其中n为数组的长度。它是一种高效的排序算法,常被用于实际应用中。
相关问题
python 列表快速排序
Python中的列表快速排序使用的是递归分治的思想,具体步骤如下:
1. 选取基准数(pivot),可以选择第一个数或者随机选取一个数。
2. 将比基准数小的数放在基准数左边,比基准数大的数放在右边,相同的数可以放在任意一边。这个过程称为partition。
3. 对左右两个子序列分别重复步骤1和2,直到每个子序列只有一个元素为止。
4. 最后将所有的子序列拼接起来就得到了排序后的序列。
以下是 Python 实现快速排序的代码:
```python
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums
left = [x for x in nums[1:] if x < pivot]
right = [x for x in nums[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
```
Python快速排序
Python快速排序是一种高效的排序算法,它采用分治的思想,将一个大问题分解成若干个小问题来解决。具体来说,快速排序的实现过程如下:
1. 选择一个基准元素(通常是列表的第一个元素);
2. 将列表中小于基准元素的元素放在基准元素的左边,大于基准元素的元素放在基准元素的右边;
3. 对基准元素左右两边的子列表分别递归执行步骤1和步骤2,直到子列表的长度为1或0。
Python快速排序的时间复杂度为O(nlogn),是一种非常高效的排序算法。在实现快速排序时,需要传入待排序列表以及排序的开始索引和结束索引,以便对部分数据进行排序。