分治法的基本思想如何写我教你。（精选5篇）

更新日期:2025-05-10 20:15

写作核心提示：

撰写关于分治法的基本思想的作文时，应注意以下事项：
1. 确定文章主题：明确作文的主题是关于分治法的基本思想，确保全文围绕这一主题展开。
2. 了解分治法：在写作前，要对分治法有充分的认识，包括其定义、原理、应用场景等，以便在作文中准确表达。
3. 结构清晰：分治法的基本思想作文应具备清晰的结构，一般包括引言、主体和结论三个部分。
4. 引入背景：在引言部分，简要介绍分治法的起源、发展及其在计算机科学领域的地位，引起读者的兴趣。
5. 解释基本思想：在主体部分，详细阐述分治法的基本思想，包括以下内容： a. 分而治之：将复杂问题分解为若干个相互独立、规模较小的子问题。 b. 求解子问题：递归求解子问题，直至子问题规模足够小，可以直接求解。 c. 合并结果：将子问题的解合并，得到原问题的解。
6. 举例说明：通过具体实例，展示分治法在实际问题中的应用，如快速排序、二分查找等，增强说服力。
7. 分析优点：论述分治法的优点，如时间复杂度低、空间复杂度小、易于实现等。
8. 讨论局限性：分析分治法的局限性，如递归调用可能导致栈

5分钟弄懂的五大常用算法之“分治法”，以C语言归并排序算法为例

分治算法，顾名思义就是“分而治之”，即把规模较大的复杂问题拆分为若干规模较小的类似子问题，并逐个解决，最后再将各个子问题的解决结果合并，得到原始问题的结果的方法。这个技巧是很多高效算法的基础，例如快速排序算法、归并排序算法、快速傅里叶变换等等。

五大常用算法之分治算法

分治算法的通俗理解

一般来说，规模小的问题比规模大的问题解决起来简单，例如数组排序问题，只有 2 个元素的数组处理起来要比有 2000 个元素的数组简单。这是分治算法的基本立足点，也是使用条件之一，总结一下就是，对于一个规模较大的问题，可以拆分成若干不相关的子问题，并且子问题解决起来更加简单。

分治算法在我们日常生活中无处不在，例如国家依次划分为省市县镇村来管理，本质上也是因为解决“子问题”（管理村）要简单许多。

有这样一个非常经典的问题：生产线生产了 99 个工件，其中 1 个工件是劣品，比其他 98 个工件质量轻一些，如果用天平称，至少多少次一定能找到这个劣品工件？

要解决这个问题，最简单粗暴的方法是逐个比较，如果第 x 个工件比第 y 个工件轻，第 x 个工件就是劣品。那么 99 个工件至少需要比较 50 次才能确保一定找到劣品。

逐个比较

能够发现，使用逐个比较的方法的时间开销与工件总数有关，如果工件总数很少，比如只有 2 个，那么只需要比较一次就可以找到劣品了。因此该问题满足使用“分治算法”的必要条件之一：规模较小的子问题解决起来更简单。现在尝试使用分治算法解决该问题：

1. 将 99 个工件等分为 3 份，每份 33 个工件；
2. 比较第 1、2 份，如果天平平衡，那么劣品必定在第 3 份中，否则劣品在轻的那一份中；
3. 将劣品所在的那一份再等分为 3 份，每份 11 个工件；
4. 重复第 2 步；
5. 将劣品所在那一份再分为 3 份，每份分别为 3、3、2 个工件；
6. 重复第 2 步；
7. 不管劣品所在那一份为 3 个工件还是 2 个工件，只需再比较一次，就可找到劣品。

可见，使用分治算法只需要比较 4 次就可以找到劣品，这远低于逐个比较法的 50 次。不过也应该注意到，使用分治法找劣品时，每次拆分子问题时，各个子问题是互不干扰的——例如其中一份的 33 个工件质量不会影响其他份的 33 个工件质量。

归并排序法

从前面这个简单的实例可以看出，分治法有时的确能够极大的提升解决问题的效率，事实上，在C语言程序开发中，许多优秀的算法本质上都是基于分治思想的，一个非常典型的例子就是归并排序法，它在处理数组排序时有着不错的效率。

在处理数组排序时，如果数组中只有 1 个元素，那么该数组本身就可看作是排好序的数组。如果数组中有 2 个元素，那么最多只需比较一次就可以得到排好序的数组。这其实是归并排序法的核心，也即规模越小的数组，对其排序越简单。下图是一个长度为 5 的数组，为了排序，先把它拆分到不能继续拆为止。

拆分到不能继续拆

显然，“拆分到不能继续拆”后，子问题已经变成了只有 1 个元素的数组，这样的数组已经是“排好序”的数组了。按照我们前面讨论的，现在需要做的就是把这些已经排好序的子数组合并，问题转化为：按照顺序合并有序数组，如下图所示：

按照顺序合并有序数组

归并排序的C语言实现

