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

D&C算法——快速排序。快速排序是一种排序算法，速度比第二章介绍的选择排序快得多。

1. 分而治之

假如你是一个农场主，有一小块土地，你要将这块土地均匀地分成方块，且分出的方块要尽可能大。

用D&C方法：1>找出基线条件，这种条件必须尽可能简单；2>不断将问题分解（或缩小规模），直到符合基线条件

找出基线条件，最容易处理的情况是，一条边的长度是另一条边的整数倍。

根据D&C的定义，每次递归调用都必须缩小问题的规模。我们首先找出这块地可容纳的最大方块。

那么，何不对余下的那一小块地使用相同的算法呢？

余下的土地满足基线条件，因为160是80的整数倍

因此，对于最初的土地，适用的最大方块为80m*80m

D&C并非可用于解决问题的算法，而是一种解决问题的思路

再看一个例子：

给定一个数组：【2 | 4 | 6】   要将这些数字相加，并返回结果

使用循环很容易：

def sum(arr):
    total = 0
    for x in arr:
        total = total + x
    return total
print(sum([1,2,3,4]))

运行：10

使用递归函数：

1> 找出基线条件：如果数组不包含任何元素或只包含一个元素，计算总和将非常容易

基线条件：[ ]          不包含任何元素 ==> 总和为0

                 [7]         只包含一个元素 ==> 总和为7

因此这就是基线条件

2> 每次递归调用都必须离空数组更进一步

递归记录了状态

既然使用循环可以轻松完成任务，为何还要使用递归呢？

Haskell等函数式编程语言没有循环！

练习：

·请编写前述sum函数的代码

def sum(list):
    if list == []:
        return 0
    else:
        return list[0] + sum(list[1:])
print(sum([2,4,6]))

运行：12

·编写一个递归函数来计算列表包含的元素数

def count(list):
    if list == []:
        return 0
    else:
        return 1+count(list[1:])
print(count([2,4,6]))

运行：3

2.快速排序

快速排序是一种常用的排序算法，比选择排序快得多。

使用快速排序对数组进行排序。对排序算法来说，最简单的数组就是不需要排序的数组。因此，基线条件为数组为空或只包含一个元素。在这种情况下，只需原样返回数组——根本不用排序,如下

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

更长点：

两个：[1 | 7]  检查第一个元素是否比第二个元素小，如果不比第二个小，就交换他们的位置。

三个：[33 | 15 | 10]  将数组分解，直到满足基线条件。

其解释如下

快速排序工作原理：

从数组中选择一个元素，这个元素被称为基准值。暂时将数组的第一个元素用作基准值，找出比基准值小的元素以及比基准值大的元素

这被称为分区，现在你有：

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

2> 基准值

3> 一个由所有大于基准值的数字组成的数组

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

如果子数组是有序的，就像下面这样合并得到一个有序数组：左边的数组+基准值+右边的数组

在这里就是[10,15]+[33]+[ ]，结果为[10,15,33]

如何对子数组进行排序？

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

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

-->[10, 15, 33]

不管将哪个元素用作基准值，这都管用

这个子数组都只有一个元素，而你知道如何对这些数组进行排序。

三个元素（15作基准值）：1> 选择基准值； 2> 将数组分成两个子数组：小于和大于基准值的元素； 3> 对这两个子数组进行快速排序

四个元素（33作基准值）：左边包含三个元素，对三个元素的数组进行排序，对其递归地调用快速排序

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

为什么呢？假设有一个包含五个元素的数组。

这些子数组包含的元素数都在0-4内，而你已经知道如何用快速排序对包含0-4个元素的数组进行排序！

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

* 归纳证明

这是一种证明算法行之有效的方式，他分两步：基线条件和归纳条件

递归条件：如果我站在一个横档上，就能将脚放到下一个横档上

归纳条件：如果我站在第二个横档上，就能爬到第三个横档

基线条件：我已经站在第一个横档上，通过每次爬一个横档，我就能爬到梯子最顶端

在基线条件中，我证明这种算法对空数组或包含一个元素的数组管用

在归纳条件中，我证明如果快速排序对包含一个元素管用，对包含两个元素的数组也管用；如果……两个……三个……以此类推。快速排序对任何长度的数组都管用

