算法基础：Python和C#语言实现

---作者简介---罗德·斯蒂芬斯（Rod Stephens） 连续15年被评为Microsoft Visual Basic最有价值专家（MVP），长期在ITT Technical Institute教授编程入门课程。他已经撰写了超过30本技术书籍，这些书被翻译成多种语言在世界范围内出版。他还撰写了超过250篇杂志文章，内容涵盖C#、Visual Basic、Delphi和Java等。---译者简介---余青松 华东师范大学高级工程师。1990年毕业于华东师范大学并留校任教。编著计算机相关教材30余本，在国内外学术期刊和学术会议上发表科技论文近百篇。江红 华东师范大学副教授，博士。1994年毕业于复旦大学计算机系。曾荣获上海市教学成果一等奖、华东师范大学教学成果一等奖、华东师范大学优秀任课教师奖等荣誉。

出版者的话译者序前言作者简介第1章　算法基础 111　方法 112　算法和数据结构 213　伪代码 214　算法的特点 4141　大O符号 5142　常用的运行时间函数 7143　运行时间函数的可视化比较 1115　实际考虑 1216　本章小结 1317　练习题 14第2章　数值算法 1621　数据随机化 16211　随机数生成器 16212　随机化数组 20213　生成非均匀分布 21214　随机行走 2222　查找最大公约数 25221　计算最大公约数 25222　最大公约数算法的扩展应用 2723　计算乘幂 2824　处理素数 29241　查找素数因子 29242　查找素数 31243　素性检验 3225　计算数值积分 33251　矩形法则 34252　梯形法则 34253　自适应积分算法 35254　蒙特卡罗积分法 3726　方程求解 3827　高斯消元法 40271　前向消元 40272　后向代换 41273　算法实现 4228　最小二乘法拟合 42281　线性最小二乘法 43282　多项式最小二乘法 4429　本章小结 45210　练习题 46第3章　链表 4831　基本概念 4832　单向链表 49321　遍历链表 49322　查找节点 49323　使用哨兵 50324　在顶部添加节点 51325　在尾部添加节点 51326　在指定节点后插入节点 52327　删除节点 5233　双向链表 5334　有序链表 5435　自组织链表 55351　前移方法 56352　交换方法 56353　计数方法 56354　混合方法 56355　伪代码 5736　链表算法 57361　复制链表 58362　插入排序 58363　选择排序 6037　多线链表 6138　循环链表 61381　标记节点 62382　使用哈希表 63383　链表回溯 64384　链表反转 65385　龟兔赛跑算法 66386　双向链表中的环路 6839　本章小结 68310　练习题 68第4章　数组 7041　基本概念 7042　一维数组 72421　查找数组元素 72422　查找最大值、最小值和平均值 72423　查找中值 73424　查找众数 74425　插入数组元素 76426　删除数组元素 7743　非零数组下界 77431　二维数组 78432　高维数组 7844　三角形数组 8145　稀疏数组 83451　查找行或列 84452　获取元素的值 85453　设置元素的值 86454　删除数组元素 8746　矩阵 8947　本章小结 9148　练习题 91第5章　堆栈和队列 9351　堆栈 93511　链表堆栈 94512　数组堆栈 95513　双堆栈 96514　堆栈算法 9752　队列 101521　链表队列 101522　数组队列 102523　特殊队列 10453　二项堆 105531　二项树的定义 105532　二项堆的定义 106533　合并树 107534　合并堆 108535　入队操作 111536　出队操作 111537　运行时间分析 11254　本章小结 11355　练习题 113第6章　排序 11561　O(N 2)算法 115611　数组的插入排序算法 115612　数组的选择排序算法 116613　冒泡排序算法 11762　O(NlogN)算法 119621　堆排序算法 120622　快速排序算法 124623　合并排序算法 13063　小于O(NlogN)的算法 132631　计数排序算法 132632　鸽巢排序算法 133633　桶排序算法 13564　本章小结 13665　练习题 137第7章　查找 13971　线性查找算法 13972　二分查找算法 14073　插值查找算法 14174　多数投票算法 14275　本章小结 14376　练习题 144第8章　哈希表 14581　哈希表的基本概念 14582　链接哈希表 14683　开放寻址哈希表 147831　删除数据项 148832　线性探测 149833　二次探测 150834　伪随机探测 151835　双重哈希 151836　有序哈希 15284　本章小结 15485　练习题 154第9章　递归 15691　基本算法 156911　阶乘 156912　斐波那契数 158913　棒料切割问题 159914　汉诺塔 16192　图形算法 163921　科赫曲线 163922　希尔伯特曲线 165923　谢尔宾斯基曲线 166924　垫圈图案 168925　天际线问题 16893　回溯算法 172931　八皇后问题 173932　骑士巡游问题 17594　组合与排列 177941　基于循环的组合 178942　允许重复项的组合 179943　不允许重复项的组合 180944　允许重复项的排列 181945　不允许重复项的排列 182946　轮询调度算法 18395　递归的删除 188951　尾部递归的删除 188952　动态规划 189953　自底向上编程 190954　删除递归的通用方法 19196　本章小结 19397　练习题 194第10章　树 196101　有关树的术语 196102　二叉树的性质 198103　树的表示 2001031　构建常规树 2001032　构建完全树 203104　树的遍历 2031041　前序遍历 2041042　中序遍历 2061043　后序遍历 2061044　广度优先遍历 2071045　遍历的应用 2071046　遍历的运行时间分析 208105　有序树 2081051　添加节点 2091052　查找节点 2101053　删除节点 211106　最小共同祖先 2121061　在有序树中查找最小共同祖先 2121062　使用指向父节点的指针 2131063　使用指向父节点的指针和深度字段 2141064　常规树 2141065　欧拉环游 2161066　所有节点对的最小共同祖先 217107　线索树 2171071　构建线索树 2181072　线索树的应用 220108　特殊的树算法 2211081　动物游戏 2211082　表达式求值 223109　区间树 2241091　构建区间树 2251092　与点相交 2261093　与区间相交 2261094　四叉树 2281095　字符串树 2311010　本章小结 2351011　练习题 235第11章　平衡树 239111　AVL树 2391111　添加值 2391112　删除值 240112　2-3树 2411121　添加值 2421122　删除值 242113　B树 2441131　添加值 2451132　删除值 245114　平衡树的变种 2461141　自顶向下的B树 2461142　B+树 247115　本章小结 248116　练习题 248第12章　决策树 250121　搜索博弈树 2501211　极小极大算法 2511212　初始移动和响应 2541213　博弈树启发式算法 254122　搜索常规决策树 2551221　优化问题 2561222　穷举搜索 2571223　分支定界搜索 2581224　决策树启发式算法 2591225　其他决策树问题 264123　群集智能 2671231　蚁群优化算法 2681232　蜂群算法 2681233　群集仿真 269124　本章小结 270125　练习题 271第13章　基本网络算法 274131　有关网络的术语 274132　网络的表示 276133　遍历 2781331　深度优先遍历 2781332　广度优先遍历 2801333　连通性测试 2811334　生成树 2821335　最小生成树 2831336　欧几里得最小生成树 2841337　构建迷宫 284134　强连通组件 2851341　Kosaraju算法 2851342　关于Kosaraju算法的讨论 286135　查找路径 2881351　查找任意路径 2881352　标签设置最短路径 2891353　标签修正最短路径 2911354　所有节点对的最短路径 292136　传递性 2951361　传递闭包 2951362　传递归约 296137　最短路径算法的改进 2981371　形状点 2981372　提前终止 2991373　双向搜索 2991374　最佳优先搜索 2991375　转弯惩罚和禁行 299138　本章小结 302139　练习题 302第14章　高级网络算法 304141　拓扑排序 304142　回路检测 306143　地图着色 3071431　双色地图 3071432　三色地图 3081433　四色地图 3091434　五色地图 3091435　其他地图着色算法 312144　最大流量 3121441　工作分配 3141442　最小流量切割 314145　网络克隆 3161451　字典 3161452　克隆引用 317146　节点团 3181461　暴力破解方法 3181462　Bron-Kerbosch算法 3191463　查找三角形节点团 323147　社区检测 3241471　极大节点团 3251472　Girvan-Newman算法 3251473　派系过滤法 326148　欧拉路径和欧拉回路 3261481　暴力破解方法 3271482　弗莱里算法 3271483　Hierholzer算法 327149　本章小结 3281410　练习题 329第15章　字符串算法 331151　匹配括号 3311511　算术表达式求值 332

