GESP5级C++考试语法知识（十四、分治算法（一））

🌟分治算法第一课：《分治魔法初体验》

—— 魔法学院的“拆问题”超级魔法

🏰 故事开始：乱糟糟的魔法书架

1、在遥远的算法大陆上，
有一所非常厉害的学校：

✨分治魔法学院✨

2、这一天，小魔法师“小码”接到了一个任务：

📚 整理魔法图书馆！

3、图书馆里有很多数字魔法书：

8 3 5 1 7 2 6 4

4、管理员爷爷着急地说：

“天啊！这些书完全乱了！”

“如果一本一本慢慢整理，
可能天黑都整理不完呀！”

5、同学们想：

“那怎么办呢？”

6、这时，汉克老师出现了！

他说：

✨“遇到大问题，不要硬拼！”✨

✨“把它拆小！我们可以使用分治算法来解决”✨

🌈 一、什么叫“分治”？

1、汉克老师在黑板上写下：

大问题 ↓ 拆成小问题 ↓ 分别解决 ↓ 最后合并

这就是：

🌟分治算法（Divide and Conquer）

2、🧠 分治是什么意思？

（1）“分”：

👉 把大问题拆开

（2）“治”：

👉 解决小问题

（3）最后：

👉 再把答案合起来

3、🍭 就像吃大蛋糕！

（1）如果一个超大蛋糕：

🎂🎂🎂🎂🎂🎂🎂

一口根本吃不下！

（2）怎么办？

当然是：

切开

（3）变成：

🍰 🍰 🍰 🍰

很多小蛋糕，我们就容易吃的下了！

4、🌟 分治算法最核心的思想

✨“大问题不好做？”

✨“那就拆小！”✨

🏰 二、第一次学习“拆问题”

1、举个例子，现在我们来整理：

8 3 5 1

2、汉克老师说：

“先别急着排序！”

先拆！

3、第一步：切一半

8 3 5 1

4、第二步：继续拆

（1）左边：

8 3

还能拆：

8 3

（2）右边：

5 1

还能拆：

5 1

（3）现在变成：

8 3 5 1

5、🌟 神奇的事情来了！

每组只有：

1个数字

的时候，

其实已经：

“自动有序了！”

6、比如：

8

只有一个数。

乱不乱？

当然不乱！

7、所以：

🌟分治算法的重要思想：

当问题足够小，

它就变简单了！

🧠 三、开始“治”——解决小问题

1、现在：

8 3

怎么合并？

2、汉克老师说：

“谁小谁在前面！”

3、比较：

8 和 3

3更小！

4、所以：

3 8

5、另一边：

5 和 1

6、变成：

1 5

7、现在整个世界变成：

3 8 1 5

🌟 四、最后一步：合并大答案

1、现在：

（1）左边有序：

3 8

（2）右边也有序：

1 5

（3）怎么变成：

1 3 5 8

呢？

2、🍭 拉拉链魔法！

（1）像拉拉链一样：

（2）比较左右两边的第一个数：

3 和 1

1更小：

1

1就排在前面了。1的后面的数字5，就要参与下一轮比较了。

（3）再比较：

3 和 5

3更小：

1 3

3就排在1的后面了。3的后面的数字8，就要参与下一轮比较了。

（4）再比较：

8 和 5

5更小：

1 3 5

5就排在3的后面了。3的后面的数字8，没有比较的对手了。

（5）最后只剩下：

8

得到：

1 3 5 8

（6）这个交替比较的过程，是不是就像：

给左右两侧的衣服，拉拉链一样呢？

🌈 五、这就是分治算法！

整个过程：

🌟第一步：分（Divide）

拆开：

8 3 5 1 ↓ 8 3 ｜ 5 1 ↓ 8 ｜ 3 ｜ 5 ｜ 1

🌟第二步：治（Conquer）

小问题自己解决：

8 和 3 → 3 8 5 和 1 → 1 5

🌟第三步：合（Combine）

把答案合并：

3 8 + 1 5 ↓ 1 3 5 8

🎯 六、为什么分治算法厉害？

1、汉克老师问大家：

“如果有100万个数字，
一个一个整理，
会不会累死？”

2、同学们回答：

会！！！

3、但分治法：

