快速排序算法使用了分治思想。分治是说如果一个比较难的问题不好解决，我们可以尝试把它分解成若干个简单的同类子问题，依次求解各个子问题，再将子问题的解组合起来得到原问题的解。
快排的思想是：
- 在数据集中找一个元素作为基准值 (pivot), 一般取第一个就行
- 所有比基准值小的元素放到基准值的左边，大于等于基准值的元素放到基准值的右边
- 对左右子集重复上面两部操作，直到数据集为空或数据集中只剩下一个元素
如对 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)
