快速排序是对冒泡排序的一种改进，由C. A. R. Hoare在1960年提出。它采用了“分治法”的策略来进行排序。

快速排序基本思想：

1、从数列中选取一个基准数p

2、小于等于p的放到它的左边，大于p的放到它的右边

3、对被分割开的左右两部分重复以上步骤，直到左右两部分中都只有一个元素

算法实现：

import random

def quicksort(lists):
    if len(lists) < 2:
        return lists        #左右两部分完成排序后结束递归
    else:
        pivot = lists[0]    #选择列表第一个数作为基准值
        left = [i for i in lists[1:] if i <= pivot]      #把小于等于基准值的数换到其左边
        right = [j for j in lists[1:] if j > pivot]      #把大于基准值的数换到其右边
        return quicksort(left)+[pivot]+quicksort(right)  #返回排序完毕的列表

if __name__=="__main__":
    lists= [2,5,4,1,6,7,4,9,1]
    random.shuffle(lists)      #打乱列表，防止出现极端情况
    print(lists)               #输出排序前列表
    print(quicksort(lists))    #输出排序后列表

输出示例：

[4, 7, 1, 5, 2, 9, 6, 1, 4]
[1, 1, 2, 4, 4, 5, 6, 7, 9]

快速排序时间复杂度：

最优情况：每一次的p都能恰好平分数组，此时时间复杂度为O(nlogn)

最差情况：每一次的p都刚好是最大或最小的数，此时时间复杂度为 O(n^2)

平均情况：时间复杂度为O(nlogn)