哇，编程！——跟小明一起学算法

内 容 简 介
本书融入了游戏设计思想，通过游戏攻关的方式，介绍各种算法的原理和应用。全书共分8章，具体包括排序算法、穷举算法、递归算法、回溯算法、贪心算法、分治算法，栈、队列、树三种数据结构，动态规划算法，图论相关算法等内容。

游明伟，神鸡编程教育研究院副院长，毕业于武汉大学，原平安集团高级工程师。15岁开始接触编程，师从NOI金牌教练董永建，获NOIP2007（提高组）福建省赛区一等奖，获武汉大学、厦门大学等多校保送资格，参与《信息学奥赛一本通（提高篇）》第一版编著。

吴健之。武汉大学计算机学院本科、硕士，师从武汉大学原常务副校长、现深圳大学校长李清泉教授。神鸡编程联合创始人兼首席技术官，神鸡编程教育研究院常务副院长，腾讯QQ音乐原高级工程师，金牌讲师。10年专业编程实践经验，是中国青少儿编程教育界中的实战派。加入腾讯前，曾任极验验证（IDG、红衫投资）创业合伙人兼产品副总裁。曾经参与工信部在线视频教学系统的研发、中华书局“基于二十四史的大数据与知识图谱语义分析”研发。

数据结构与算法是计算机专业的一门必修基础课，作为程序员的底层能力，理解并掌握这些知识不仅可以培养罗辑思维能力，更能深入理解计算机系统，从而才能写出更高效的代码。本书作者曾获得2007年全国青少年信息学奥林匹克联赛提高组福建省赛区一等奖，作者结合自己的学习经历和实战经验，深入浅出地讲解了各种常用算法和数据结构和原理和应用。书中将游戏与算法结合，通过游戏攻关的形式将知识点层层递进，将学习枯燥的算法变成了一项孩子们喜欢做的事情。用浅显易懂的语言讲解分析每种算法，并给出完整的代码，使学习变得轻松有趣。

