快速排序是一种常用的排序算法，比选择排序快得多。例如， C语言标准库中的函数qsort实现的就是快速排序。快速排序也使用了D&C。
下面来使用快速排序对数组进行排序。对排序算法来说，最简单的数组什么样呢？还记得前一节的“提示”吗？就是根本不需要排序的数组。
因此， 基线条件为数组为空或只包含一个元素。在这种情况下，只需原样返回数组——根本就不用排序。
def quicksort(array):
if len(array) < 2:
return array
我们来看看更长的数组。对包含两个元素的数组进行排序也很容易。
包含三个元素的数组呢？
别忘了， 你要使用D&C，因此需要将数组分解，直到满足基线条件。下面介绍快速排序的工作原理。首先，从数组中选择一个元素，这个元素被称为基准值（pivot）。
稍后再介绍如何选择合适的基准值。我们暂时将数组的第一个元素用作基准值。
接下来，找出比基准值小的元素以及比基准值大的元素。
这被称为分区（partitioning） 。现在你有：
一个由所有小于基准值的数字组成的子数组；
基准值；
一个由所有大于基准值的数组组成的子数组。
这里只是进行了分区，得到的两个子数组是无序的。但如果这两个数组是有序的，对整个数组进行排序将非常容易。
如果子数组是有序的，就可以像下面这样合并得到一个有序的数组：左边的数组 + 基准值 + 右边的数组。在这里，就是[10, 15] + [33] + []，结果为有序数组[10, 15, 33]。
如何对子数组进行排序呢？对于包含两个元素的数组（左边的子数组）以及空数组（右边的子数组），快速排序知道如何将它们排序，因此只要对这两个子数组进行快速排序，再合并结果，就能得到一个有序数组！
不管将哪个元素用作基准值，这都管用。假设你将15用作基准值。
这个子数组都只有一个元素，而你知道如何对这些数组进行排序。现在你就知道如何对包含三个元素的数组进行排序了，步骤如下。
- 选择基准值。
- 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。
- 对这两个子数组进行快速排序。
包含四个元素的数组呢？
假设你也将33用作基准值。
左边的子数组包含三个元素，而你知道如何对包含三个元素的数组进行排序：对其递归地调用快速排序。
因此你能够对包含四个元素的数组进行排序。如果能够对包含四个元素的数组进行排序，就能对包含五个元素的数组进行排序。为什么呢？假设有下面这样一个包含五个元素的数组。
根据选择的基准值，对这个数组进行分区的各种可能方式如下。
AMY: 第一个以1为基准的明显有问题 应该是 [][1][3524] 此处是一谬误
注意，这些子数组包含的元素数都在0～4内，而你已经知道如何使用快速排序对包含0～4个元素的数组进行排序！因此，不管如何选择基准值，你都可对划分得到的两个子数组递归地进行快速排序。
例如，假设你将3用作基准值，可对得到的子数组进行快速排序。
将子数组排序后，将它们合并，得到一个有序数组。即便你将5用作基准值，这也可行。
将任何元素用作基准值都可行，因此你能够对包含五个元素的数组进行排序。同理，你能够对包含六个元素的数组进行排序，以此类推。
归纳证明
刚才你大致见识了归纳证明！归纳证明是一种证明算法行之有效的方式，它分两步：基线条件和归纳条件。是不是有点似曾相识的感觉？
例如，假设我要证明我能爬到梯子的最上面。
递归条件是这样的：如果我站在一个横档上，就能将脚放到下一个横档上。换言之，如果我站在第二个横档上，就能爬到第三个横档。这就是归纳条件。而基线条件是这样的，即我已经站在第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子最顶端。
对于快速排序，可使用类似的推理。在基线条件中，我证明这种算法对空数组或包含一个元素的数组管用。
在归纳条件中，我证明如果快速排序对包含一个元素的数组管用，对包含两个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用，以此类推。因此，我可以说，快速排序对任何长度的数组都管用。这里不再深入讨论归纳证明，但它很有趣，并与D&C协同发挥作用。
下面是快速排序的代码。
def quicksort(arr):
if len(arr) < 2:
return arr
else :
pivot = arr[0]
less = [i for i in arr[1:] if i <= pivot]
greater = [i for i in arr[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([10,5,2,3,4,5,6,78])