第四章 快速排序
1 分而治之（divided and conquer,D＆C）
第一个?：如何将一块地均匀地分成方块，并确保分出的方块是最大的呢？
使用D&C策略（并非解决问题的算法，而是一种解决问题的思路）！D&C解决问题的两个步骤：
①找出基线条件，尽可能的简单
②不断讲问题分界，或者说缩小规模，使其满足基线条件
首先基线条件：一个条边的长度是另一条边的两倍。50m*25m
再找递归条件，这就要用到D＆C策略了，先找出可容纳的最大方块，对余下方块使用同样的算法。
你可以从这块地中划出两个640 m×640 m的方块，同时余下一小块地640m*400m，适用于这小块地的最大方块，也是适用于整块地的最大方块（涉及欧几里得算法）。对这块地实用同样的办法，变成400m*240m,然后变为240m*160m,最后变为160m*80,达到了基线条件。
第二个?：给定一个数字数组。
用循环很容易完成：
def sum(arr): total = 0 for x in arr: total += x return totalprint(sum([1, 2, 3, 4]))
递归如何处理？
①找出基线条件：如果数组中只有一个数或者没有数，那么加总很好算
②每次递归调用都必须离空数组更近一步。
两者之间是等效的，但是右边的数组更短，缩小了问题的规模。
sum()函数的递归运行过程：
提示：编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。
练习
4.1 请编写前述 sum 函数的代码。
def sum(list): if list == []: return 0 return list[0] + sum(list[1:])print(sum([1,2,3,4,5,6,7]))
4.2 编写一个递归函数来计算列表包含的元素数。
def sum(list): if list == []: return 0 return list[0] + sum(list[1:])print(sum([1,2,3,4,5,6,7]))
4.3 找出列表中最大的数字。
def max(list): if len(list) == 2: return list[0] if list[0] > list[1] else list[1] sub_max = max(list[1:]) #这里如果list很大，栈的空间就会很大，因为max()函数一直在运行，只到list被切分成长度为2 return list[0] if list[0] > sub_max else sub_maxprint(max([1,2,3,4,5,6,7,8,9]))
基线条件：数组只包含一个元素。
递归条件：把数组分成两半，将其中一半丢弃，并对另一半执行二分查找。
2 快速排序
基线条件：数组为空或者只有一个元素，这样就不需要排序了
两个元素的数组进行元素比较即可。三个元素呢？
快速排序的工作原理：
①从数组中选择一个元素，这个元素被称为基准值（pivot）
②找出比基准值小的元素以及比基准值大的元素，这被称为分区（partitioning），数组变为：
一个由所有小于基准值的数字组成的数组；基准值；一个由所有大于基准值的数组组成的子数组。
现在要对子数组进行排序，对于包含两个元素的数组（左边的子数组）以及空数组（右边的子数组），快速排序知道如何将它们排序，因此只要对这两个子数组进行快速排序，再合并结果，就能得到一个有序数组！
对三个元素的数组进行排序：
①选择基准值。
②将数组分成两个子数组：小于基准值的元素和大于基准值的元素。
③对这两个子数组进行快速排序。
包含四个元素呢？同样的做法，找出一个基准值，如果一个子数组有三个元素，对三个元素递归调用快速排序。那么五个元素同样也可以。
代码表示：
def quicksort(array): if len(array) < 2: return array else: pivot = array[0] #将数组的第一个元素定为基准线 less = [i for i in array[1:] if i <= pivot] #遍历数组剩下元素，如果小于它，放入less列表 greater = [i for i in array[1:] if i > pivot] #遍历数组剩下元素，如果大于它，放入greater列表 return quicksort(less) + [pivot] + quicksort(greater) #对less和greater递归，最后返回排序数组print quicksort([10, 5, 2, 3])
3 再谈大O表示法
快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n 2 )。
与选择排序一样慢！但这是最糟情况。在平均情况下，快速排序的运行时间为O(n log n)。
比较合并排序和快速排序：
有时候，常量的影响可能很大，对快速查找和合并查找来说就是如此。快速查找的常量比合并查找小，因此如果它们的运行时间都为O(n log n)，快速查找的速度将更快。实际上，快速查找的速度确实更快，因为相对于遇上最糟情况，它遇上平均情况的可能性要大得多。
4 平均情况和最糟情况
快速排序的性能高度依赖你选择的基准值。假设你总将第一个元素用作基准值，那么栈长为O(n)，如果你总将中间的元素用作基准值，那么栈长为O(log n)。
实际上，在调用栈的每层都涉及O(n)个元素。
因此，完成每层所需的时间都是O(n)
在第二张图中，层数为O(log n)（用技术术语说，调用栈的高度为O(log n)），每层需要的时间为O(n)。因此整个算法需要的时间为O(n) * O(log n) = O(n log n)。这就是最佳情况。在最糟情况下，有O(n)层，因此该算法的运行时间为O(n) * O(n) = O(n **2 )。
这里要告诉你的是，最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(n log n)。
练习
使用大O表示法时，下面各种操作都需要多长时间？4.5 打印数组中每个元素的值。O(n)
4.6 将数组中每个元素的值都乘以2。O(n)
4.7 只将数组中第一个元素的值乘以2。O(1)
4.8 根据数组包含的元素创建一个乘法表，即如果数组为[2, 3, 7, 8, 10]，首先将每个元素都乘以2，再将每个元素都乘以3，然后将每个元素都乘以7，以此类推。O(n**2 )。
5 小结D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n)快得多。