前言
近些年来，随着人工智能、大数据等技术的迅猛发展，计算机编程开始逐渐进入大众的视野，特别是教育行业，各种少儿编程班如雨后春笋般层出不穷。人们开始渐渐意识到，培养孩子的逻辑和计算思维能力，已经成为一项必不可少的教育方式。而这些在我的童年时期，是一项遥不可及的事物，甚至在我小学和初中期间，计算机还仍未被普及。那时候人们对计算机的认识，还只限于QQ和各种网页小游戏。计算机科学发展到现在，我们在感叹科技发展迅速的同时，也必须感谢这个美好的时代。
我第一次接触计算机编程是在初三保送高中阶段，其他同学还在埋头准备中考时，我有幸遇到了我的恩师——NOI金牌教练董永建。恰逢董老师在保送生中选拔信息学奥赛学生，中考期间和整个暑假，我们42名保送生提前开始了高中生活，跟随董老师从零开始接触计算机、学习算法，直到暑假结束仅剩4名同学坚持了下来。后来，我们4个人从机房搬进了
“小黑屋”，认识了各位师兄，开始了真正的“封闭式训练”。高中三年我们没有周末、没有节假日、没有寒暑假，把所有的课余时间全贡献给“小黑屋”，董老师带着我们参加各种培训、参加高校ACM比赛，为了锻炼体能，带着我们爬山，偷玩游戏被发现了，罚我们操场跑圈……和师兄、师弟、师妹们在“小黑屋”里的三年时光，是我至今回想都觉得快乐的时光，也是影响我一生的时光。在接触编程后半年，我第一次参加了NOIP（National Olympiad in Informatics in Provinces，信息学奥林匹克联赛），第一年初出茅庐，只是让我们见识了世面，师兄们才是当年的主力。我们充当了一年陪考，直到第二年，经过一年多的积累，我们成了主力，在2017年NOIP竞赛，我获得了省一等奖。所有光鲜的背后，都隐藏着熬过无数个不为人知的黑夜。
非常感谢董永建老师的悉心教导，让我在初中时期开始，对计算机编程和算法有了初步的认识。也缘于NOIP竞赛，让我取得了保送武汉大学的资格，并因此决定了我毕业以后的工作和生活。人生选择一条路，一直走到尽头，不退让，不更改，是件幸事。
NOIP竞赛对于很多孩子和家长来说，还是一个比较陌生的事物。它由中国计算机学会（CCF）统一组织，每年在同一时间、不同地点以各省市为单位由特派员组织。这个竞赛最初设立的目的是向中学阶段的青少年普及计算机科学知识，带来新的学习思路，并借此选拔人才。得益于近年来计算机知识的普及，许多对算法思想感兴趣的学生和家长已经开始把NOIP当成一种新的学习思路和方法。本书所讲的算法便是基于NOIP竞赛内容进行阐述的，从基础的排序算法到图论算法，逐步深入了解算法思路。
为了便于各位读者对枯燥算法内容的理解，本书融入了游戏设计思想，通过游戏攻关的方式，介绍各种算法的原理和应用。当你通读完本书后，会发现原来我们平常玩的各种手游，比如“吃鸡”“王者”，它们的设计思路就是采用了各种算法，这时候你就已经开始领略到算法的奥妙，并开始进入算法的魔法大门了。
为什么写这本书?
写这本书的原因，是来自朋友和妻子的启发。得益于NOIP竞赛，我大学的专业学的是软件工程，毕业后从事的也是软件开发工作。在快要迈入而立之年的某一天，我的妻子问了我一个问题：“你做了这么多年软件开发，早年也参加过NOIP，是不是现在得有所沉淀了？”这时候我们的女儿刚出生6个月，我因此开始思考教育的问题。这时候我的一个朋友告诉
我：“你可以尝试写一本书，将你在NOIP竞赛所学及多年工作积累记录下来，说不定以后还能用来给你女儿当教材。”于是，便有了这本《哇，编程！——跟小明一起学算法》。
■ 本书导读
全书共分8章：
第1章主要介绍排序算法，介绍了经典的三种排序方法，同时介绍了时间复杂度、空间复杂度。
第2章主要介绍了五种基础的算法，是信息学奥赛中常见的五种算法，一道算法题往往会包含多种基础算法，本章也为后续篇章的算法奠定基础。
第3、4章主要介绍了三种数据结构——栈、队列、树，数据结构是一门语言的基础，本章在介绍算法的同时也强化了C++语言，补充了一些C++基础学习中未涉及的内容。
第5章主要介绍了动态规划算法，动态规划算法往往是NOIP（普及组、提高组）的压轴题，也是能区分竞赛选手差距的题目，本章由最经典的背包问题开始讲解动态规划算法，理解本章才算是开始理解“算法的精髓”。
第6、7、8章主要介绍图论相关算法，包括深度优先搜索、广度优先搜索、图的遍历、最小生成树、并查集、最短路径等。这三章所讲的算法属于进阶算法，图论相关算法其本质依然是前面章节所讲的基础算法，在介绍图论算法时，也继续帮助读者巩固前面部分的基础算法。
阅读本书的读者，需要具备基本的C++语言基础，本书算法尽量采用通俗易懂的例子给读者讲解。学习算法并不是一件难事，算法本身也并不高深，难在理解算法后怎么再用通俗的话语讲解出来。本书所涉及的算法，也是我从初中就开始接触并学习的，我相信初中程度的读者也能够理解并使用本书所写的算法。
■ 致谢
在开始写这本书之前，我一直犹豫要不要写，因为刚出生的女儿几乎占用了我所有周末和空闲时间，是妻子的鼓励，让我下定决心要写完这本书，作为送给女儿的礼物。在我写书的这半年里，所有的节假日我都躲在图书馆度过，感谢我的妻子这半年里辛劳的付出，感谢她在背后的支持。
感谢我的大学室友——JazyWoo同学提供了给我写书的机会，帮我联络各方资源，也感谢他在写书期间，与我共同探讨，共同完成此书。
还要再一次感谢董永建老师，是他的谆谆教导才能让我有幸写了这本算法书。

