1. 分治思想

分治思想是一种重要的问题解决方法，它将一个复杂的问题分解成多个相似的子问题来解决，然后将这些子问题的解合并 起来得到原问题的解。这个过程包括三个主要步骤：分解、解决和合并。

分解：将原问题划分为若干规模更小、彼此独立、互不重叠的子问题。子问题和原问题属于同一类问题，适用相同的求解逻辑；划分一般配合递归实现。

解决：递归处理各个子问题，持续缩小问题规模，直到子问题足够简单、能够直接给出答案（递归的基线条件）。

合并：按照预定规则，把所有子问题的解整合在一起，构造出原问题的最终解。这一步的复杂度随场景变化，部分算法中合并是开销最高的环节（如归并排序），也有一些场景合并十分简单。

图1为分治思想示意图。

图 1 分治思想示意图

图1展示了分治（Divide and Conque）思想的标准执行流程，整体划分为分、治、合并三个阶段：

1.分（Divide）

将规模较大、不易直接求解的原问题（父问题），分解为若干个结构与原问题同质、规模更小的独立子问题。

2. 治（Conquer）

递归或独立求解各个子问题：若子问题规模足够小，则直接求解；若仍较为复杂，则继续套用分治流程分解，最终得到每个子问题对应的解。

3. 合并（Combine）

将全部子问题的解按照预设规则进行整合，构造出原父问题的最终解。

2. 二分查找算法的分治思想

我们通过一个游戏来引入二分查找算法。

我心里想好一个 1～100 之间的整数，你来猜这个数字；我只会给出三种反馈：大了、小了、猜对了。

思考一下，第一轮你会猜那个数字？

如果我们随机去猜，运气好可以一次猜中，但更多可能要试很多次；其实还有一种更聪明的思路：我们可以借助每一轮猜数得到的反馈，持续缩小猜数范围。

例如，第一次我们猜区间中点 50：

要是反馈 “猜大了”，就直接说明目标数字一定落在 1～49，后半段全部可以舍弃；

要是反馈 “猜小了”，就说明目标数字在 51～100，前半段可以全部排除。

图 2二分查找示意图

通过一次猜测，我们就直接把目标数字的候选范围折一半。之后每一轮，我们都在剩下的新区间里，继续选取中间数猜测，重复这个过程，区间会持续折半收缩，直到找到目标。

图 3二分查找示意图

这种每次选取区间中点比对、根据判定结果保留有效区间、舍弃无效区间，不断将问题规模折半缩减的策略，就是二分查找算法。它本质上就是分治思想的典型应用：把一个大范围的查找问题，拆成两个更小范围的子问题，判断之后只保留包含解的那一个子问题继续求解。

二分查找算法是分治策略的典型特例，同样遵循分 → 治 → 合并的框架，但它有一个非常特殊的地方：每次拆分后只需要选择其中一个子问题继续求解，其余子问题直接舍弃，属于分治里的 取舍型分治。

2.递归法与分治思想

递归法与分治思想经常一起使用。递归法通常用于实现分治策略，通过将问题分解为更小的子问题并递归地解决它们来解决问题。分治思想则提供了一种将问题分解为更小、更容易解决的子问题的策略，使得递归法能够更有效地应用。

假如准备要编写一个计算自然数 n 阶乘的程序。在编写程序之前，我们先明确：自然数 n 的阶乘，是所有小于及等于该数的自然数的积。

例如自然数 6 的阶乘：

6! = 1 x 2 x 3  x 4 x 5 x 6 = 720

程序需求：给定一个自然数 n，计算 n!，并把结果输出到控制台。那我们该怎么用程序求解阶乘？

观察阶乘定义，我们能找到一个递推关系：n 的阶乘，等于 n 乘以 (n-1) 的阶乘。

而 (n-1)! 又可以继续拆成(n-1)* (n-2)，一路往下拆解：

以4!举例：

4! = 4 * (4-1)!

= 4 * (4-1) * (4-2)!

= 4 * (4-1) * (4-2) *1!

求4的阶乘采用上面的计算方法，进行三层分解即可。

第一层：4的阶乘分解为4与（4-1）阶乘的积；

第二层：（4-1）阶乘分解为（4-1）与(4-2)阶乘的积；

第三层：(4-2)阶乘分解为(4-2)与(4-3)阶乘的积，也就是(4-2)与1阶乘的积。

经过三层分解，将计算规模为4的阶乘分解为计算规模为1的阶乘，剩余的就是四则运算了。

这个层层拆解的过程，就是我们前面讲的分治思想的落地。

前面的二分查找属于取舍型分治：拆分出两个子问题，判断之后只保留包含解的那一个，丢掉另一个，不需要合并多个独立子结果。

而阶乘递归，是一条链式的分治：每次拆分只产生一个子问题，没有多个并行子分支，但是同样遵守分 → 治 → 合并的完整框架。它是分治里比较特殊的单链分治，和归并排序（后面会讲归并排序）同时处理左右两个子区间、再合并的多分支分治不一样。

理解了分治思想的递推关系，我们就可以设计算法、画出流程图。

图 4计算阶乘流程图

在图4流程图中，把计算n的阶乘封装到factorial(n)函数中，该方法计算传入参数n的阶乘，在方法内部对n的阶乘进行分解，当n=1时直接返回1，因为1的阶乘是1，反之，将n的阶乘分解为n与(n-1)阶乘的积，求（n-1）的阶乘，还是调用factorial(n-1)方法。