算法是高效率编程的秘诀。算法用于描述如何排序记录、搜索数据项、计算诸如素数因子之类的数值、寻找街道路网中两点之间的最短路径，以及通过通信网络确定所允许的最大信息流。好算法和坏算法之间的区别在于：面对同一个问题，使用好算法可能意味着几秒就可以解决问题，而使用坏算法则需要几小时的时间，甚至永远解决不了问题。
研究算法有助于我们建立一个解决特定问题的实用方法工具包，同时可以帮助我们了解在不同的情况下哪些算法更有效，这样我们就可以选择最适合某个特定程序的算法。一个算法可能在一组数据上性能表现优越，但对于其他数据则性能表现糟糕。因此，了解如何选择最适合特定场景的算法十分关键。
更为重要的是，通过研究算法，我们可以学习解决问题的通用技巧并将其应用于其他问题，即使我们了解的所有算法中并不存在任何一个适合当前场景的算法。这些技巧可以让我们以不同的方式看待新问题，这样我们就可以创建属于自己的特定算法来解决问题，同时满足意想不到的需求。
学习和研究算法除了可以帮助我们解决实际工作中遇到的问题外，还可以帮助我们找到称心如意的职位。许多大型科技公司，例如微软、谷歌、雅虎、IBM，都希望程序员能够理解算法，并掌握相关的问题求解技术。在面试时，一些公司还会重点考察求职者的算法编程和解决逻辑问题的能力。
当然，好的面试官并不期望应聘者能够解决所有的难题。事实上，当应聘者没能解决难题的时候，他们可能会更好地了解应聘者。最好的面试官并不是想知道应聘者提供的答案，而是想看看应聘者如何处理一个不熟悉的问题。他们想看看应聘者在面试时是否会就此放弃并提出这个问题不适用于工作面试。或者，应聘者可以分析问题，并提出一个合理的推理路线，使用算法方法来解决问题。“天哪，我不知道。也许我会上网搜索”是一个糟糕的回答，而“似乎递归的分而治之方法可能奏效”是一个不错的回答。
本书是一本易于阅读的计算机算法入门教程，阐述了许多重要的经典算法，并指出不同算法所适用的场景。本书阐述了如何通过分析算法来理解算法的性能，最重要的是，本书将教授用于帮助读者自行创建新算法的技能。
本书描述的一些实用算法包括：
数值算法，例如随机化、因子分解、素数问题、数值积分。
常见数据结构的操作方法，例如数组、链表、树、网络。
高级数据结构的用法，例如堆、平衡树、B树。
排序和查找。
网络算法，例如最短路径、生成树、拓扑排序、流量计算。
本书阐述的通用问题求解技巧包括：
暴力算法或者穷举搜索算法
分而治之法
回溯法
递归法
分支定界法
贪婪算法和爬山算法
最低成本算法
限制范围
启发式算法
为了帮助读者掌握算法，本书提供了练习题。读者可以借助这些练习题来探索如何修改算法以适用于新的场景。练习也有助于读者掌握算法中的主要技术。
最后，本书还提供了读者在面试中可能遇到的一些算法问题的处理技巧。算法技巧可以帮助读者解决众多面试难题。即使读者不能使用算法技巧来解决每一个难题，也至少证明读者熟悉解决某些问题的方法。
为什么要研究算法
研究算法主要有以下几个原因。首先，算法提供了有用的工具，我们可以使用这些工具来解决特定的问题，例如排序或者查找最短路径。即使我们所采用的程序设计语言中包含直接采用某种算法来处理任务的工具，理解这些工具的工作原理也会有帮助。例如，理解数组和列表排序算法的工作原理，将有助于我们决定在程序中采用哪些适合的数据结构。
其次，算法也教授我们一些方法，以及如何将这些方法应用到其他具有相同数据结构的问题上。算法提供了一系列可以应用于其他问题的技术，如递归、分而治之、蒙特卡罗模拟、链表数据结构、网络遍历等，它们广泛适用于各种各样的问题。
再次，研究算法可以锻炼我们的大脑，这或许是最重要的原因。就像力量训练可以帮助足球运动员或者棒球运动员锻炼肌肉一样，研究算法可以培养我们解决问题的能力。职业运动员在比赛中可能不需要仰卧举重，类似地，程序员可能不需要在项目中实现简单的排序算法。然而，无论是参加体育比赛还是编写程序，多加练习都有助于提高我们的能力。
最后，研究算法具有很强的趣味性，可以使人获得满足感，有时还会令人喜出望外。当我将一堆数据存储到程序中，并渲染出一个真实的三维场景时，结果总是令我惊喜连连。即使经过几十年的研究，当一个特别复杂的算法产生了正确的结果时，我仍然能感受到胜利的喜悦。当所有的程序片段能够完美地结合起来解决一个特别具有挑战性的问题时，我感觉至少世界上有些事情是正确并且值得的。
算法的选择
本书选取的每一种算法都是基于以下一个或者多个原因：
该算法非常有用，经验丰富的程序员应该理解该算法的工作原理，以及如何在程序中正确使用该算法。
该算法展示了重要的算法编程技术，该技术可以应用于其他问题的求解过程。
该算法通常会被计算机科学专业的学生研究，因此该算法或其使用的技术可能会出现在技术面试中。
通过阅读本书并完成章末练习，读者将在算法技术方面打下良好的基础，并学会解决自己面临的程序设计问题。
读者对象
本书主要面向三类读者：专业程序员、正在为工作面试做准备的程序员、学习程序设计的学生。
专业程序员会发现，本书中描述的算法和技术有助于他们解决在工作中遇到的问题。即使读者遇到的问题不能使用本书中的算法直接解决，研究这些算法也会给读者提供全新的视角，从而帮助读者洞察问题，找到新的解决方案。
正在为工作面试做准备的程序员可以使用本书学习算法技巧。读者参加的面试中可能不会包括本书中描述的任何一个具体问题，但有可能包括十分相似的问题，因此读者可以使用在本书中学到的技巧来解决问题。即使不能完整地求解一个问题，但是只要读者能发现某个数据结构与算法中使用的数据结构相似，就可以提出类似的策略，这样也可以得到一定程度的加分。
基于前面阐述的原因，所有学习程序设计的学生都应该学习算法。本书阐述的基本都是简单、优雅和强大的算法，但这些算法并不都是十分常见的，所以读者自己并不一定会有什么偶然的机会去发现这些算法。递归法、分而治之法、分支定界法，以及如何使用众所周知的数据结构，对于任何对程序设计感兴趣的人而言都是不可或缺的知识。
注意：就我个人而言，我研究算法纯粹是为了享受！算法对我而言就等同于填字游戏或者数独游戏。我非常享受成功实现一个复杂的算法并观察其运行结果所带来的成就感！
在聚会上，算法也是不错的开场白：“对于标签设置和标签修正最短路径算法，请问您有何高见呢？”
如何充分利用本书
读者可以通过阅读本书来了解一些新的算法和技术，但是要想真正掌握这些算法，则需要切实使用它们。读者需要使用某种程序设计语言来实现算法。同时，还需要对算法进行试验和修正，并在旧问题上尝试算法的新变体。关于如何使用本书中的算法，本书中的练习题和面试问题可以为读者提供一些新方法。
为了充分利用本书，强烈建议读者使用最喜欢的程序设计语言实现尽可能多的算法，甚至采用多种程序设计语言实现算法，以了解不同程序设计语言对算法运行结果的影响。读者应该完成本书中的练习题，至少需要撰写解决练习题的纲要。最理想的情况是使用某种程序设计语言实现这些算法。书中的每一道练习题都有其被选中的原因，在仔细研究这些问题之前，读者可能不会意识到这一点。这些练习题可能会引导读者走上正确之路，路上趣味无穷，但限于篇幅，本书无法展开阐述。
最后，建议读者查阅一些互联网上的面试题，并尝试解决这些问题。在很多面试中，面试者并不需要真正给出解决方案，但是至少应该提出解题思路。当然，如果读者有足够的时间来给出解决方案，将会有更大的收获。
学习算法是一项需要实际动手操作的实践活动。读者应该勇于放下书本，使用编译器编写一些实际的代码！
本书网站
本书有两个网站：Wiley出版社的官网和作者本人的网站。这两个网站都包含本书的源代码。
本书Wiley出版社的官网地址为wwwwileycom/go/essentialalgorithms2e。读者也可以访问wwwwileycom，然后按书名或者书号（ISBN 978-1-119-57599-3）搜索本书并获取所有源代码。
C#程序采用帕斯卡命名法的大小写命名约定。例如，第9章练习题4中展示汉诺塔问题图形解决方案的程序名为GraphicalTowerOfHanoi。与之对应的Python程序则使用下划线小写命名规范，其对应的程序名为graphical_tower_of_hanoipy。
本书作者的网站地址为http://wwwCSharpHelpercom/algorithms2ehtml。
本书的组织结构
以下简要介绍本书的内容。
第1章阐述了分析算法时必须理解的基础概念，讨论了算法和数据结构之间的区别，引入了大O符号，并描述了各种实际考虑比理论运行时间计算更重要的情形。
第2章阐述了处理数值的几种算法，这些算法用于随机化数值和数组、计算最大公约数和最小公倍数、执行快速指数运算、判断一个数值是否是素数等。其中一些算法还涉及有关自适应数值积分算法和蒙特卡罗模拟的重要技术。
第3章阐述了链表数据结构，这些灵活的结构可以用来存储结构随时间增长、收缩和变化的列表。这些基本概念对于构建其他链接数据结构（例如树和网络）也很重要。
第4章阐述了特殊的数组算法和数据结构，例如三角矩阵和稀疏数组，它们可以节省程序时间和内存。
第5章阐述了让程序以先进先出（FIFO）或者后进先出（LIFO）的顺序存储和检索数据项的算法与数据结构。这些数据结构在其他算法中很有用，可以用于模拟真实场景，例如商店的结账队列。
第6章阐述了排序算法，展示了各种实用的算法技术。不同的排序算法适用于不同类型的数据，并且具有不同的理论运行时间，所以理解这些排序算法非常有好处。这些算法也是已知的具有精确理论性能边界的算法，因此特别值得研究。
第7章阐述了可以用来对排序列表进行搜索的算法，演示了二分查找算法和插值查找算法等重要技术。
第8章阐述了哈希表的数据结构。哈希表数据结构使用额外的内存，使程序能够非常快速地定位特定的数据项。哈希表充分展示了在许多项目中非常重要的时间和空间权衡策略。
第9章阐述递归算法，即自己调用自己的算法。有些问题具有自然递归属性，因此递归技术可以简化问题的求解。不幸的是，递归有时会导致问题，因此本章还描述了在必要时如何避免使用递归。
第10章阐述了高度递归的树数据结构，这些结构对于存储、操作和研究分层数据非常有用。树还可以在特殊场景中使用，例如求解算术表达式。
第11章阐述了随着时间的推移如何保持树的平衡性。通常，树结构会变得又高又细，这会破坏树算法的性能。平衡树通过确保树不会增长得太高和太细来解决这个问题。
第12章阐述试图解决可建模为一系列决策问题的算法。这些算法经常用于求解非常困难的问题，所以往往只给出近似解而非最优解。然而，这些算法具有很大的灵活性，因而可以被应用于各种各样的问题。
第13章阐述了基本网络算法，例如访问网络中的所有节点、检测网络中的回路、创建生成树和通过网络查找路径。
第14章阐述了高级网络算法，例如用于安排相关任务的拓扑排序、图着色、网络克隆、为员工分配工作等。
第15章阐述了操作字符串的算法，其中一些算法（例如搜索子字符串）内置于大多数程序设计语言中，不需要定制编程就可以直接使用。其他算法（例如括号匹配和查找字符串之间的差异）则需要一些额外的工作，同时也涉及一些有用的技术。
第16章阐述了如何对信息进行加密和解密，涵盖加密的基础知识，并描述了几种有趣的加密技术，例如维吉尼亚加密算法、分组加密算法和公开密钥加密算法。本章不涉及现代加密算法的所有细节，例如数据加密标准（DES）和高级加密标准（AES），因为这些加密算法更适合在专门讨论加密的书籍中阐述。
第17章阐述了计算机科学中最重要的两类问题：P问题（可以在确定的多项式时间内解决的问题）和NP问题（可以在不确定的多项式时间内解决的问题）。本章描述了这两类计算复杂性问题，并给出了验证一个问题属于P问题还是NP问题的方法，以及计算机科学中最深刻的问题—P问题是否等价于NP问题。
第18章阐述了在多个处理器上运行的算法。几乎所有的现代计算机都包含多个处理器，而且未来的计算机将包含更多的处理器，因此这些算法对于充分发挥计算机的潜能是不可或缺的。
第19章阐述了一些技巧和技术，可以用于攻克程序员面试过程中所遇到的难题。本章还包括一个网站列表，其中包含大量的面试题，读者可以用来练习。
附录包含各章末尾练习题的参考答案。
此外，为了帮助读者从书中获取更多的知识，并更好地理解书中的内容，本书设计了以下几种模块。
精彩的附加资料
包含额外的信息和主题。