快速排序示例代码：

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

运行：

[2, 3, 5, 10]

3. 再谈大O表示法

快速排序的独特之处在于，其速度取决于选择的基准值

上述图表中的时间是基于每秒执行十次操作计算得到的。实际上，计算机每秒执行的操作数远不止十次

还有一种名为合并排序的排序算法，其运行时间为O（nlogn），此选择排序快得多！快速排序的情况比较棘手，在最糟情况下，其运行时间为O（n^2）

1> 比较合并排序和快速排序

有一个打印列表中每个元素的简单函数

1. def print_items(list):
2. for item in list:
3. print(item)

它迭代整个列表一次，因此运行时间为O（n）

现在对这个函数进行修改，使其在打印每个元素前都休眠1秒钟

from time import sleep
def print_item2(list):
    for item in list:
        sleep(1)
        print(item)

它在打印每个元素前都暂停1秒钟，假设你使用这两个函数来打印一个包含5个元素的列表：

[2 | 4 | 6 | 8 | 10]

print_item : 2 4 6 8 10

print_item2 : <休眠>   2<休眠>  4<休眠>  6<休眠>  8<休眠>  10

这两个函数都迭代整个列表一次，因此运行时间都为O（n）

但是print_item要快得多，因为它没有在每次打印前都暂停1秒钟

因此，虽然使用大O表示法表示时，这两个函数的速度相同，但实际上print_item的速度更快。在大O表示法中，n实际上指的是这样的：c是算法所需的固定时间量，被称为常量。例如print_item所需时间可能是10毫秒*n，而print_item2所需的时间为1秒*n

通常不考虑这个常量。因为如果两种算法的大O运行时间不同，这种常量无关紧要。举例：

简单查找：10毫秒*n            二分查找：1秒*logn

你可能认为，简单查找的常量为10毫秒，而二分查找的常量为1秒，因此简单查找的速度要快得多。现在假设你要在包含40亿个元素的列表中查找，所需时间将如下：

简单查找： 10毫秒*40亿 = 463天            二分查找： 1秒*32 = 32秒

二分查找的速度还是快得多，常量根本没有什么影响

但有时候，常量的影响可能很大，对快速查找和合并查找来说就是如此

快速查找的常量比合并查找小，因此如果他们的运行时间都为O（nlogn），快速查找的速度更快

实际上，快速查找的速度确实更快，因为相对于遇上最糟情况，它遇上平均情况的可能性要大很多。

2> 平均情况和最糟情况

快速排序的性能高度依赖于你选择的基准值

假设你总是将第一个元素用作基准值，且要处理的数组是有序的，由于快速排序算法不检查输入数组是否有序，因此它依然尝试对其进行排序

数组并没有被分成两半，相反，其中一个子数组始终为空，这导致调用栈非常长

现在假设你总是将中间元素用作基准值

第一个示例展示的是最糟情况，而第二个展示的是最佳情况

在最糟情况下，栈长为O（n），而在最佳情况下，栈长为O（logn）

* 现在来看看栈的第一层，你将一个元素用作基准值，并将其他的元素划分到两个子数组中。这涉及数组中的全部8个元素，因此该操作的时间为O（n）。在调用栈的第一层，涉及全部8个元素，但实际上，在调用栈的每层都涉及O(n)个元素。即使以不同的方式划分数组，每次也将涉及O(n)个元素

在这个示例中层数为O（logn）（调用栈的高度为O(logn)）,而每层需要的时间为O(n)。因此整个算法的运行时间为O(n)*O(logn)=O(nlogn)，这是最佳情况。最糟情况下为O(n)*O(n)=O(n^2)

最佳情况也是平均情况

只要每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(nlogn)。快速排序是最快的排序算法之一，也是D&C典范。

4. 小结

①D&C将问题逐步分解,使用D&C处理列表时,基线条件很可能是空数组或只包含一个元素的数组

②实现快速排序时，请随机的用作基准值的元素。快速排序的平均运行时间为O（nlogn）

③大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在

④比较简单查找和二分查找时,常量几乎无关紧要,因为列表很长时,O(logn)的速度比O(n)快得多