分而治之（divide and conquer，D&C）——一种著名的递归式问题解决方法。

D&C算法是递归的。使用D&C解决问题的过程包括两个步骤。

(1) 找出基线条件，这种条件必须尽可能简单。(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。

假设你有一块1680*640m的土地。你要将这块地均匀地分成方块，且分出的方块要尽可能大，应该怎样分？

你可以从这块地中划出两个640 m×640 m的方块，同时余下一小块地。

也就是：

现在是顿悟时刻：何不对余下的那一小块地使用相同的算法呢？最初要划分的土地尺寸为1680 m×640 m，而现在要划分的土地更小，为640 m×400 m。适用于这小块地的最大方块，也是适用于整块地的最大方块。换言之，你将均匀划分1680 m×640 m土地的问题，简化成了均匀划分640 m×400 m土地的问题！

下面再次使用同样的算法。对于640 m × 400 m的土地，可从中划出的最大方块为400 m × 400 m。这将余下一块更小的土地，其尺寸为400 m × 240 m。

你可从这块土地中划出最大的方块，余下一块更小的土地，其尺寸为240 m × 160 m。

接下来，从这块土地中划出最大的方块，余下一块更小的土地。

余下的这块土地满足基线条件，因为160是80的整数倍。将这块土地分成两个方块后，将不会余下任何土地！

因此，对于最初的那片土地，适用的最大方块为80 m× 80 m。

以上就是递归的分治法解决问题的思路。

问题2

再来看一个例子，数字数组各元素求和。如，数字数组[2,4,6]的求和。用一个循环很容易解决问题，但这里要用递归的分治法。

第一步：找出基线条件。最简单的数组什么样呢？如果数组不包含任何元素或只包含一个元素，计算总和将非常容易。因此这就是基线条件。

第二步：每次递归调用都必须离空数组更近一步。如何缩小问题的规模呢？下面是一种办法。

这与下面的版本等效。

这两个版本的结果都为12，但在第二个版本中，给函数sum传递的数组更短。换言之，这缩小了问题的规模！

函数sum的工作原理类似于下面这样。

这个函数的运行过程如下。

别忘了，递归记录了状态。

3 快速排序

对排序算法来说，最简单的数组什么样呢？就是根本不需要排序的数组。

因此，基线条件为数组为空或只包含一个元素。在这种情况下，只需原样返回数组——根本就不用排序。

def quicksort(array): if len(array) < 2: return array

我们来看看更长的数组。对包含两个元素的数组进行排序也很容易。

包含三个元素的数组呢？

别忘了，你要使用D&C，因此需要将数组分解，直到满足基线条件。下面介绍快速排序的工作原理。

首先，从数组中选择一个元素，这个元素被称为基准值（pivot）。我们暂时将数组的第一个元素用作基准值。

接下来，找出比基准值小的元素以及比基准值大的元素。

这被称为分区（partitioning）。现在你有：

I 一个由所有小于基准值的数字组成的子数组；

II 基准值；

III 一个由所有大于基准值的数组组成的子数组。

这里只是进行了分区，得到的两个子数组是无序的。但如果这两个数组是有序的，对整个数组进行排序将非常容易。

如果子数组是有序的，就可以像下面这样合并得到一个有序的数组：左边的数组 + 基准值 +右边的数组。在这里，就是[10, 15] + [33] + []，结果为有序数组[10, 15, 33]。

如何对子数组进行排序呢？对于包含两个元素的数组（左边的子数组）以及空数组（右边的子数组），快速排序知道如何将它们排序，因此只要对这两个子数组进行快速排序，再合并结果，就能得到一个有序数组！

quicksort([15, 10]) + [33] + quicksort([])> [10, 15, 33]

不管将哪个元素用作基准值，这都管用。假设你将15用作基准值。

这个子数组都只有一个元素，而你知道如何对这些数组进行排序。现在你就知道如何对包含三个元素的数组进行排序了，步骤如下。

(1) 选择基准值。

(2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。

(3) 对这两个子数组进行快速排序。

包含四个元素的数组呢？

假设你也将33用作基准值。

左边的子数组包含三个元素，而你知道如何对包含三个元素的数组进行排序：对其递归地调用快速排序。

因此你能够对包含四个元素的数组进行排序。如果能够对包含四个元素的数组进行排序，就能对包含五个元素的数组进行排序。

根据选择的基准值，对这个数组进行分区的各种可能方式如下。

将任何元素用作基准值都可行，因此你能够对包含五个元素的数组进行排序。同理，你能够对包含六个元素的数组进行排序，以此类推。

下面是快速排序的代码：

附代码：

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]))

参考： Aditya Bhargava巴尔加瓦著（袁国忠译）的《算法图解-像小说一样有趣的算法入门书》

－End－