python 快速排序

原理

快速排序使用分治法(Divideandconquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

步骤

从数列中挑出一个元素，称为”基准”(pivot)，

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码

普通版

defquick_sort(list):

less=[]

pivotList=[]

more=[]

#递归出口

iflen(list)<=1:

returnlist

else:

#将第一个值做为基准

pivot=list[0]

foriinlist:

#将比急转小的值放到less数列

ifi

less.append(i)

#将比基准打的值放到more数列

elifi>pivot:

more.append(i)

#将和基准相同的值保存在基准数列

else:

pivotList.append(i)

#对less数列和more数列继续进行排序

less=quick_sort(less)

more=quick_sort(more)

returnless+pivotList+more

咳咳，下面这段代码出自《Pythoncookbook第二版》传说中的三行实现python快速排序。

defqsort(arr):

iflen(arr)<=1:

returnarr

else:

pivot=arr[0]

less=[xforxinarr[1:]ifx

greater=[xforxinarr[1:]ifx>=pivot]

returnqsort(less)+[pivot]+qsort(greater)

当然还有一行语法糖版本:

qs=lambdaxs:((len(xs)<=1and[xs])or[qs([xforxinxs[1:]ifx=xs[0]])])[0]

是不是感受到了Python的魅力?

以上内容为大家介绍了python快速排序，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注我们