浅尝Python快速排序

wiki

什么是快速排序？

wiki百科的定义是：快速排序，又称划分交换排序，简称快排，一种排序算法。在平均状况下，排序n个项目次比较。在最坏状况下则需要次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上可以很有效率地达成。

步骤

快速排序步骤

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

• 从数列中挑出一个元素，称为"基准"（pivot），

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

• 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

举个🌰

比如有一个数组

96 69 1314 520 666

1. 选取一个基准数就是之前说的privot，一个比较大小的数。

一般都会取最后一个数，这里就取666为基准数，依次把数组的数和666比较，比666小的放左边，比666大的放右边，这样有如下结果：

96 69 520 666 1314

2. 判断区间个数，经过第1步后右边区间只有一个数了，没有数字再和它比较了，因此不需要重复操作，左边区间还有：

96 69 520

3. 重复第1步，选取520作为基准数，得到比较结果：

96 69 520

4. 重复第1步，选取69作为基准数，得到比较结果：

69 96

5. 这样左右两边区间都只有一个数了，这就标志着排序完成，最后把所有区间合并就得到排序结果：

69 96 520 666 1314

Code

上代码！

def quick_sort(lst):
   _less = [] # 存储小于基准数的值
   _greater = [] # 存储大于基准数的值
   # 递归函数一定要有退出条件
   if len(lst) <= 1:
       return lst
   # 基准数，直接获取src的最后一个
   _pivot = lst.pop()
   for _item in lst:
       if _item <= _pivot:
           _less.append(_item)
       else:
           _greater.append(_item)
   # 这里用到了python的list是可以直接相加的特性
   # 递归思想很重要，去处理列表中不止1个的
   return quick_sort(_less) + [_pivot] + quick_sort(_greater)

代码中采用了递归的做法，优化的地方也是有的，比如用生成器去优化列表的值获取。

l = [69, 96, 520, 666, 1314]
print(quick_sort(l))
[69, 96, 520, 666, 1314]

如果你对今天的内容还感兴趣的话，何不点个赞再走呢？

如果感兴趣到想赞赏我，就不要犹豫啦～

---

目前我开了2个主群，我邀请了一些我的BAT伙伴前来助阵。定期也会在群里组织抽奖、送书等活动。更有各种资源分享。

目前2个主群都以过百，想要加入的小伙伴，可以加我微信，我拉你们，或者公众号后台回复关键“关注作者”。

另外：「高级群」已经升级啦！如果你错过了种子轮，难道还要错过天使轮吗？群内不定期组织红包接龙，每天中午1小时的随即话题讨论，没有广告，只聊技术、生活，这样的群上哪找？

推荐阅读：