基本思想

规模较大的问题分解为规模较少的问题，较小的问题分解成更小的问题，直到容易解决为止

  • 对较小问题解决，是继续分解————递归方程
  • 直到容易解决为止(通常一个元素)，边界条件

可以无限变小直到自己会做为止。

分治步骤

  1. 分解：将原问题分解成规模较小的子问题
  • 原问题可以被分为多个子问题 P1,P2,…,PK
  • 子问题形式需要和原问题一致
  1. 解决：通过递归的方式解决子问题
  • P1,P2 独立解，以及 P1,P2 共同相关的解
  1. 合并，对子问题的解进行合并，形成原问题的解。

快速排序

分解

选择一个主元素 k，将原数组分解为两个子数组，小于主元素的所有元素组成了一个子数组，大于主元素的所有元素组成了另外一个子数组。
[<=k] [>k]

解决

对子数组进行递归调用解决

合并

通过上述步骤，对已完成原数组的排序，无需合并操作