• D&C将分体分解处理，对于列表来说base case通常是空列表或单元素列表
  • 实现快速排序时，请随机选择pivot，BigO = O(n*log(n))
  • BigO表示法有时常量作用很小（简单查找O(n*n)和二分查找O(logn)），但有时作用很大（如快排和合并排序，快排优于合并排序）

1. 分治法 D&C

Divide and Conquer，DC算法是递归的

  • 找出base case，条件尽量简单
  • recursive：不断将问题分解（缩小规模），直到符合base case

例1. 矩形分最大方形

  • base case（最简单的矩形）：一条边是另一条边的整数倍（l=25，w=50），那么最大的方块是25*25，可分出两个方块
  • recursive case：以小的边作为方块长度，找出最多的方块，之后剩余的那个矩形（因为不满足base case）再进行递归，实现缩小问题规模，判断是否符合基线条件

例2. 数组加和

Base case，即最简单的数组

  • 空数组，总和为0
  • 一个元素的数组，总和为元素本身

Recursive

  • 每次取出数组中一个数
  • 将结果改为该数 + 剩余数组的加和

2. 快速排序（例3）

C语言标准库中的快排是基于D&C实现的

归纳证明

归纳证明是一种证明算法有效性的方式，它分为两步：基线条件和归纳条件

举例：证明我能爬到梯子的最顶层

  • 基线条件：我已经站到第一个横档上
  • 递归条件：如果我能站在一个横档上，我就能将脚放到上一层横档上

结论：我能爬到最顶层

归纳证明与分治法协同发挥作用，得出了快速排序算法

快排的实现

Base case

  • 最简单的数组，即根本不需要排序的数组：空数组或就含有一个元素

Recursive case

  • 找到一个pivot（可以是数组中的一个数），将比pivot小的数归纳为一个数组放到左侧，将比pivot大的数归为一个数组放到右侧
  • 分别对左侧和右侧的数组进行快排
  • 如果新生成的数组满足base case则停止
  1. def quick_sort(arr):
  2.     if len(arr) < 2:
  3.         return arr
  4.     else:
  5.         pivot = arr[0]
  6.         less_arr = [x for x in arr if x < pivot]
  7.         greater_arr = [x for x in arr if x > pivot]
  8.         return quick_sort(less_arr) + [pivot] + quick_sort(greater_arr)

3. BigO

快速排序前是没有检测数组是否有序，因此，如果数组有序，快排还是会重复一遍递归

如果选用第一个元素作为pivot，那么会产生快排的最糟情况，时间复杂度为O(n*n)

  • 因为每次选择最小元素，调用栈深度O(n)（调用栈表示递归过程中函数体和变量存储空间，每次递归外层函数体结束释放一层栈空间）
  • 每一层进行less和greater归并需要O(n)
  • 因此总BigO = O(n) * O(n)

最优情况（也是平均情况）

  • 栈深度为O(logn)，因为每次选择的元素是中间值（中位数为理想情况，相当于二分法 -> log(n)）
  • 每一层归纳 O(n)
  • BigO = O(n*log(n))

快排和合并排序

  • 其本质上都是O(n*log(n))
  • 但是快排的常量更小，所以快排的速度更快