1. 分而治之
分而治之(divide and conquer，D&C)——一种著名的递归式问题解决方法。快速排就是一种使用D&C的排序算法。
1-1
1-2
1-3
1-4
1-5
这里重申一下D&C的工作原理：
(1) 找出简单的基线条件；
(2) 确定如何缩小问题的规模，使其符合基线条件。D&C并非可用于解决
问题的算法，而是一种解决问题的思路。
实例代码
# 用递归计算[2, 4, 6]
def sum1(list1):
if list1 == []:
return 0
return list1[0] + sum1(list1[1:])
print(sum1([2, 4, 6]))
# 用递归计算列表包含的元素数
def count1(list1):
if list1 == []:
return 0
return 1 + count(list1[1:])
#找出列表中最大数
def max_1(list):
if len(list) == 2: # 基线条件
return list[0] if list[0] > list[1] else list[1]
sub_max = max_1(list[1:])
return list[0] if list[0] > sub_max else sub_max
print(max_1([2, 3, 5, 7]))
# 注意 : 编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。
2.快速排序
快速排序是一种常用的排序算法，比选择排序快得多。例如，C语言标准库中的函数qsort实现的就是快速排序。快速排序也使用了D&C。
如何对包含三个元素的数组进行排序了，步骤如下。
(1) 选择基准值(pivot)。
(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)
print(quicksort([3, -1, 9, 7]))
3. 再谈大O表示法
快速排序的独特之处在于，其速度取决于选择的基准值。
在讨论快速排序的运行时间前，我们再来看看最常见的大O运行时间。
image.png
还有一种名为合并排序（merge sort）的排序算法，其运行时间为O(n log n)，比选择排序快得多！快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。与选择排序一样慢！但这是最糟情况。在平均情况下，快速排序的运行时间为O(n log n)。
你可能会有如下疑问:
- 这里说的最糟情况和平均情况是什么意思呢？
- 若快速排序在平均情况下的运行时间为O(n log n)，而合并排序的运行时间总是O(n log n)，为何不使用合并排序？它不是更快吗？
4. 比较合并排序和快速排序
4-1
这两个函数都迭代整个列表一次，因此它们的运行时间都为O(n)。你认为哪个函数的速度更快呢？
我认为print_items要快得多，因为它没有在每次打印元素前都暂停1秒钟。因此，虽然使用大O表示法表示时，这两个函数的速度相同，但实际上print_items的速度更快。
在大O表示法O(n)中，n实际上指的是这样的。
4-2
c是算法所需的固定时间量，被称为常量。
例如，print_ items所需的时间可能是10毫秒 *n，而print_items2所需的时间为1秒 * n。通常不考虑这个常量，因为如果两种算法的大O运行时间不同，这种常量将无关紧要。
就拿二分查找和简单查找来举例说明。假设这两种算法的运行时间包含如下常量。
4-3
你可能认为，简单查找的常量为10毫秒，而二分查找的常量为1秒，因此简单查找的速度要快得多。现在假设你要在包含40亿个元素的列表中查找，所需时间将如下。
4-4
正如你看到的，二分查找的速度还是快得多，常量根本没有什么影响。
但有时候，常量的影响可能很大，对快速查找和合并查找来说就是如此。快速查找的常量比合并查找小，因此如果它们的运行时间都为O(n log n)，快速查找的速度将更快。
实际上，快速查找的速度确实更快，因为相对于遇上最糟情况，它遇上平均情况的可能性要大得多。
此时你可能会问，何为平均情况，何为最糟情况呢？
5. 平均情况和最糟情况
5-1
5-2
- 因为你每次都将数组分成两半，所以不需要那么多递归调用。你很快就到达了基线条件，因此调用栈短得多。
- 第一个示例展示的是最糟情况，而第二个示例展示的是最佳情况。在最糟情况下，栈长为O(n)，而在最佳情况下，栈长为O(log n)。
小结
1. D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
2. 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
3. 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
4. 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n)
快得多。
