分而治之
快速排序——一种常用的优雅的排序算法。快速排序使用分而治之的策略。
分而治之 （divide and conquer，D&C）——一种著名的递归式问题解决方法。
如何将一块地均匀地分成方块，并确保分出的方块是最大的呢？使用D&C策略。
使用D&C解决问题的过程包括两个步骤。
(1) 找出基线条件，这种条件必须尽可能简单。
(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。
思考
给定一个数字数组。你需要将这些数字相加，并返回结果。使用循环很容易完成这种任务。但如何使用递归函数来完成这种任务呢？
第一步 ：找出基线条件。
最简单的数组什么样呢？请想想这个问题，再接着往下读。
如果数组不包含任何元素或只包含一个元素，计算总和将非常容易。
第二步 ：每次递归调用都必须离空数组更近一步。
如何缩小问题的规模呢？
快速排序
你要使用D&C，因此需要将数组分解，直到满足基线条件。下面介绍快速排序的工作原理。首先，从数组中选择一个元素，这个元素被称为基准值 （pivot）。
接下来，找出比基准值小的元素以及比基准值大的元素。这被称为分区 （partitioning）
一个由所有小于基准值的数字组成的子数组；
一个由所有大于基准值的数组组成的子数组。
步骤如下:
(1) 选择基准值。
(2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。
(3) 对这两个子数组进行快速排序。
下面是快速排序的代码。
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)