游明伟
2019年4月前言
近些年来，随着人工智能、大数据等技术的迅猛发展，计算机编程开始逐渐进入大众的视野，特别是教育行业，各种少儿编程班如雨后春笋般层出不穷。人们开始渐渐意识到，培养孩子的逻辑和计算思维能力，已经成为一项必不可少的教育方式。而这些在我的童年时期，是一项遥不可及的事物，甚至在我小学和初中期间，计算机还仍未被普及。那时候人们对计算机的认识，还只限于QQ和各种网页小游戏。计算机科学发展到现在，我们在感叹科技发展迅速的同时，也必须感谢这个美好的时代。
我第一次接触计算机编程是在初三保送高中阶段，其他同学还在埋头准备中考时，我有幸遇到了我的恩师——NOI金牌教练董永建。恰逢董老师在保送生中选拔信息学奥赛学生，中考期间和整个暑假，我们42名保送生提前开始了高中生活，跟随董老师从零开始接触计算机、学习算法，直到暑假结束仅剩4名同学坚持了下来。后来，我们4个人从机房搬进了
“小黑屋”，认识了各位师兄，开始了真正的“封闭式训练”。高中三年我们没有周末、没有节假日、没有寒暑假，把所有的课余时间全贡献给“小黑屋”，董老师带着我们参加各种培训、参加高校ACM比赛，为了锻炼体能，带着我们爬山，偷玩游戏被发现了，罚我们操场跑圈……和师兄、师弟、师妹们在“小黑屋”里的三年时光，是我至今回想都觉得快乐的时光，也是影响我一生的时光。在接触编程后半年，我第一次参加了NOIP（National Olympiad in Informatics in Provinces，信息学奥林匹克联赛），第一年初出茅庐，只是让我们见识了世面，师兄们才是当年的主力。我们充当了一年陪考，直到第二年，经过一年多的积累，我们成了主力，在2017年NOIP竞赛，我获得了省一等奖。所有光鲜的背后，都隐藏着熬过无数个不为人知的黑夜。
非常感谢董永建老师的悉心教导，让我在初中时期开始，对计算机编程和算法有了初步的认识。也缘于NOIP竞赛，让我取得了保送武汉大学的资格，并因此决定了我毕业以后的工作和生活。人生选择一条路，一直走到尽头，不退让，不更改，是件幸事。
NOIP竞赛对于很多孩子和家长来说，还是一个比较陌生的事物。它由中国计算机学会（CCF）统一组织，每年在同一时间、不同地点以各省市为单位由特派员组织。这个竞赛最初设立的目的是向中学阶段的青少年普及计算机科学知识，带来新的学习思路，并借此选拔人才。得益于近年来计算机知识的普及，许多对算法思想感兴趣的学生和家长已经开始把NOIP当成一种新的学习思路和方法。本书所讲的算法便是基于NOIP竞赛内容进行阐述的，从基础的排序算法到图论算法，逐步深入了解算法思路。
为了便于各位读者对枯燥算法内容的理解，本书融入了游戏设计思想，通过游戏攻关的方式，介绍各种算法的原理和应用。当你通读完本书后，会发现原来我们平常玩的各种手游，比如“吃鸡”“王者”，它们的设计思路就是采用了各种算法，这时候你就已经开始领略到算法的奥妙，并开始进入算法的魔法大门了。
为什么写这本书?
写这本书的原因，是来自朋友和妻子的启发。得益于NOIP竞赛，我大学的专业学的是软件工程，毕业后从事的也是软件开发工作。在快要迈入而立之年的某一天，我的妻子问了我一个问题：“你做了这么多年软件开发，早年也参加过NOIP，是不是现在得有所沉淀了？”这时候我们的女儿刚出生6个月，我因此开始思考教育的问题。这时候我的一个朋友告诉
我：“你可以尝试写一本书，将你在NOIP竞赛所学及多年工作积累记录下来，说不定以后还能用来给你女儿当教材。”于是，便有了这本《哇，编程！——跟小明一起学算法》。
■ 本书导读
全书共分8章：
第1章主要介绍排序算法，介绍了经典的三种排序方法，同时介绍了时间复杂度、空间复杂度。
第2章主要介绍了五种基础的算法，是信息学奥赛中常见的五种算法，一道算法题往往会包含多种基础算法，本章也为后续篇章的算法奠定基础。
第3、4章主要介绍了三种数据结构——栈、队列、树，数据结构是一门语言的基础，本章在介绍算法的同时也强化了C++语言，补充了一些C++基础学习中未涉及的内容。
第5章主要介绍了动态规划算法，动态规划算法往往是NOIP（普及组、提高组）的压轴题，也是能区分竞赛选手差距的题目，本章由最经典的背包问题开始讲解动态规划算法，理解本章才算是开始理解“算法的精髓”。
第6、7、8章主要介绍图论相关算法，包括深度优先搜索、广度优先搜索、图的遍历、最小生成树、并查集、最短路径等。这三章所讲的算法属于进阶算法，图论相关算法其本质依然是前面章节所讲的基础算法，在介绍图论算法时，也继续帮助读者巩固前面部分的基础算法。
阅读本书的读者，需要具备基本的C++语言基础，本书算法尽量采用通俗易懂的例子给读者讲解。学习算法并不是一件难事，算法本身也并不高深，难在理解算法后怎么再用通俗的话语讲解出来。本书所涉及的算法，也是我从初中就开始接触并学习的，我相信初中程度的读者也能够理解并使用本书所写的算法。
■ 致谢
在开始写这本书之前，我一直犹豫要不要写，因为刚出生的女儿几乎占用了我所有周末和空闲时间，是妻子的鼓励，让我下定决心要写完这本书，作为送给女儿的礼物。在我写书的这半年里，所有的节假日我都躲在图书馆度过，感谢我的妻子这半年里辛劳的付出，感谢她在背后的支持。
感谢我的大学室友——JazyWoo同学提供了给我写书的机会，帮我联络各方资源，也感谢他在写书期间，与我共同探讨，共同完成此书。
还要再一次感谢董永建老师，是他的谆谆教导才能让我有幸写了这本算法书。