一直拆 一直拆 一直拆

4、每次都把问题变小。

而且拆的，特别快！

🌟 七、生活中的分治思想

1、🍕 分披萨

太大：

🍕

切开：

🍕 🍕 🍕 🍕

2📚 整理书柜

先整理左边。

再整理右边。

左右两边分别治理。

最后达成全部有序。

3、👨‍👩‍👧‍👦 大扫除

一家人一起分工：

• 妈妈扫地

• 爸爸擦桌子

• 孩子整理玩具

比一个人干快多了！

🌟 八、归并排序正式登场

1、刚刚汉克老师讲的这个：

拆开 排序 合并

的排序方法，

名字叫：

✨归并排序（Merge Sort）✨

2、🧠 为什么叫“归并”？

因为：

先拆，拆到最小，

再“归”回来，

“并”在一起。

🌳 九、归并排序的递归树

1、汉克老师在黑板画了一棵树：

8 3 5 1 / \ 8 3 5 1 / \ / \ 8 3 5 1

2、再往回合并：

3 8 1 5 \ / 1 3 5 8

3、🌟 这个递归树：

它能帮助我们：

看清问题是怎么被拆开的！

🎮 十、课堂小游戏：《魔法数字整理师》

1、汉克老师给出数字：

7 2 9 1

请同学们：

第一步

拆：

7 2 ｜ 9 1

第二步

继续拆：

7 ｜ 2 ｜ 9 ｜ 1

第三步

排序合并：

2 7 ｜ 1 9

第四步

最终：

1 2 7 9

🌟十一、归并排序完整程序

#include <iostream> using namespace std; int a[100]; // 原数组 int temp[100]; // 临时数组 // 归并排序函数 void merge_sort(int l, int r) { // 只有一个数字，不需要排序 if(l == r) return; // 找中间位置 int mid = (l + r) / 2; // 排序左边 merge_sort(l, mid); // 排序右边 merge_sort(mid + 1, r); // 开始合并 int i = l; // 左边起点 int j = mid + 1; // 右边起点 int k = l; // temp数组的位置 // 两边都有数字时 while(i <= mid && j <= r) { // 谁小谁先放进去 if(a[i] <= a[j]) { temp[k] = a[i]; i++; } else { temp[k] = a[j]; j++; } k++; } // 左边还有剩余 while(i <= mid) { temp[k] = a[i]; i++; k++; } // 右边还有剩余 while(j <= r) { temp[k] = a[j]; j++; k++; } // 把排好序的数据复制回原数组 for(int p = l; p <= r; p++) { a[p] = temp[p]; } } int main() { int n; cout << "请输入数字个数："; cin >> n; cout << "请输入数字：" << endl; for(int i = 0; i < n; i++) { cin >> a[i]; } // 调用归并排序 merge_sort(0, n - 1); cout << "排序后：" << endl; for(int i = 0; i < n; i++) { cout << a[i] << " "; } return 0; }

🌟 十二：代码详细讲解

1、🧠 数组定义

（1）原始数组：

int a[100];

这是：

原始数字仓库

例如：

8 3 5 1

都放在这里。

（2）🌟 temp数组

int temp[100];

这是：

临时整理仓库

（3）为什么需要它？

因为：

排序时不能乱覆盖原数据。

所以先放到temp里。

2、🌟 归并排序函数

void merge_sort(int l, int r)

（1）上传参数的意思：

排序：

l 到 r

这一段数字。

（2）例如：

merge_sort(0,3);

意思：

排序：

第0~3个数字

3、🌟 结束条件

if(l == r) return;

（1）🧠 为什么？

因为：

只有一个数字

时，

它已经有序了！

（2）例如：

8

需要排序吗？

当然不用！

4、🌟 确定中间位置

int mid = (l + r) / 2;

（1）例如：

0 ~ 3

中间位置：

1

（2）所以：

左边：

0~1

右边：

2~3

5、🌟 递归拆分

(1) 先排左边

merge_sort(l, mid);

(2)再排右边

merge_sort(mid + 1, r);

6、🌳 递归树（课堂演示）

（1）程序会变成：

merge_sort(0,3) ↓ merge_sort(0,1) merge_sort(2,3)

（2）继续：

