分治法将一个难以直接解决的大问题划分成一些规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。

1.概述

1.1设计思想

1. 大问题划分成一些规模较小的子问题，以便各个击破，分而治之
2. 最好使子问题的规模大小相等
3. 最好使各子问题之间相互独立。如果子问题不独立，分治法需要重复的求解公共的子问题，此时虽然也可以用分治法，但一般用动态规划法较好

1.2求解过程

1. 划分：即分治，划分为小问题
2. 求解子问题：一般用递归的方法求解各个子问题，有时递归也可以用循环来实现
3. 合并：把各个子问题的解合并起来

2.递归

分治与递归就像一对孪生兄弟

递归：就是子程序（或函数）直接调用自己或者通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法

递归通常用来解决结构自相似的问题。

递归有两个基本要素：

1. 边界条件：确定递归到何时终止，也称为递归出口
2. 递归模式：大问题是如何分解为小问题的，也称为递归体

递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

3.排序问题中的分治法

3.1归并排序

二路归并的分治策略是：

• 划分：将待排序序列r1，r2……rn划分为两个长度相等的子序列r1，……rn/2和rn/2+1，……rn
• 求解子问题：分别对这两个子序列进行归并排序，得到两个有序子序列
• 合并：将这两个有序子序列合并成一个有序序列

1. 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/ - 中等 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/oddeven.go

3.2快速排序

归并排序是按照记录在序列中的位置对序列进行划分的，而快速排序是按照记录的值对序列进行划分的。

快速排序的分治策略是：

• 划分：选定一个记录作为轴值，以轴值为基准将序列划分为两个子序列r1，……，ri-1和ri+1，……，rn，轴值的位置i在划分的过程中确定，前子序列都小于等于轴值，后子序列都大于等于轴值
• 求解子问题：分别对划分后的每一个子序列递归处理
• 合并：因为子序列的排序是在当前数组中，所以合并不需要执行任何操作

注意，轴值不需要选定，核心在于划分出两个子序列，前子序列都小于等于某个值，后子序列都大于等于某个值

1. 面试题 16.16. 部分排序https://leetcode-cn.com/problems/sub-sort-lcci/ - 中等 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/subsort.go 使用快速排序超时，然后使用另一种算法完美解决

4.组合问题中的分治法

4.1最大子段和问题

给定由n个整数（可能有负数）组成的序列(a1,a2,……,an)，最大子段和问题要求该序列某个区间范围之内和最大，当所有整数均为负整数时，其最大字段和为0。如(-20,11,-4,13,-5,2)，最大子段和为11-4+13=20

用分治策略求解最大子段和：

• 划分：按照平衡子问题原则，将序列(a1,a2,……,an)划分成长度相同的两个子序列(a1,……,a[n/2])和(a[n/2+1],……,an)，会有三种情况
• a1,a2,……,an的最大字段和等于a1,……,a[n/2]的最大子段和
• a1,a2,……,an的最大字段和等于a[n/2+1],……,an的最大子段和
• a1,a2,……,an的最大字段和等于ai+……+aj, 1<=i<=2/n，n/2+1<=j<=n
• 求解子问题：对于划分中情况1和情况2可以递归求解，情况3需要分别计算s1=max(a1+……+a[n/2])，s2=max(a[n/2+1]+……+a[n])，则s1+s2为情况3的最大子段和
• 合并：比较在划分阶段的三种情况下的最大子段和，取三者中较大者为原问题的解

这种类型的题，能考虑使用分治法，感觉已经领悟了分治的核心：划分-求解子问题-合并。蛮力法做差不多是O(n^2)，分治法时间复杂度O(nlog2n)。

另外感觉这种题目，可能使用动态规划效果会更好一些。

1. 53. 最大子序和 https://leetcode-cn.com/problems/maximum-subarray/- 简单 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/maximumsubarray.go

4.2棋盘覆盖问题

在一个2^k*2^k个方格组成的棋盘，恰有一个方格和其他方格不同，称该方格为特殊方格。棋盘覆盖问题要求用图4.11(b)所示的4种不同形状的L型骨牌股改给定棋盘上除特殊方格以外的所有方格，且任何两个L型骨牌不得重复覆盖。

使用分治法求解这个问题的技巧在于如何划分棋盘，使划分后的子棋盘大小相同，并且每个子棋盘都包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。

我当时在思考这个题的时候，已经发现可以用L骨牌覆盖较小棋盘汇合处，但是不知道怎么处理才能使程序更加简单。作者提供的思路：将汇合处设置为特殊方格，不但使递归的操作完全相同，而且很容易标记骨牌形状。

分治法在划分-求解子问题-合并这三个方面还是有很多技巧的。

在乐扣上没有找到这样的题目，可能是因为说明和判断都过于困难，但是我找到了一道相似而且容易一些的题目，就拿这道题练手吧。

1. 240. 搜索二维矩阵 IIhttps://leetcode-cn.com/problems/search-a-2d-matrix-ii/ - 中等 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/searchMatrix.go

4.3循环赛日程安排问题

设有n=2^k个选手进行网球循环赛，要求设计一个满足以下要求的比赛日程表：

(1)每个选手必须与其他n-1个选手各赛一次

(2)每个选手一天只能赛一次

可以将比赛日程表设计为一个n行n-1列的二维表，行代表选手，列代表第几天。

