分治算法

此前学习的递归设计方法，是针对规模大的问题拆成规模小的问题，并且规模大的问题和规模小的问题的解决办法相同。

分治算法与递归设计方法的不同之处就是，该规模较大的问题分解为多个不重叠的子问题，并将其称为“分而治之”
**
分治的三个步骤：

  1. 分解：将原问题分解为若干个规模较小、相互不重叠与原问题形式相同的子问题
  2. 解决：
    1. 若子问题规模较小且易于解决时候直接解出
    2. 否则递归地解决各个子问题
  3. 合并：将各个子问题的解个并未原问题的解

归并排序

问题分析

  • 分解：将排序数组分解为左右两个相等的不重叠的数组
  • 解决：递归
  • 合并：将两个已经有序的数组合并为一个有序的数组

image.png

代码实现