分治算法解决思路

分治算法

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

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

分治的三个步骤：

1. 分解：将原问题分解

1. 若干个规模较小、互相不重叠与与原问题形式相同的子问题

2. 合并：将各个子问题的解个并未原问题的解

1. 若子问题规模较小且易于解决时候直接解出
2. 否则递归地解决各个子问题

归并排序例子

问题分析

• 分解

• 将原数组分解为左右两个数组
• 分解至每个数组都只有一个元素

• 合并将两个有序数组合并为一个有序数组

• 合并算法则是比较两个数组的第一个元素大小，然后推到result数组中。
• 递归：如果数组都有多个元素，则重复上一个步骤

代码实现