从图4可以看出，在factorial(n)函数内部又调用了factorial(n-1)函数，这种在方法内部又调用自身函数的结构称为递归结构，该方法也称为递归函数。

递归有递推和回归的意思，递推就是把复杂的任务不断分解，让问题规模越来越小，当问题规模小到能够直接解答时，递推就结束了。递推的结束预示着回归的开始，回归从递推结束时问题的解答开始回归，由最简问题的解答按照递推路径反方向获取整个问题的解答。

3.归并排序的分治思想

归并排序严格遵循分治思想：分、治、合并三个阶段全部完整执行。它把一个无序数组拆成左右两个独立子问题，两个子问题都要求解，最后再把两组子解合并组装，和我们前面讲的 取舍型分治（二分查找）和单链式分治（阶乘递归）有所区别。

假设给定一个无序整数数组，我们使用归并排序完成升序排序，整个过程严格按照分治的三个阶段进行。

分：切分问题

选取数组中点，把当前待排序数组切为左右两段，生成两个独立、规模减半的子数组。数组拆分会不断重复，每一拆分后的数组都继续对半切开，越切越小，直到碰到分治的边界条件。

治：解决子问题

当分解的数组仅包含一个元素时，单个元素天然有序，不需要任何排序操作，直接返回，这就是分治的最简出口，不能再继续拆分。

如果拆分后的数组还不止一个元素，就继续递归：先把左边排好，再把右边排好。这个向下递归的过程，就是分治思想的治：独立解决每一个子数组的排序任务。等到左、右两段各自全部有序，子问题就求解完毕。

合并：组装子解

当左右两个子数组各自完成排序、都成为有序子数组之后，就进入分治的最后一环 —— 组装子解。

我们手里现在是两段独立、有序的子数组，不需要再对全部元素重新乱序比较。我们用两个指针，分别从这两个有序子数组的开头开始比对，每次挑选更小的元素，放到新数组里。一直重复挑选，直到其中一个子数组全部取完；再把另一个子数组剩下的元素直接接在后面，最终拼成一个更长的有序数组。这个新得到的有序数组，就是当前这一层原问题的解。

图 5归并排序示意图

图5为数组[38,27,43,3,9,82,10]的归并排序过程示意图，完整展示了[分 —治 —合并]的分治执行流程。

首先看蓝色箭头。归并排序会不断选取中点，把当前数组切分成左右两个更小的子数组。这个过程会一直重复，数组越拆越小，直到每个子数组里只剩下一个元素。

再看绿色叶子。当数组只有一个元素时，它已经天然有序，不需要再拆分，也不需要额外排序，直接返回即可，这就是递归的出口。

最后看橙色箭头。开始回溯合并：左右两个子数组已经各自有序，我们只需要分别从它们的开头比较，每次取出更小的元素，放入新数组。其中一个子数组取完后，再把另一个子数组剩余的元素直接接在后面。

合并会沿着递归树逐层向上进行，小的有序数组合并成更大的有序数组，最后得到整个问题的解：[3, 9, 10, 27, 38, 43, 82]。

所以，归并排序的关键不是一开始就全局排序，而是先拆到最简，再把局部有序的结果逐层组装起来。

4.汉诺塔问题

问题描述

汉诺塔（Tower of Hanoi）问题是一个古老的数学难题，也是应用分治思想的经典递归案例。问题起源于一个古老的传说：有三根柱子，其中一根柱子上自上而下按大小顺序摞着 n 个不同大小的圆盘，目标是将这些圆盘移动到另外一根柱子上，并满足以下规则：

（1）一次只能移动一个圆盘。

（2）大的圆盘不能叠放在小的圆盘之上。

（3）可以使用第三根柱子作为辅助。

解题步骤

解决汉诺塔问题的关键在于理解和应用递归和分治思想。基本的思路是，为了将n个圆盘从起始柱子移动到目标柱子，我们需要先将n-1个较小的圆盘从起始柱子移动到辅助柱子（这本身就是一个汉诺塔问题，但规模较小），然后将最大的圆盘从起始柱子移动到目标柱子，最后再将n-1个圆盘从辅助柱子移动到目标柱子。

图 6 汉诺塔移动示意图

当汉诺塔问题的规模 n 为 3 时，意味着有三根柱子（通常命名为 A、B、C），并且柱子 A 上摞着三个按大小顺序排列的圆盘。目标是将这三个圆盘按照规则移动到柱子 C 上。利用分治思路，我们把该任务拆分为三部分完成：

第一部分：解决子问题，将上方 2 个圆盘从起始柱 A 移动到辅助柱 B：

将最小的圆盘（圆盘1）从柱子A移动到柱子C。

将第二小的圆盘（圆盘2）从柱子A移动到柱子B。

将最小的圆盘（圆盘1）从柱子C移动到柱子B，此时辅助柱子B上有两个圆盘，且圆盘1在圆盘2上面。

第二部分：执行简单操作，移动最大圆盘：

将最大的圆盘（圆盘3）从柱子A移动到柱子C。

第三部分：解决第二个子问题，将辅助柱 B 上的 2 个圆盘移动到目标柱 C：

将最小的圆盘（圆盘1）从柱子B移动到柱子A。

将第二小的圆盘（圆盘2）从柱子B移动到柱子C。

将最小的圆盘（圆盘1）从柱子A移动到柱子C，此时目标柱子C上有三个圆盘，且按大小顺序排列。

整个过程反复把搬运多个圆盘的复杂任务拆成更小的同类子任务，直到子问题简化为只移动单个圆盘，再依次组合各子任务的结果，汉诺塔问题的求解完整体现了分治思想的应用。