1.本书的撰写有机结合了理论与实现，在讲授算法理论的同时也通过C#实例讲授了算法的实现。2.本书在内容上采取“广度优先”的组织思想，同时介绍了算法设计与分析中高级的部分。3.本书有机融合了算法与数据结构的知识，可以同时当做“算法设计与分析”和“数据结构与算法”两门课程的教材或参考书使用。特别地，本书还融入和面试相关的内容，使得本书特别适合作为算法相关工作面试的参考资料。

算法是使高效的程序成为可能的方法。它们解释了如何排列记录、搜索项、计算数值（比如质因子分解）、查找一个街道网络中的最短路径、确定可能通过通信网络的最大流。算法好坏的差别可能意味着是在一秒、一个小时内解决问题，还是永远也不能解决问题。
学习算法使你能建立有用的方法工具来解决具体的问题。它能帮助你理解在不同的情况下，哪个算法是最有效的，所以对于一个特定的问题，你就能选择最适合的算法。对某些数据而言性能优异的算法可能对其他的数据而言表现糟糕。所以知道如何选择一个最适合当前情况的算法是很重要的。
更重要的是，通过学习算法，你可以学习常规的问题解决技巧。即使你已知的任何算法都不能很好地适合当前的状况，你也可以把这些技巧应用到其他问题上。这些技巧让你从不同的角度看问题，使你能创造和分析自己的算法，从而解决你的问题，并且满足没有预料到的需求。
除了帮助你解决工作上的问题，这些技巧甚至会帮助你获得需要使用这些技巧的工作。许多大的科技公司，比如微软、谷歌、雅虎、IBM等公司都想要让他们的程序员理解算法和相关问题的解决技巧。其中，有些公司因为让面试者在面试中解决算法编程和逻辑难题而“臭名昭著”。
好的面试官不一定期待你解决每一个难题。事实上，当你没有解决某个难题时，他们可能会了解更多。最好的面试官想看到你如何处理一个不熟悉的问题，而不是想要看到答案。他们想看到你是举起双手说这个问题在面试中是不合理的，还是你分析了这个问题，并提出了一条有希望的推理来用算法解决这个问题。“天哪，我不知道。或许我要上网搜一下”将会是一个坏的答案。“看起来一个递归的分治法可能有用”将会是一个好得多的答案。
这是一本易读的计算机算法导论书。它描述了一些重要的传统算法，并且说明了每一个算法在什么时候是适合的。它解释了如何分析算法从而理解它们的行为。最重要的，它教会了你创造自己新算法的技巧。
这里是本书中描述的一些有用的算法：
数值算法，比如随机化、分解因式、处理质数、数值积分
熟练操作常见数据结构的方法，比如堆、树、平衡树、B树
排序和搜索
网络算法，比如最短路径、生成树、拓扑排序和流计算
这里是本书中解释的一些常规的问题解决技巧：
暴力或者穷举搜索
分治法
回溯法
递归
分支界限
贪心算法和爬山法
最小花费算法
缩小范围
启发式算法
为了帮助读者掌握这些算法，本书提供了一些练习，读者可以利用它们来探索自己的方法，以便修改书中的算法并把它们应用到新的情况中。这些练习也会帮助你巩固算法中的主要技巧。
最后，本书包含了解决面试中可能遇到的算法问题的技巧。算法技巧会让你解决许多面试中的难题。即使你不能用算法技巧解决每一个难题，至少表明你熟悉这些方法并且能用它们解决其他的问题。
算法选择
本书中的每一个算法都是因为一个或多个下列原因而被选择的：
这个算法是有用的，并且有经验的程序员应该能理解它如何工作以及如何在程序中使用它。
这个算法展示了你可以应用到其他问题中的重要算法编程技巧。
计算机科学专业的学生普遍学习这个算法，所以这个算法或者它使用的技巧可能出现在一个技术性面试中。
当读者读完本书并做完练习后，将会有一个好的算法基础并掌握解决自己编程问题的技巧。
本书的目标人群
本书主要针对三种读者：专业程序员、准备面试的程序员和学习编程的学生。
专业程序员将会发现本书中所描述的算法和技巧对于解决他们工作中遇到的难题是很有用的。即使遇到无法直接用书中的算法解决的问题，阅读本书中的算法也会让你从新的角度观察问题，从而发现新的解决办法。
准备工作面试的程序员可以使用本书来磨炼他们的算法技巧。你的面试可能不会包括书中描述的任何问题，但是可能包含一些足够相似的问题。你可以用从本书中学到的技巧解决它们。
学习编程的学生应该学习这些算法。本书中描述的许多方法是简单、富有魅力而且有效的。但是它们并不都是十分显而易见的，所以你不一定会在偶然间自己发现它们。递归、分治、分支界限等技巧，还有使用众所周知的数据结构，这些对任何有兴趣编程的人都是十分需要掌握的。
注　就我个人而言，算法只是一种乐趣，它们就像填字游戏或者数独一样。我喜欢组成一个复杂的算法，倒一些数据进去，然后看到一个美丽的三维图形、一条匹配一系列点的曲线，或者一些其他的优雅的答案出现。我喜欢这种感觉。
充分运用本书
仅仅是阅读本书，就能学到一些新的算法和技巧。但是要真正掌握这些算法体现出的方法，就需要用它们工作，需要用某种编程语言实现它们。你还需要实验、修改这些算法，尝试旧问题的新变型。本书中的练习和面试问题能让你想到使用这些算法中技巧的新方法。
为了从本书中得到最大的收获，我强烈推荐用一种你最喜欢的语言实现尽可能多的算法。甚至用多种语言来实现，看看不同的语言是如何影响问题实现的。你应该研究这些练习并至少写下解决它们的提纲。理想状况下，你也应该实现它们。通常一个练习被编入本书是有原因的，你可能需要认真审视这个问题，才能发现这个原因。
最后，看看网上的一些面试问题，然后弄明白你将如何解决它们。在许多面试中，可能不会要求你实现一个解决方案，但是你应该能勾勒出大体的解决方案。如果你有时间实现解决方案，你将会学到更多。
理解算法是一个实践问题。不要害怕放下书，打开一个编译器，写一些真正的代码吧。
本书的网站
其实，本书有两个网站：Wiley的版本和我的版本。每一个网站都包含了本书的源代码。
Wiley的网址是http://www.wiley.com/go/essentialalgorithms。你也可以去http://www.wiley.com通过书名或ISBN来搜索这本书。一旦找到了这本书，可以点击“下载”（Downloads）标签来获取本书的所有源代码。一旦下载了这些代码，只需要用你喜欢的压缩工具解压它们即可。
注　在Wiley的网站，你可能会发现用ISBN搜索更容易。本书的ISBN是978-1-118-61210-1。
要想在我的网站上找到这本书，请登录http://www.CSharpHelper.com/algorithms.html。
本书的结构
这一部分介绍了本书的详细内容。
第1章　解释了分析算法中必须理解的概念。其中讨论了算法与数据结构之间的不同，引入了大O符号，并介绍了当实际因素比理论运行时间计算更重要时的时间问题。
第2章　解释了几个处理数值的算法。这些算法用于随机化数字和数组，计算最大公约数和最小公倍数，快速求幂，判断一个数字是否为质数。一些算法还引入了自适应求积和蒙特卡罗模拟这些重要的技巧。
第3章　解释了链表数据结构。这种灵活的结构可以用来存储随时间增长的列表。这些基础概念对于建立其他的链接数据结构，比如树和网络，也是很重要的。
第4章　解释了特殊的数组算法和数据结构，比如节省程序时间和存储空间的三角形数组和稀疏数组。
第5章　解释了让一个程序以先进先出（FIFO）和后进先出（LIFO）的顺序存储和取出元素的算法及数据结构。这些数据结构对于其他算法很有用。它们也可以用来模拟现实世界中的场景，比如在商店中排队结账。
第6章　解释了排序算法。这些算法展示了有用的算法技巧。不同的排序算法适应于不同种类的数据，并且有不同的理论运行时间，所以理解这些算法的特点是很有好处的。这些也是为数不多理论性能界限已知的算法，所以研究它们特别有趣。
第7章　解释了程序可以用来搜索有序列表的方法。这些算法展示了重要的技巧，比如说二分法和插值法。
第8章　解释了散列表—使用额外的存储空间来使一个程序快速查找特定元素的数据结构。它们有力地展示了时间与空间的权衡在许多程序中的重要性。
第9章　解释了递归算法—调用其自身的算法。递归技巧使某些算法更容易理解和实现，虽然它们有时会导致问题。所以这一章也介绍了当必要时如何从一个算法中移除递归。
第10章　解释了高度递归的树这一数据结构。它对于存储、操作和学习分层数据很有用，并且可以应用在意想不到的地方，比如求算术表达式的值。
第11章　解释了在自身随着时间增长时保持平衡的树。一般来说，树结构会变得很高很瘦，并且那将破坏树算法的性能。平衡树通过确保树不变得太高太瘦而解决这个问题。
第12章　解释了尝试解决可以被建模为一系列决策的问题的算法。这些算法通常在解决非常困难的问题中使用，所以它们一般只找到近似解而不是可能的最优解。然而，它们是非常灵活的，并且可以被应用到范围很广的问题中。
第13章　解释了基础网络算法，比如访问一个网络中的所有结点、检测循环、创建生成树、查找网络中的路径。
第14章　解释了更多的网络算法，比如用拓扑排序来安排相关的任务、地图着色、网络克隆、向雇员分配任务。
第15章　解释了操作字符串的算法。这些算法中的一部分，比如搜索子串，被内置为工具。大多数编程语言都可以直接使用它们，而不用自己编程。其他的算法，比如括号匹配和查找字符串差异，要求额外做一些工作，而且也展示了一些有用的技巧。
第16章　解释了如何加密和解密信息。其中涵盖了加密基础和几个有趣的加密技巧，比如 Vigenère密码、分组密码和公钥加密。这一章没有叙述所有的特定加密算法的细节，比如DES（数据加密标准）和AES（高级加密标准），因为它们更适合在一本加密的专著中介绍。
第17章　解释了计算机科学中最重要的两类问题：P（可以在多项式时间内解决的问题）和NP（不能在多项式时间内解决的问题）。这一章介绍了这些类别，证明一个问题属于P还是NP，还有计算机科学中最深刻的问题：P等于NP吗？
第18章　解释了在多处理器上运行的算法。几乎所有的现代计算机都包含着多处理器，并且未来的计算机将会包含更多，所以这些算法对于最有效地利用一台计算机的潜在能力至关重要。
第19章　介绍了一些窍门和技巧，读者可以用它们来攻克编程面试中可能遇到的难题和挑战。这章还包括一个网站列表，这些网站上有大量读者可以用作练习的难题。
附录A　总结了本书中算法使用的观点和策略，使读者可以解决这里的算法没有明确涵盖的其他问题。
附录B　包含每章末练习的解答。
使用本书需要的知识
读者不需要任何特殊的知识就能阅读本书和理解书中的算法。然而，如果读者真的想掌握这些知识，应该用某种实际的编程语言尽可能多地实现算法。用任何语言完成算法的具体实现将会帮助读者更好地理解算法的细节和语言要求的特殊处理方法。
当然，如果读者打算使用一种编程语言实现算法，需要配备合适的开发环境。
本书的网站上提供了在Visual Studio 2012中用 C#编写的实现实例，读者可以下载并考查它们。如果想运行那些程序，需要在一台能很好运行Visual Studio的计算机上安装C# 2012。
运行任何版本的Visual Studio，都要求你有一台相当快的、有大的硬盘和内存的现代计算机。例如，我很高兴我的计算机有2GB内存、500GB硬盘、1.83GHz的Intel Core 2系统。硬盘空间比我需要的大许多，但是硬盘相对便宜，为什么不买大的呢？
读者可以在一台功能不是很强大的计算机上运行Visual Studio，但是使用功能不强的计算机会非常缓慢且令人沮丧。Visual Studio会占用很大的内存，所以，如果计算机遇到了性能问题，安装更多的内存可能会有帮助。
这些程序将会用C# Express Edition 载入和执行，所以没有必要安装更贵的C#版本。你可以在http://www.microsoft.com/visualstudio/eng/downloads#d-express-windows-desktop上获得C# Express Edition的更多信息并下载C#。
约定
为了帮读者充分利用本书，并了解正在发生的事情，我在本书中使用了几个约定。
漂亮的边框
像这样的边框包含着更多的信息和副主题。

