分而治之
原文链接：https://note.noxussj.top/?source=sifo
什么是分而治之？
在我们前面有学习过一系列数据结构、以及相关的一些算法，包含排序、搜索算法。而本次学习的分而治之它不是数据结构，也不是一种算法，而是算法设计中的一种方法，可以理解为是一种思想。我们可以利用这种思想去设计很多种算法。
分而治之是将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。主要分成三个部分，分别是 “分”、”递归解决”、”合”。
基础案例
场景一
归并排序
- 分：把数组从中间一分为二
- 解：递归地对两个子数组进行归并排序
- 合：合并有序子数组
首先它会把一个大的数组拆分成两个小的数组，再分别对每个小数组又进行拆分成两个小数组，以此类推，最后把单个元素的小数组全部进行合并并排序，最后组成一个大数组从而解决了问题。
归并排序是一个典型的分而治之思想的应用。
场景二
快速排序
- 分：选基准，按基准把数组分成两个子数组
- 解：递归地对两个子数组进行快速排序
- 合：对两个子数组进行合并
步骤如同归并排序类似。
场景三
二分搜索同样具备 “分”、”解”、”合” 的特性。
原文链接：https://note.noxussj.top/?source=sifo
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