警告：包含与上下文直接相关的信息，提醒读者必须牢记。
注意：包含与当前讨论内容相关的注解、技巧和提示等。
阅读本书的准备工作
为了阅读本书并理解算法，读者不需要任何特殊装备，只是可能需要眼镜和咖啡。然而，如果读者希望真正掌握本书的内容，则需要在实际的程序设计语言环境中实现尽可能多的算法。读者选择使用哪种程序设计语言并不重要。无论使用哪种程序设计语言实现算法细节，都将帮助读者更好地理解算法，以及掌握使用该特定语言所需的特定处理方法。
当然，如果读者打算使用某种程序设计语言实现算法，则需要一台计算机和相应的开发环境。
本书配套网站中包含一些示例代码，读者可以下载源代码，并使用Visual Studio 2017执行C#代码，或者使用Python 37执行Python代码。如果读者想运行这些程序，则需要在计算机上安装C# 2017或者Python 37，然后就可以正常运行这些程序了。
运行任何版本的Visual Studio都需要有一台速度较快的现代化计算机，并且配有大容量的硬盘和内存。例如，500GB的硬盘对我来说绰绰有余，况且硬盘的价格相对而言比较便宜，建议读者为自己的计算机购买并配置大一点的硬盘。
当然，读者可以在配置较低的系统上运行Visual Studio。但是，使用低配的计算机可能会使运行速度非常缓慢，其体验会令人沮丧。Visual Studio需要占用较多的内存，所以如果读者的计算机性能存在问题，可以考虑扩展内存容量。
使用免费的Visual Studio Community Edition可以运行本书提供的C#程序，因此不需要安装其他昂贵的Visual Studio版本。读者可以通过以下网址获取更多的信息并免费下载Visual Studio：https://visualstudiomicrosoftcom/downloads。
读者可以通过以下网址下载Python：https://wwwpythonorg/downloads/。Python 37或者更高版本应该能够运行本书的Python示例程序。除了在本地系统上安装Python外，还可以在云中运行。例如，Google Colaboratory（https://colabresearchgooglecom）是一个免费的环境，该云环境允许用户在任何Android设备上运行Python程序。
本书构建示例程序的系统环境是Windows 10，因此如果读者在其他平台（例如Linux、OS X或者云）上运行Python，可能会存在一些差异。遗憾的是，如果读者在其他平台环境中遇到问题，我就爱莫能助了，只能靠读者自己来解决问题。
算法的运行