merge_sort(0,0) merge_sort(1,1) merge_sort(2,2) merge_sort(3,3)

（3）最后全部拆成：

单个数字！

7、🌟 开始合并（最核心）

（1）三个小助手

int i = l; int j = mid + 1; int k = l;

（2）🧠 i是谁？

左边队伍开始的指针。

（3）🧠 j是谁？

右边队伍开始的指针。

（4）🧠 k是谁？

temp数组位置。

（5）🌈 举例

现在：

左边：

位置索引： 0 1 数值： 3 8

右边：

位置索引： 2 3 数值： 1 5

三个小助手:

左侧队伍指针 i = 0 左侧队伍指针 j = 2 临时数组temp k= 0

开始比较：

第一次

3 和 1

1小。

放进去：

1

三个小助手:

左侧队伍指针 i = 0 左侧队伍指针 j = 2+1 =3 临时数组temp k= 0+1 =1

第二次

3 和 5

3小。

变成：

1 3

三个小助手:

左侧队伍指针 i = 0+1 =1 左侧队伍指针 j = 3 临时数组temp k= 1+1 =2

第三次

8 和 5

5小。

变成：

1 3 5

三个小助手:

左侧队伍指针 i = 1 左侧队伍指针 j = 3+1=4 (4>3） 临时数组temp k= 2+1=3

最后剩下8

得到：

1 3 5 8

// 左边还有剩余 while(i <= mid) { temp[k] = a[i]; i++; k++; }

左侧队伍指针 i = 1+1=2（2>1） 左侧队伍指针 j = 4 (4>3） 临时数组temp k= 3+1=4

排好了，还要复制回原来的数组

// 把排好序的数据复制回原数组 for(int p = l; p <= r; p++) { a[p] = temp[p]; } }

8、🌟 核心while循环

while(i <= mid && j <= r)

意思：

左右两边都有数字时

持续比较。

🌟 谁小谁进去

if(a[i] <= a[j])

如果左边更小。

temp[k] = a[i];

放进temp。

然后：

i++;

左边向后走。

9、🌟 处理剩余数字

有时候：

左边结束了。

右边还有数字。

例如：

1 3

和：

5 8 9

前面比较完：

1 3

后：

5 8 9

还没放进去。

怎么办？

直接全部复制！

左边剩余

while(i <= mid)

右边剩余

while(j <= r)

10、🌟 复制回原数组

for(int p = l; p <= r; p++) { a[p] = temp[p]; }

为什么？

因为：

真正的数据在：

temp

里面。

要复制回：

a数组

11、🌟 完整运行过程演示

输入：

8 3 5 1

第一步：拆

8 3 ｜ 5 1

第二步：继续拆

8 ｜ 3 ｜ 5 ｜ 1

第三步：合并小组

3 8 ｜ 1 5

第四步：最终合并

1 3 5 8

12、🌟 时间复杂度

归并排序非常快！

因为：

每次都：

对半拆！

速度大约：

O(n log n)

小学生可以简单记：

“超级快的排序，而且非常稳定的排序！”

13、🌟 归并排序优点

✅ 非常稳定

相同数字不会乱顺序。

✅ 非常快

适合大量数据。

✅ 分治思想特别经典

很多高级算法都从这里开始。

🌟 十三、本课总结：

1、✨“大问题拆小，小问题解决，再合起来！”✨

这就是：

🌈分治算法的灵魂！

2、✨分治算法不是硬拼！✨

而是：

大问题 ↓ 拆小 ↓ 小问题解决 ↓ 再合并

3、今天我们学会了：

🌟 什么是分治法

把大问题拆小。

4、🌟 分治三步

分 治 合

5、🌟 什么是归并排序

不断拆分。

最后合并。

6、🌟 为什么分治厉害

因为：

小问题更容易解决！

十四、🏆 课后挑战

请同学们自己试着拆：

6 4 9 2 7 1

看看：

🌟 怎么拆？

🌟 怎么合并？

🌟 最后结果是什么？

🌈 下节课预告

下一节课：

⚡《快速排序大冒险》⚡

我们会学习：

🌟 如何选“队长数字”

🌟 如何让小的站左边

🌟 如何让大的站右边

🌟 神奇的双指针魔法

还有更多冒险等着大家！