根据前面的分析，使用C语言实现归并排序法需要实现两个子模块：拆分和合并。拆分数组有多种方法，通常采用二等分法，设数组头的索引为 start，数组尾的索引为 end，mid=(start+end)/2，每次平均拆分，都会将数组分为 start 到 mid，和 mid+1 到 end 两个子数组，再对这两个子数组执行同样的拆分，一直到不能拆分为止。所谓“不能拆分”，其实就是数组中只有一个元素，也即 start 等于 end，这一过程非常适合使用递归实现。我们先确定递归的停止条件：

void pide(int *arr, int start, int end)
{
    if (start >= end)
        return;
}

否则，我们将继续拆分子数组（start, mid）和（mid+1, end），这一过程的C语言代码如下：

void pide(int *arr, int start, int end)
{
    if (start >= end)
    return;
    int mid = (start+end)/2;
    pide(arr, start, mid);
    pide(arr, mid+1, end);
}

关于 pide() 递归函数的理解，我之前的这篇文章详细讨论过。

搞定拆分模块后，再来看看合并模块。按照前面讨论的，拆分到“不能拆为止”的都可认为是已经排好序的子数组，所以合并模块要按照顺序（本例从小到大）将子数组合并：

int merge(int *arr, int start, int mid, int end)
{
    int ln = mid-start +1;
    int rn = end - mid;
    int left, right;
    
    for (int i=0; i<ln; i++) {
        left = arr;
    }
    for (int j=0; j<rn; j++) {
        right = arr;
    }
}

C语言代码1

我们先将要合并的拆分后的两个子数组分别保存在 left 和 right 数组里，应注意，这里使用了C语言的变长数组语法，因此在编译时要指定-std=c99选项。接着，我们逐个比较 left 和 right 中的元素，按照顺序填入 arr，这一过程的C语言代码如下所示：

int merge(int *arr, int start, int mid, int end)
{
...
    int i=0, j=0, k=0;
    for (k = start; i < ln && j < rn; ++k) {
        if (left < right) {
            arr = left;
            ++i;
        } else {
            arr = right;
            ++j;
        }
    }

C语言代码2

执行完毕后，left 和 right 中可能还有剩余元素，这些剩余元素必定是需要放在 arr 后部分的，因此C语言代码可以如下写：

int merge(int *arr, int start, int mid, int end)
{
...
    if (i < ln)
        for (; i < ln; i++) {
            arr = left;
            ++k;
        }
    if (j < rn)
        for (; j < rn; ++j) {
            arr = right;
            ++k;
        }
}

C语言代码3

到这里，merge() 函数就完成了，将之与 pide() 函数组合起来，也即：

void pide(int *arr, int start, int end)
{
    if (start >= end)
    return;
    int mid = (start+end)/2;
    pide(arr, start, mid);
    pide(arr, mid+1, end);

    merge(arr, start, mid, end);
}

C语言代码4

现在 pide() 函数便可对输入的数组 arr 排序了。

测试归并排序法

这里使用 8 个元素的数组做测试：

int main()
{
    int arr = {1, 3, 2, 5, 8, 7, 6, 4};

    pide(arr, 0, 7);
    for (int i=0; i<8; i++)
        printf("%d ", arr);
    printf("
");

    return 0;
}

C语言代码5

编译并执行这段C语言代码，得到如下输出：

# gcc t.c -std=c99
# ./a.out 
1 2 3 4 5 6 7 8

归并排序算法的时间复杂度

在计算过程中，累加和比较的过程是关键操作，一个长度为 n 的数组在递归的每一层都会进行 n 次操作，分治法的递归层级在 logN 级别，所以整体的时间复杂度是 O(nlogn)。

归并排序法是一个效率不错的排序算法，可能时间复杂度看起来不是特别直观，我们将之与简单粗暴的“冒泡排序算法”对比，在我的机器上分别对不同规模的数组排序，得到如下结果：

排序效率对比

冒泡排序算法是比较简单的算法，在处理规模较小的数组时和归并排序法的效率不相上下，但是在处理规模较大的数组时，冒泡排序算法的效率逐渐远离归并排序了，且数组的规模越大，二者的效率差异越大，在处理 100 万个数组元素时，归并排序算法仅消耗 230 毫秒就处理完毕了，而冒泡排序算法在执行 2 分钟后仍然还没有完成，我没有耐心等下去，提前结束它了。

小结

分治法是解决问题的优秀思想，不仅在现实生活中，在程序开发中更是如此，本文主要通过归并算法实例讨论了这一点。不过应该注意，使用分治法解决问题时，问题应该满足以下条件：

• 问题可以拆分为若干类似的彼此不干扰的子问题
• 问题规模缩小时，更容易解决
• 子问题的解可以合并为原始问题的解

显然，这些条件是容易理解的。

点个关注再走吧

欢迎在评论区一起讨论，质疑。文章都是手打原创，每天最浅显的介绍C语言、linux等嵌入式开发，喜欢我的文章就关注一波吧，可以看到最新更新和之前的文章哦。

未经许可，禁止转载。

算法-分治法

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最大子段和问题

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

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

4.2棋盘覆盖问题

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循环赛日程安排问题

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

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

5.几何问题中的分治法

5.1最近对问题

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

5.2凸包问题

总结

最后

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