1、目 录 7目 录 第 1 章 一大波数正在靠近排序.1 第 1节 最快最简单的排序桶排序.2 第 2节 邻居好说话冒泡排序.7 第 3节 最常用的排序快速排序.12 第 4节 小哼买书.20 第 2 章 栈、队列、链表.25 第 1节 解密 QQ号队列.26 第 2节 解密回文栈.32 第 3节 纸牌游戏小猫钓鱼.35 第 4节 链表.44 第 5节 模拟链表.54 第 3 章 枚举！很暴力.57 第 1节 坑爹的奥数.58 第 2节 炸弹人.61 第 3节 火柴棍等式.67 第 4节 数的全排列.70 第 4 章 万能的搜索.72 第 1节 不撞南墙不回头深度优先搜索.73 第 2节 解救小
2、哈.81 第 3节 层层递进广度优先搜索.88 第 4节 再解炸弹人.95 第 5节 宝岛探险.106 第 6节 水管工游戏.117 第 5 章 图的遍历.128 第 1节 深度和广度优先究竟是指啥.129 第 2节 城市地图图的深度优先遍历.136 啊哈！算法 8 第 3节 最少转机图的广度优先遍历.142 第 6 章 最短路径.147 第 1节 只有五行的算法Floyd-Warshall.148 第 2节 Dijkstra算法通过边实现松弛.155 第 3节 Bellman-Ford解决负权边.163 第 4节 Bellman-Ford的队列优化.171 第 5节 最短路径算法对比分析.1
3、77 第 7 章 神奇的树.178 第 1节 开启“树”之旅.179 第 2节 二叉树.183 第 3节 堆神奇的优先队列.185 第 4节 擒贼先擒王并查集.200 第 8 章 更多精彩算法.211 第 1节 镖局运镖图的最小生成树.212 第 2节 再谈最小生成树.219 第 3节 重要城市图的割点.229 第 4节 关键道路图的割边.234 第 5节 我要做月老二分图最大匹配.237 第 9 章 还能更好吗微软亚洲研究院面试.243 第 1章 一大波数正在靠近排序 1一大波数正在靠近 排序 第1章 啊哈！算法 2 第 1 节 最快最简单的排序桶排序 在我们生活的这个世界中到处都是被排序过
4、的东东。站队的时候会按照身高排序，考试的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排序总之很多东东都需要排序，可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。首先出场的是我们的主人公小哼，上面这个可爱的娃就是啦。期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有 5 个同学，这 5 个同学分别考了 5分、3 分、5 分、2 分和 8 分，哎考得真是惨不忍睹（满分是 10 分）。接下来将分数进行从大到小排序，排序后是 8 5 5 3 2。你有没有什么好方法编写一段程序，让计算机随机读入 5 个数然后将这5 个数从大到小输出？请先想一
5、想，至少想 15 分钟再往下看吧(*_*)。第 1章 一大波数正在靠近排序 3 我们这里只需借助一个一维数组就可以解决这个问题。请确定你真的仔细想过再往下看哦。首先我们需要申请一个大小为 11 的数组 int a11。OK，现在你已经有了 11 个变量，编号从 a0a10。刚开始的时候，我们将 a0a10都初始化为 0，表示这些分数还都没有人得过。例如 a0等于 0 就表示目前还没有人得过 0 分，同理 a1等于 0 就表示目前还没有人得过 1 分a10等于 0 就表示目前还没有人得过 10 分。下面开始处理每一个人的分数，第一个人的分数是 5 分，我们就将相对应的 a5的值在原来的基础增加
6、1，即将 a5的值从 0 改为 1，表示 5 分出现过了一次。第二个人的分数是 3 分，我们就把相对应的 a3的值在原来的基础上增加 1，即将 a3的值从 0 改为 1，表示 3分出现过了一次。啊哈！算法 4 注意啦！第三个人的分数也是 5 分，所以 a5的值需要在此基础上再增加 1，即将 a5的值从 1 改为 2，表示 5分出现过了两次。按照刚才的方法处理第四个和第五个人的分数。最终结果就是下面这个图啦。你发现没有，a0a10中的数值其实就是 0 分到 10 分每个分数出现的次数。接下来，我们只需要将出现过的分数打印出来就可以了，出现几次就打印几次，具体如下。a0为 0，表示“0”没有出现过
7、，不打印。a1为 0，表示“1”没有出现过，不打印。a2为 1，表示“2”出现过 1 次，打印 2。a3为 1，表示“3”出现过 1 次，打印 3。a4为 0，表示“4”没有出现过，不打印。a5为 2，表示“5”出现过 2 次，打印 5 5。a6为 0，表示“6”没有出现过，不打印。a7为 0，表示“7”没有出现过，不打印。a8为 1，表示“8”出现过 1 次，打印 8。a9为 0，表示“9”没有出现过，不打印。a10为 0，表示“10”没有出现过，不打印。最终屏幕输出“2 3 5 5 8”，完整的代码如下。#include int main()int a11,i,j,t;for(i=0;i=
8、10;i+)ai=0;/初始化为0 for(i=1;i=5;i+)/循环读入5个数 第 1章 一大波数正在靠近排序 5 scanf(%d,&t);/把每一个数读到变量t中 at+;/进行计数 for(i=0;i=10;i+)/依次判断a0a10 for(j=1;j=ai;j+)/出现了几次就打印几次 printf(%d,i);getchar();getchar();/这里的getchar();用来暂停程序，以便查看程序输出的内容 /也可以用system(pause);等来代替 return 0;输入数据为：5 3 5 2 8 仔细观察的同学会发现，刚才实现的是从小到大排序。但是我们要求是从大到
9、小排序，这该怎么办呢？还是先自己想一想再往下看哦。其实很简单。只需要将 for(i=0;i=0;i-)就 OK啦，快去试一试吧。这种排序方法我们暂且叫它“桶排序”。因为其实真正的桶排序要比这个复杂一些，以后再详细讨论，目前此算法已经能够满足我们的需求了。这个算法就好比有 11 个桶，编号从 010。每出现一个数，就在对应编号的桶中放一个小旗子，最后只要数数每个桶中有几个小旗子就 OK了。例如 2 号桶中有 1 个小旗子，表示2 出现了一次；3 号桶中有 1 个小旗子，表示 3 出现了一次；5 号桶中有 2 个小旗子，表示 5出现了两次；8 号桶中有 1 个小旗子，表示 8出现了一次。现在你可以
10、尝试一下输入 n 个 01000 之间的整数，将它们从大到小排序。提醒一下，啊哈！算法 6 如果需要对数据范围在 01000 之间的整数进行排序，我们需要 1001 个桶，来表示 01000之间每一个数出现的次数，这一点一定要注意。另外，此处的每一个桶的作用其实就是“标记”每个数出现的次数，因此我喜欢将之前的数组 a 换个更贴切的名字 book（book 这个单词有记录、标记的意思），代码实现如下。#include int main()int book1001,i,j,t,n;for(i=0;i=1000;i+)booki=0;scanf(%d,&n);/输入一个数n，表示接下来有n个数 fo
11、r(i=1;i=0;i-)/依次判断编号10000的桶 for(j=1;j=booki;j+)/出现了几次就将桶的编号打印几次 printf(%d,i);getchar();getchar();return 0;可以输入以下数据进行验证。10 8 100 50 22 15 6 1 1000 999 0 运行结果是：1000 999 100 50 22 15 8 6 1 0 最后来说下时间复杂度的问题。代码中第 6 行的循环一共循环了 m次（m为桶的个数），第 9 行的代码循环了 n 次（n 为待排序数的个数），第 14 行和第 15 行一共循环了 m+n 次。所以整个排序算法一共执行了 m+n
12、+m+n 次。我们用大写字母 O来表示时间复杂度，因此该第 1章 一大波数正在靠近排序 7算法的时间复杂度是 O(m+n+m+n)即 O(2*(m+n)。我们在说时间复杂度的时候可以忽略较小的常数，最终桶排序的时间复杂度为 O(m+n)。还有一点，在表示时间复杂度的时候，n 和 m通常用大写字母即 O(M+N)。这是一个非常快的排序算法。桶排序从 1956 年就开始被使用，该算法的基本思想是由E.J.Issac 和 R.C.Singleton提出来的。之前我说过，其实这并不是真正的桶排序算法，真正的桶排序算法要比这个更加复杂。但是考虑到此处是算法讲解的第一篇，我想还是越简单易懂越好，真正的桶排
13、序留在以后再聊吧。需要说明一点的是：我们目前学习的简化版桶排序算法，其本质上还不能算是一个真正意义上的排序算法。为什么呢？例如遇到下面这个例子就没辙了。现在分别有 5 个人的名字和分数：huhu 5 分、haha 3分、xixi 5 分、hengheng 2 分和 gaoshou 8 分。请按照分数从高到低，输出他们的名字。即应该输出 gaoshou、huhu、xixi、haha、hengheng。发现问题了没有？如果使用我们刚才简化版的桶排序算法仅仅是把分数进行了排序。最终输出的也仅仅是分数，但没有对人本身进行排序。也就是说，我们现在并不知道排序后的分数原本对应着哪一个人！这该怎么办呢？不要
14、着急，请看下节冒泡排序。第 2 节 邻居好说话冒泡排序 简化版的桶排序不仅仅有上一节所遗留的问题，更要命的是：它非常浪费空间！例如需要排序数的范围是 02100000000 之间，那你则需要申请 2100000001 个变量，也就是说要写成 int a2100000001。因为我们需要用 2100000001 个“桶”来存储 02100000000 之间每一个数出现的次数。即便只给你 5 个数进行排序（例如这 5 个数是 1、1912345678、2100000000、18000000 和 912345678），你也仍然需要 2100000001 个“桶”，这真是太浪费空间了！还有，如果现在需
15、要排序的不再是整数而是一些小数，比如将 5.56789、2.12、1.1、3.123、4.1234这五个数进行从小到大排序又该怎么办呢？现在我们来学习另一种新的排序算法：冒泡排序。它可以很好地解决这两个问题。冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。例如我们需要将 12 35 99 18 76 这 5个数进行从大到小的排序。既然是从大到小排序，也就是说越小的越靠后，你是不是觉得我在说废话，但是这句话很关键(_)。首先比较第 1 位和第 2 位的大小，现在第 1 位是 12，第 2 位是 35。发现 12比 35 要小，啊哈！算法 8 因为我们希望越小越靠
16、后嘛，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是35 12 99 18 76。按照刚才的方法，继续比较第 2 位和第 3 位的大小，第 2位是 12，第 3位是 99。12比99 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 99 12 18 76。根据刚才的规则，继续比较第 3 位和第 4 位的大小，如果第 3 位比第 4 位小，则交换位置。交换之后这 5 个数的顺序是 35 99 18 12 76。最后，比较第 4 位和第 5 位。4 次比较之后 5 个数的顺序是 35 99 18 76 12。经过 4 次比较后我们发现最小的一个数已经就位（已经在最后一位，请注意 12 这个数的移动过程），是不是很神奇。现在再来回忆一下刚才比较的过程。每次都是比较相邻的两个数，如果后面的数比前面的数大，则交换这两个数的位置。一直比较下去直到最后两个数比较完毕后，最小的数就在最后一个了。就如同是一个气泡，一步一步往后“翻滚”，直到最后一位。所以这个排序的方法有一个很好听的名字“冒泡排序”。说到这里其实我们的排序只将 5 个数中最小的一个归位了。每将一个数归位我们