注　像这样的格式有注释、指导、提示、技巧和当前讨论的旁白。
至于文本中的样式：
新的术语和重要的词语在被引入时表示为楷体。
击键操作，比如Ctrl＋A，意味着先按住Ctrl键再按A键。
文本中的URL和电子邮件地址用斜体表示，比如http://www.CSharpHelper.com和 RodStephens@CSharpHelper.com。
给我发电子邮件
如果你有任何疑问、意见或建议，请随时给我发电子邮件至RodStephens@CSharpHelper.com。我不能保证解决你所有的算法问题，但我一定尽力为你指明正确的方向。
致谢
感谢Bob Elliott、Tom Dinse、Gayle Johnson和Daniel Scribner，是他们的努力使本书得以出版。同时感谢技术编辑George Kocur、Dave Colman和Jack Jianxiu Hao，他们的帮助确保了本书中的信息尽可能准确。

计算机\算法

[美]罗德?斯蒂芬斯（Rod Stephens）著：
罗德•斯蒂芬斯（Rod Stephens） Microsoft Visual Basic 最有价值专业人员，并且一直在ITT Technical Institute教授编程入门课程。作为一位获奖导师，他定期进行大会报告并且已经撰写了26本书，这些书已经被翻译成近20种语言出版。他还在杂志上撰写了超过250篇的文章，内容涵盖了C#、Visual Basic、Delphi和Java。