游明伟
2019年4月

目录
第1章　整理下背包 1
1.1　桶排序 2
1.2　冒泡排序 8
1.3　快速排序 15
1.4　时间和空间复杂度 20
第2章　开始闯关吧 22
2.1　忘记密码了——穷举算法 23
2.2　汉诺塔——递归算法 25
2.3　八皇后——回溯算法 31
2.4　分装备——贪心算法 41
2.5　二分查找——分治算法 45
第3章　爆满的服务器与背包 53
3.1　服务器爆满——队列 54
3.2　合成宝石——优先队列 61
3.3　背包里的道具——栈 65
3.4　十进制转任意进制 74
第4章　点亮技能树 77
4.1　树 78
4.1.1　树的定义 79
4.1.2　树的相关术语 80
4.2　二叉树 83
4.2.1　二叉树性质 84
4.2.2　特殊的二叉树 85
4.2.3　二叉树的遍历 87
4.2.4　二叉树的存储结构 105
4.3　堆 107
4.3.1　大根堆与小根堆 107
4.3.2　堆的操作 109
4.4　堆排序 132
第5章　爆装备啦，快来捡 139
5.1　捡到完美的海螺——递推算法 140
5.2　01背包——动规算法 143
5.3　完全背包——动规算法 148
5.4　多重背包——动规算法 152
第6章　迷宫 156
6.1　图的概念 157
6.1.1　图的定义 158
6.1.2　图的存储结构 162
6.2　图的遍历 167
6.2.1　深度优先搜索法 168
6.2.2　广度优先搜索法 172
6.3　并查集 176
6.3.1　分析 177
6.3.2　并查集的原理 179
6.3.3　并查集的操作 180
6.4　最小生成树 186
6.4.1　Prim算法 187
6.4.2　Kruskal算法 192
第7章　探索地图每个角落 197
7.1　深度优先搜索 198
7.2　广度优先搜索 211
第8章　快逃命去吧 229
8.1　拓扑排序 230
8.2　最短路径 240
8.2.1　Floyd算法 240
8.2.2　Dijkstra算法 250
8.2.3　Bellman-Ford算法 255
8.2.4　SPFA算法 261