【算法图解】快速排序

分而治之

假如有一块长方形土地，要将土地均匀分成方块，而且方块要尽可能大，如何分呢？

D&C策略

1. 找出长方形地块的宽作为分割出正方形的边长，分割出正方形。
2. 剩下来不能分割的部分继续用第一步进行分割。
3. 直到能分割成全部正方形。
4. 返回结果，结束程序。

此问题中基线条件为一条边长度是另一条边的整数倍。

D&C原理

1. 找出简单的基线条件
2. 确定如何缩小问题规模，使其符合基线条件。

再来看一个问题，求2+4+6的和。

1. 找出基线条件。此问题的基线条件是数组中只包含一个数字，则计算容易许多。
2. 将sum([2,4,6])的第一个数拆分出来，变为2+sum([4,6])
3. 重复第二步，直到sum()中只有一个元素。
4. 在调用栈中返回结果。
5. 结束。

代码表现为：

def sum(x):
    if x == 2:
        return 2
    else:
        return x + sum(x - 2)
print sum(6)

快速排序

快速排序也运用了D&C，其原理如下：

1. 找出其中一个数，拿左右相邻数与这个数比较，把所有小于基准值的放到左边，大于基准值的放到右边。
2. 左边和右边同时重复第一步。
3. 直到数组长度为1
4. 调用栈返回值。
5. 结束程序。

代码表现如下：

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)
print quicksort([10,5,2,3])