wiki
什么是快速排序?
wiki百科的定义是:快速排序,又称划分交换排序,简称快排,一种排序算法。在平均状况下,排序n个项目
次比较。在最坏状况下则需要
次比较,但这种状况并不常见。事实上,快速排序通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上可以很有效率地达成。
步骤
快速排序步骤
快速排序使用分治法策略来把一个序列(list)分为两个子序列(sub-lists)。
举个?
比如有一个数组
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]
如果你对今天的内容还感兴趣的话,何不点个赞再走呢?
如果感兴趣到想赞赏我,就不要犹豫啦~