王宏志 黎玲利 译：暂无简介

算法的修养对计算机从业者来说至关重要，这种重要性不仅仅体现在计算机科学的研究中，也体现在软件开发的过程中，可以说开发一款优秀软件离不开高效的算法。因此，算法知识成为面试过程中的必考知识。正是由于其重要性，各出版社出版了林林总总的算法设计与分析教材和参考书。
和目前的算法教材相比，本书有着如下鲜明的特征：
第一，本书的撰写有机结合了理论与实现。算法是一门理论性很强的课程，这也使得传统的算法教材中较少有算法实现。本书则不同，在讲授算法理论的同时，也通过C#实例讲授了算法的实现，并且既有理论方面的习题，也有程序设计方面的习题。
第二，本书在内容上采取“广度优先”的组织思想，不仅讲授了基础的算法和数据结构知识，如数值算法、排序、搜索、链表、树算法、图算法，也介绍了算法设计与分析中的高级部分，如密码算法、计算复杂性理论、分布式算法等，这让读者阅读此书就能掌握多种不同的算法与数据结构。
第三，本书有机地融合了算法与数据结构的知识，可以同时当作“算法设计与分析”和“数据结构与算法”两门课程的教材或参考书使用。特别地，本书还融入和面试相关的内容，使得本书特别适合作为相关工作面试的参考资料。
译者应机械工业出版社的要求对本书进行了翻译。由于水平有限，而且翻译要求的时间紧张，译文中一定存在许多不足，在此敬请各位同行专家学者和广大读者批评指正，欢迎大家将发现的错误或提出的意见与建议发送到邮箱 wangzh@hit.edu.cn，以便将来改进本书的译本。
我要感谢哈尔滨工业大学的李沅泽、刘奇、樊昱才、张晓凯、魏思达、魏龑、董乐天、马靖昆、王必聪、季文骢、唐帮盈、司傲然、徐时雨、高桥、杨树佳、时春香、米尔根 "紫帕、周舒妍、任雪健、韩雍博、陆鑫、罗嘉瑞、道发发、马常青、李宁、赵世琦、妥明翔、万晓珑、孙彤等同学参加了翻译工作。在完成译稿之后，哈尔滨工业大学的巢泽敏同学阅读全文并且对译稿提出了很多有益的意见，在此也表示感谢。同时感谢机械工业出版社的姚蕾编辑和朱劼编辑，由于她们的信任和支持，本书的翻译工作才得以顺利进行。

