快速排序

快速排序算法使用了分治思想。分治是说如果一个比较难的问题不好解决，我们可以尝试把它分解成若干个简单的同类子问题，依次求解各个子问题，再将子问题的解组合起来得到原问题的解。
快排的思想是：

1. 在数据集中找一个元素作为基准值 (pivot), 一般取第一个就行
2. 所有比基准值小的元素放到基准值的左边，大于等于基准值的元素放到基准值的右边
3. 对左右子集重复上面两部操作，直到数据集为空或数据集中只剩下一个元素
   如对 6, 2, 8, 3, 12, 7 进行排序
   第一步以 6 作为基准值，分出左右2个子集
   [2, 3] [6] [8, 12, 7]
   左右子集递归操作
   [] [2] [3] [6] [7] [8] [12]
   合并结果集
   2 3 6 7 8 12

def quick_sort(l):
    if len(l) <= 1:  # 基线条件：空数组或只有一个元素的数组本来就有序直接返回
        return l

    pivot = l[0]  # 取第一个元素为基准值
    left = [x for x in l[1:] if x < pivot]  # 小于基准值的数放到左边
    right = [x for x in l[1:] if x >= pivot]  # 大于等于基准值的数放到右边

    # 对左右子集递归调用快速排序，最后将结果集拼接
    return quick_sort(left) + [pivot] + quick_sort(right)

l = [6, 2, 8, 3, 12, 7]
print(l)
l = quick_sort(l)
print(l)

递归必须有退出条件，这里退出条件就是空数组或只有一个元素的数组，这两种情况我们是知道怎么排序的，它们本来就有序。

快速排序是一种不稳定的排序算法
快速排序是最快的排序算法之一，算法平均时间复杂度是 O(nlog(n)), 最坏时间复杂度是 O(n^2)