python 快速排序

　　原理

　　快速排序使用分治法(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/