python 快速排序

发布时间:2022-05-09 09:54:55 人气:33 作者:多测师

  原理

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

  步骤

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

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

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

python 快速排序

  代码

  普通版

  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/


上一篇:python 归并排序
下一篇:Python 堆排序
返回列表
在线客服
联系方式

热线电话

17727591462

上班时间

周一到周五

二维码
线