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)