D&C
divide and conquer
基线条件：最简单的情况
递归条件：以最快的速度缩小问题规模，使其符合基线条件
归纳证明
基线条件：最简单的情况，比如长度为0或1的数组
归纳条件：证明如果算法对长度为1的数组管用，那么对长度为2的数组也管用；如果对长度为2的数组管用，那么对长度为3的数组也管用；以此类推，证明算法对任意长度的数组都管用。
quicksort
1、处理长度为0或1的数组排序
直接返回数组
2、处理长度为2的数组
比较两个元素，如果第一个元素>第二个元素，交换两个元素位置
3、处理长度为3的数组
选择基准值，分区为两个数组，数组less存放<=基准值的元素；数组greeter存放>基准值的元素
因为数组只包含3个元素，选择1个作为基准值，剩余的元素分区成的两个数组长度肯定<=2，因为quicksort知道如何处理长度<=2的数组，所以可以分别对两个数组进行quicksort
4、处理长度为4的数组
同【3】。分区后的两个数组长度肯定<=3，此时quicksort知道如何处理长度<=3的数组
5、以此类推，证明快速排序算法可以处理任意长度的数组。
快速排序-基线条件
如果数组长度为0或1，直接返回数组
if len(array) < 2:
return array
快速排序-递归条件
基准值：选择数组任意元素为基准值，比如第一个元素
pivot = array[0]
分区：遍历数组中其它元素，<=基准值的元素放入数组less；>基准值的元素放入数组greeter
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
分别对两个数组进行快速排序
quicksort(less)
quicksort(greater)
将排序后的两个数组与基准值合并，即为预期的排序结果
return quicksort(less) + [pivot] + quicksort(greater)
快速排序-完整代码
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
