温馨提示×

python实现快速排序的示例(二分法思想)

小云
97
2023-08-17 13:58:40
栏目: 编程语言

下面是一个使用递归方法实现快速排序的示例代码:

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, 9, 1, 8, 6, 3, 7, 4]
sorted_arr = quick_sort(arr)
print(sorted_arr)

输出结果为:[1, 2, 3, 4, 5, 6, 7, 8, 9]

在快速排序中,通过选择一个元素作为基准(pivot),将数组分为两个子数组,一个子数组中的元素小于等于基准,另一个子数组中的元素大于基准。然后对这两个子数组进行递归排序,最终得到排序后的数组。

在示例代码中,选择第一个元素作为基准,然后使用列表解析将小于等于基准的元素放入less列表,将大于基准的元素放入greater列表。最后递归对lessgreater进行快速排序,并将结果与基准元素合并返回。

0