这个问题的解法是执行递归分割，最终分割为只有两个人的小方块，安排两个人的日程。我们以上图c为例讲解，最左上角为1号2号选手，其对应的右下角方位为左上角完全拷贝，左下角为3号和4号选手，右上角为完全拷贝。

算法核心是先确定了一个比赛日程规则，前半程比赛完了后，人员参加后半程比赛。

此处有两个点要说明一下

• 第0列没什么意义，主要是为了二维表能够对称
• 该算法的一个前提是有2^k个选手

在乐扣上找了一下对应的算法题，感觉应该是下面这道，但是没有充会员，看不了，如果有哪位同学有这道题内容的话，可以提供一下。

1. 输出比赛匹配对https://leetcode-cn.com/problems/output-contest-matches/ - 中等

5.几何问题中的分治法

5.1最近对问题

设p1=(x1,y1)，p2=(x2,y2)，……，pn=(xn,yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。严格地讲，最接近点对可能多余一对，简单起见，只找出其中的一对作为问题的解。

先考虑一维情况。此时S中的点退化为x轴上的n个点x1,x2,……,xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数相同。递归地在S1和S2上求出最接近点对(p1,p2)和(q1,q2)，如果集合S中的最接近点对都在子集S1或S2中，则d=min{(p1,p2),(q1,q2)}即为所求，如果集合S中的最接近点对都在子集S1或S2中，则一定是(p3,q3)，其中p3是子集S1的最大值，q3是子集S2的最小值。

m选取一般采用集合S的中值，可以分割得比较平衡一些。

对于二维情况，思路也类似。

递归求出S1和S2的最小距离为d后，则S1和S2之前的最小距离必然位于P1和P2之间。

如果p的位置确定，则S2中与p距离小于d的点位于以p为圆心，以d为半径的圆中。为了便于计算，符合条件的点最多位于d*2d区域范围内。而且因为S1和S2的最小距离为d，所以这个区域内，这种点不会超过6个。如下图所示：

没有找到二维的题目，一维的题目找到一个，使用该题目进行验证

1. 1200. 最小绝对差https://leetcode-cn.com/problems/minimum-absolute-difference/ - 简单 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/minimumabsolutedifference.go

5.2凸包问题

用分治法解决凸包问题的方法和快速排序类似，这个方法称为快包。

设p1=(x1,y1),p2=(x2,y2),……,pn=(xn,yn)是平面上n个点构成的集合S，并且这些点按照x轴坐标升序排列。几何学中有这样一个明显的事实：最左边的点p1和最右边的点pn一定是该集合的凸包顶点。p1pn连成的直线把S分为两个子集S1和S2。

首先找到S1中的顶点pmax，它是距离直线p1pn最远的订单，则三角形pmaxp1p2的面积最大。S1中所有在直线pmaxp1左侧的点构成集合S1-1，S1中所有在直线pmaxpn右侧的点构成了集合S1-2，包含在三角形pmaxp1pn之考虑了。递归处理集合S1-1和S1-2，将求解过程中得到的所有最远距离的点连接起来，就可以得到集合S1的凸包。同理可以求S2的凸包。

如何判断一个点是否在给定直线的左侧还是右侧呢？

|x1 y1 1|

|x2 y2 1| = x1y2+x3y1+x2y3-x3y2-x2y1-x1y3

|x3 y3 1|

当且仅当点p3=(x3,y3)位于直线p1p2左侧时，该式的符号为正。

在乐扣上没有凸包的习题，所以这个就先不做了。

使用二分法求解凸包问题，还是需要我们有一定的几何知识和观察能力的，能够判断出凸包顶点有哪些特征，也需要能够快速判定点位于直线哪一侧，只有这两个问题解决了，该算法才能比较好的实现。

总结

分治法能够极大的提高算法速度，而且分治法和迭代几乎是孪生关系。

使用分治法，需要完全领悟划分-求解子问题-合并的核心。推导出递归时需要设定的边界条件和迭代模式。

这里面比较重要的类型有

排序问题：归并排序、快速排序

组合问题：最大子段和问题、棋盘覆盖问题、循环赛日程安排问题

几何问题：最近对问题、凸包问题

归并排序、快速排序、最大子段和问题、棋盘覆盖问题建议自己尝试一下，因为排序算法是必须要练习的，最大子段和问题涉及到子问题有关联，棋盘覆盖问题涉及到二维数组。

最后

大家如果喜欢我的文章，可以关注我的公众号（程序员麻辣烫）

往期文章回顾：

算法

1. 算法学习计划
2. 蛮力法

技术

1. 浅谈微服务
2. TCP性能优化
3. 限流实现1
4. Redis实现分布式锁
5. Golang源码BUG追查
6. 事务原子性、一致性、持久性的实现原理
7. CDN请求过程详解
8. 记博客服务被压垮的历程
9. 常用缓存技巧
10. 如何高效对接第三方支付
11. Gin框架简洁版
12. InnoDB锁与事务简析

读书笔记

1. 敏捷革命
2. 如何锻炼自己的记忆力
3. 简单的逻辑学-读后感
4. 热风-读后感
5. 论语-读后感

思考

1. 对项目管理的一些看法
2. 对产品经理的一些思考
3. 关于程序员职业发展的思考
4. 关于代码review的思考
5. Markdown编辑器推荐-typora