王宏志　黎玲利
2016年8月10日于哈尔滨

出版者的话
译者序
前言
第1章　算法基础知识1
1.1　方法1
1.2　算法和数据结构2
1.3　伪代码2
1.4　算法的特点4
1.4.1　大O符号5
1.4.2　常见的运行时间函数7
1.4.3　可视化函数12
1.5实际因素12
1.6　总结13
练习13
第2章　数值算法16
2.1　随机化数据16
2.1.1　随机数生成16
2.1.2　随机化数组20
2.1.3　生成不均匀分布21
2.2　寻找最大公约数21
2.3　求幂运算23
2.4　有关素数的运算24
2.4.1　寻找素数因子24
2.4.2　寻找素数26
2.4.3素性测试27
2.5　进行数值积分28
2.5.1　矩形规则28
2.5.2梯形规则29
2.5.3　自适应求积30
2.5.4　蒙特卡罗积分32
2.6　查找零32
2.7　总结34
练习34
第3章　链表36
3.1　基本概念36
3.2　单链表37
3.2.1　遍历链表37
3.2.2　查找单元格37
3.2.3　使用哨兵38
3.2.4　在开头添加单元格39
3.2.5　在结尾添加单元格40
3.2.6　在某个单元格后插入单元格40
3.2.7　删除单元格41
3.3　双向链表42
3.4　有序链表43
3.5　链表算法44
3.5.1　复制链表44
3.5.2　链表的插入排序45
3.6　链表的选择排序46
3.7　多线程链表47
3.8　循环链表48
3.8.1　标记单元格49
3.8.2　使用散列表50
3.8.3　链表回溯51
3.8.4　反转链表51
3.8.5　乌龟和兔子53
3.8.6　双向链表中的循环问题55
3.9　总结55
练习55
第4章　数组57
4.1　基本概念57
4.2　一维数组58
4.2.1　查找元素58
4.2.2　查找最大值、最小值、平均值59
4.2.3　插入元素60
4.2.4　移除元素61
4.3　非零下界61
4.3.1　二维数组61
4.3.2　多维数组62
4.4　三角形数组64
4.5　稀疏数组66
4.5.1　找到行或列67
4.5.2　获取值68
4.5.3　设置值69
4.5.4　删除值71
4.6　矩阵72
4.7　总结74
练习74
第5章　栈和队列76
5.1　栈76
5.1.1　栈的链表实现76
5.1.2　栈的数组实现77
5.1.3　双向栈78
5.1.4　栈的算法79
5.2　队列84
5.2.1　队列的链表实现84
5.2.2　队列的数组实现85
5.2.3　专用队列86
5.3　总结87
练习87
第6章　排序89
6.1　时间复杂度为O(N2)的算法89
6.1.1　数组中的插入排序89
6.1.2　数组中的选择排序90
6.1.3　冒泡排序91
6.2　时间复杂度为O(N log N)的算法93
6.2.1　堆排序93
6.2.2　快速排序98
6.2.3　归并排序103
6.3　时间复杂度为亚O(N log N)的算法105
6.3.1　计数排序106
6.3.2　桶排序107
6.4　总结108
练习108
第7章　搜索110
7.1　线性搜索110
7.2　二分搜索111
7.3　插值搜索112
7.4　总结113
练习113
第8章　散列表114
8.1　散列表的基础知识114
8.2　链115
8.3　开放寻址116
8.3.1　删除记录117
8.3.2　线性探测118
8.3.3　二次探测119
8.3.4　伪随机探测120
8.3.5　双散列120
8.3.6　有序散列121
8.4　总结122
练习123
第9章　递归125
9.1　基础算法125
9.1.1　阶乘125
9.1.2　斐波那契数127
9.1.3　汉诺塔128
9.2　图算法130
9.2.1　科赫曲线130
9.2.2　希尔伯特曲线131
9.2.3　谢尔宾斯基曲线132
9.2.4　垫片134
9.3　回溯算法134
9.3.1　八皇后问题136
9.3.2　骑士巡游138
9.4　选择与排列140
9.4.1　循环选择140
9.4.2　重复选择141
9.4.3　不重复选择142
9.4.4　元素可重复的排列143
9.4.5　元素不重复的排列144
9.5　消去递归145
9.5.1　尾递归的消除145
9.5.2　存储中间值146
9.5.3　一般递归的消除148
9.6　总结150
练习151
第10章　树153
10.1　树的术语153
10.2　二叉树属性155
10.3　树的表示157
10.3.1　建立树的通用方法157
10.3.2　构造完全树159
10.4　树的遍历160
10.4.1　前序遍历160
10.4.2　中序遍历162
10.4.3　后序遍历163
10.4.4　深度优先遍历164
10.4.5　遍历的运行时间164
10.5　排序树 165
10.5.1　添加结点165
10.5.2　查找结点166
10.5.3　删除结点167
10.6　线索树168
10.6.1　建立线索树169
10.6.2　使用线索树171
10.7　特化树算法172
10.7.1　动物游戏172
10.7.2　表达式求值173
10.7.3　四叉树175
10.7.4　Trie树179
10.8　总结182
练习182
第11章　平衡树185
11.1　AVL树185
11.1.1　添加值185
11.1.2　删除值187
11.2　2-3树187
11.2.1　添加值188
11.2.2　删除值189
11.3　B树191
11.3.1　添加值191
11.3.2　删除值192
11.4　平衡树变体193
11.4.1　自上而下的B树193
11.4.2　B+树193
11.5　总结194
练习195
第12章　决策树196
12.1　游戏搜索树196
12.1.1　极小化极大值算法197
12.1.2　初始步骤和反应199
12.1.3　启发式游戏树200
12.2　搜索通用决策树201
12.2.1　优化问题202
12.2.2　穷举搜索202
12.2.3　分支界限203
12.2.4　决策树的启发式搜索205
12.2.5　其他决策树问题209
12.3　总结212
练习195
第13章　基本网络算法214
13.1　网络术语214
13.2　网络的表示方法216
13.3　网络的遍历218
13.3.1　深度优先遍历218
13.3.2　广度优先遍历220
13.3.3　连通性测试221
13.3.4　生成树223
13.3.5　最小生成树224
13.4　寻找路径225
13.4.1　寻找任一路径225
13.4.2　标签设置最短路径225
13.4.3　标签校正最短路径227
13.4.4　任意两点间最短路径228
13.5　总结232
练习232
第14章　更多的网络算法234
14.1　拓扑排序234
14.2　回路检测236
14.3　地图着色237
14.3.1　两色着色237
14.3.2　三色着色238
14.3.3　四色着色 239
14.3.4　五色着色239
14.3.5　其他地图着色算法241
14.4　最大流242
14.4.1　工作分配243
14.4.2　最小割244
14.5　总结245
练习246
第15章　字符串算法247
15.1　括号匹配247
15.1.1　求算术表达式248
15.1.2　构建解析树248
15.2　模式匹配249
15.2.1　DFA249
15.2.2　为正则表达式建立DFA251
15.2.3　NFA252
15.3　字符串搜索253
15.4　计算编辑距离256
15.5　总结258
练习258
第16章　密码学260
16.1　术语260
16.2　换位密码261
16.2.1　行/列换位261
16.2.2　列换位262
16.2.3　路由加密算法263
16.3　替换密码264
16.3.1　凯撒替换264
16.3.2　维吉尼亚密码265
16.3.3　简单替换密码266
16.3.4　一次性密码本266
16.4　分组密码267
16.4.1　代换-置换网络267
16.4.2　Feistel密码268
16.5　公钥加密和RSA269
16.5.1　欧拉函数270
16.5.2　在取模运算下的乘法逆元素270
16.5.3　一个RSA的例子270
16.5.4　现实思考271
16.6　加密技术的其他用途271
16.7　总结272
练习273
第17章　复杂性理论274
17.1　符号274
17.2　复杂性分类275
17.3　归约277
17.3.1　3SAT278
17.3.2　二分图匹配278
17.4　NP难问题279
17.5　检测、报告和优化问题279
17.5.1　检测≤p报告279
17.5.2　报告≤p优化280
17.5.3　报告≤p检测280
17.5.4　优化≤p报告280
17.6　NP完全问题281
17.7　总结282
练习283
第18章　分布式程序设计284
18.1　并行的种类284
18.1.1　脉动阵列284
18.1.2　分布式计算286
18.1.3　多CPU的处理287
18.1.4　竞争条件287
18.1.5　死锁290
18.1.6　量子计算291
18.2　分布式算法291
18.2.1　调试分布式算法292
18.2.2　高度并行算法292
18.2.3　归并排序293
18.2.4　哲学家进餐294
18.2.5　两个将军问题296
18.2.6　拜占庭将军297
18.2.7　一致性298
18.2.8　领导人选举301
18.2.9　快照301
18.2.10　时钟同步302
18.3　总结303
练习303
第19章　面试难题305
19.1　面试难题提问306
19.2　面试难题回答307
19.3　总结309
练习311
附录A　算法概念综述312
附录B　练习解答320
索引371