章节内容
- 分而治之
- 快速排序
分而治之
分而治之(D&C)是一种著名的递归式问题解决方法。
使用D&C算法解决问题的过程包括两个步骤：
- 找出基线条件，这种条件必须尽可能简单
- 不断将问题分解(或者说缩小规模)，直到符合基线条件
示例一
问题：将一块1680*640的土地均匀分成方块，且分出的方块尽可能大。
使用D&C算法解决此问题包含两个步骤：
- 找出基线条件。最容易处理的情况是一条件的长度等于另一条边的整数倍。
- 找出递归条件。我们可以在这片土地上划出两个640640的方块，同时余下一小块地。递归对余下的小快地使用相同的做法。
第一次划分后余下640400的地，再划出400400后余下240400。再划出240240后余下240160；接下来划出160160后余下16080。
此时注意，余下的小块地已经符合基线条件，可以直接划分成两个8080的方块。因此，对于最初的那块地使用的最大方块是8080.
示例二
问题：将一个数组的全部元素相加，并返回结果
两个步骤：
- 找出基线条件。如果数组只有一个元素，则总和就是那个元素的值
- 递归条件。计算数组中除第一个元素外的其他元素的和，将其与第一个元素相加，并返回。
快速排序
快速排序是一种常用的排序算法，时间复杂度为O(nlogn)。C语言标准库中的函数qsort实现的就是快排。快排也是用了D&C思想。
使用D&C实现快排还是先完成两个步骤：
- 找出基线条件。对于一个数组为空或者只有一个元素，数组不需要排序，因此数组为空或只包含一个元素为基线条件。
def quickSort(arr):
if len(arr) < 2
return arr
- 找出递归条件。我们将数组第一个元素作为一个基准值，将数组分成比基准值小的区和比基准值大的区。
通过此过程数组被分成了三个部分：
[] 一个由所有小于基准值的数字组成的子数组
[] 基准值
[] 一个由所有大于基准值的数字组成的子数组
此时两个子数组是无序的。如果两个子数组有序，则排序也完成了。
再对两个子数组进行相同的操作，直至子数组只有一个元素则排序完成。
快排代码：
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, 7])
PS:
- 快排平均情况复杂度为O(nlogn)，最糟情况下为O(n^2)
- 快排遇上平均情况的可能性比遇上最糟情况的可能性大得多
- 快排和归并排序虽然时间复杂度都是O(nlogn)，但是快排的常量小于归并排序。
平均情况和最糟情况
快速排序的性能高度依赖于你选择的基准值。
假如你总是将第一个元素座位基准值，且要处理的数组是有序的。调用栈的高度是数组的长度，这是最遭情况。
假设你总将中间的元素作为基准值，调用栈的长度就是logn，这是最佳情况。
在这个实例中，层数为O(logn)，即调用栈的高度为O(logn)，而每层需要的时间为O(n)。因此整个算法需要的时间为O(n)* O(logn) = O(nlogn)
在最遭的情况下，有O(n)层，算法的运行时间为O(n)* O(n)= O(n2)
小结
- D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
- 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(nlogn)
- 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
- 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(logn)的速度比O(n)快得多。