发布时间:2022-05-09 09:54:55 人气:239 作者:多测师
原理
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
步骤
从数列中挑出一个元素,称为”基准”(pivot),
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码
普通版
def quick_sort(list):
less = []
pivotList = []
more = []
# 递归出口
if len(list) <= 1:
return list
else:
# 将第一个值做为基准
pivot = list[0]
for i in list:
# 将比急转小的值放到less数列
if i < pivot:
less.append(i)
# 将比基准打的值放到more数列
elif i > pivot:
more.append(i)
# 将和基准相同的值保存在基准数列
else:
pivotList.append(i)
# 对less数列和more数列继续进行排序
less = quick_sort(less)
more = quick_sort(more)
return less + pivotList + more
咳咳,下面这段代码出自《Python cookbook 第二版》传说中的三行实现python快速排序。
def qsort(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 qsort(less) + [pivot] + qsort(greater)
当然还有一行语法糖版本:
qs = lambda xs : ( (len(xs) <= 1 and [xs]) or [ qs( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + qs( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]
是不是感受到了Python的魅力?
以上内容为大家介绍了python 快速排序,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注多测师。https://www.e70w.com/xwzx/