最近准备去找工作,时隔几年又要把在学校时代压床底的算法掏出来吹吹灰尘了,真有种朝花夕拾的感觉…哈哈哈哈
毕竟如果面试要是写不出来,那真是太尴尬了。
写那么一波快速排序找找感觉2333
也许有人会问,我为啥把所有算法直接写在一起。
我就不!因为这样写好查啊…而且不想把自己的博文写得那么冗长。
开面见山,直奔主题。

运行环境 Runtime environment

1
2
3
操作系统: Windos10  
IDE: JetBrains Python 2018.2.4 x64
语言: Python 3.66

背景

快速排序是一种常用得排序算法,比选择排序快得多。
例如:C语言标准库得函数qsort的实现就是快速排序。
快速排序也使用了D&C。
其实我也有点郁闷,我都用了Python还折腾这个干嘛..
Python的sorted排序,用的是狂霸酷拽Dior的TimeSort算法。至于TimeSort算法有多牛逼,自己去百度吧。
Python有这个原生工具函数在,还要啥自行车啊。23333
但是,没办法嘛,面试官要问的咯。

步步实现 快速排序

对排序算法来说,最简单的数组是啥样的?那就是根本不需要排序的数组。
比如:空数组或只有一个元素的数组,这种还排个屁。
于是我先排除这种情况。

1
2
3
4
5
6
7
8
def quick_sort(tempArray):
'''
快速排序
:param tempArray: 需要被排序的数组
:return:
'''
if len(tempArray)<2: # 排除空数组和单元素数组
return tempArray

包含两个元素的数组,也不用多说了,比较一下大小互换一下位置就成,不赘述了。
如果包含多个元素,那就要加上递归操作来搞一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quick_sort(tempArray):
'''
快速排序
:param tempArray: 需要被排序的数组
:return:
'''
if len(tempArray)<2: # 排除空数组和单元素数组
return tempArray
else:
pivot = tempArray[0] # 取出数组第一个元素,作为基准值,进行递归操作
less = [i for i in tempArray[1:] if i <= pivot] # 小于等于基准值的元素塞到一起作为子数组
bigs = [i for i in tempArray[1:] if i > pivot] # 大于基准值的元素塞到一起作为子数组
return quick_sort(less)+[pivot]+quick_sort(bigs) # 我返回我自己,递归,拼接数组

if __name__ == '__main__':
print(quick_sort([5,2,6,7,8,38,9,45,4,7,9]))

运行结果如下:

1
[2, 4, 5, 6, 7, 7, 8, 9, 9, 38, 45]

上面的快速排序中使用的是列表头一个元素作为基准值,这是为了方便理解。
但是你会发现如果你要处理有序的数组,每一次都是用数组第一个元素来作为基准值,那么导致其中的一个子集始终是空集。
这样就白瞎了那么多次递归,调用栈的高度也是相当大的。
在这里,若总是将数值的中间值作为基准值,那么数组始终都能对半分,就可以减少递归的调用次数。
魔改一下上面的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from random import *
def quick_sort_2(tempArray):
'''
快速排序
:param tempArray: 需要被排序的数组
:return:
'''
if len(tempArray)<2: # 排除空数组和单元素数组
return tempArray
else:
pivot = choice(tempArray) # 随机选择一个元素,作为基准值,进行递归操作
less = [i for i in tempArray if i < pivot] # 小于基准值的元素塞到一起作为子数组
bigs = [i for i in tempArray if i > pivot] # 大于基准值的元素塞到一起作为子数组
return quick_sort_2(less)+[pivot]*tempArray.count(pivot)+quick_sort_2(bigs) # 我返回我自己,递归,拼接数组

if __name__ == '__main__':
print(quick_sort_2([5,2,6,7,8,38,9,45,4,7,9]))

运行结果如下:

1
[2, 4, 5, 6, 7, 7, 8, 9, 9, 38, 45]

总结

快速排序先要理解基准值是干什么用的。
实现快速排序时,随机选择元素作为基准值会更好些。