Python算法：快速排序

最近准备去找工作，时隔几年又要把在学校时代压床底的算法掏出来吹吹灰尘了，真有种朝花夕拾的感觉…哈哈哈哈
毕竟如果面试要是写不出来，那真是太尴尬了。
写那么一波快速排序找找感觉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
但是，没办法嘛，面试官要问的咯。

步步实现快速排序

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

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

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

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]

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

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]))