本书的撰写有机结合了理论与实现，在讲授算法理论的同时也通过C#实例讲授了算法的实现。通过描述并分析一些重要的传统算法，从而理解它们并且了解每一个算法在什么时候使用较为适合，通俗易懂地教授读者创造自己的算法的技巧。这些技巧让读者能从不同的角度看问题，建立有用的方法工具，从而解决实际问题，抑或从容面对面试难题。本书适合当作“算法设计与分析”和“数据结构与算法”两门课程的教材或参考书使用。特别是本书还融入和面试相关的内容，因此适合作为算法相关工作面试的参考资料。

作者简介

Rod Stephens初是一名数学家，但是在麻省理工学院进修时，他喜欢上了算法和编程，并且从此以后走上了专业编程的道路。作为一位获奖导师，他经常在各种技术大会上讲演，并已写了26本技术图书，被翻译为多国语言出版。

Essential Algorithms: A Practical Approach to Computer Algorithms
出版者的话
译者序
前言
第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

精彩书摘

　　《算法基础》：
　　16.3.3 简单替换密码
　　在简单替换密码中，每个字母只有一个固定的对应字母。例如，用H代替A，J代替B，C代替X，等等。
　　在这种密码中，密钥是一组明文字母到密文字母的映射。如果信息中只包含A到Z的字母，一共有4.0*1026种可能的映射。
　　如果手动加密解密，很好将映射表写下来。
　　如果使用电脑，就可以使用伪随机数发生器来重置映射。发信者选取一个数字K，并用它初始化伪随机数发生器，然后用这个发生器随机打乱A到Z的字母来生成一组映射。然后值K就成为了密钥，接受者以相同的步骤，用K初始化生成器后，就能生成出发信人使用的映射了。
　　记住一个数字比记住一整组映射要简单得多。但是大部分随机数生成器中可能的内置状态数远小于4.0*1026。举例来说，如果用一个带符号的整数初始化一个随机数生成器，这个整数最多只可能有约二十亿个不同的值，这个数字依旧很大，但是电脑可以轻易地枚举出所有可能的二十亿个值，看看哪个值产生的映射可以破解出有效的单词。
　　……

前言/序言

　　EssentialAlgorithms:APracticalApproachtoComputerAlgorithms算法是使高效的程序成为可能的方法。它们解释了如何排列记录、搜索项、计算数值（比如质因子分解）、查找一个街道网络中的最短路径、确定可能通过通信网络的最大流。算法好坏的差别可能意味着是在一秒、一个小时内解决问题，还是永远也不能解决问题。

　　学习算法使你能建立有用的方法工具来解决具体的问题。它能帮助你理解在不同的情况下，哪个算法是最有效的，所以对于一个特定的问题，你就能选择最适合的算法。对某些数据而言性能优异的算法可能对其他的数据而言表现糟糕。所以知道如何选择一个最适合当前情况的算法是很重要的。

　　更重要的是，通过学习算法，你可以学习常规的问题解决技巧。即使你已知的任何算法都不能很好地适合当前的状况，你也可以把这些技巧应用到其他问题上。这些技巧让你从不同的角度看问题，使你能创造和分析自己的算法，从而解决你的问题，并且满足没有预料到的需求。

　　除了帮助你解决工作上的问题，这些技巧甚至会帮助你获得需要使用这些技巧的工作。许多大的科技公司，比如微软、谷歌、雅虎、IBM等公司都想要让他们的程序员理解算法和相关问题的解决技巧。其中，有些公司因为让面试者在面试中解决算法编程和逻辑难题而“臭名昭著”。

　　好的面试官不一定期待你解决每一个难题。事实上，当你没有解决某个难题时，他们可能会了解更多。最好的面试官想看到你如何处理一个不熟悉的问题，而不是想要看到答案。他们想看到你是举起双手说这个问题在面试中是不合理的，还是你分析了这个问题，并提出了一条有希望的推理来用算法解决这个问题。“天哪，我不知道。或许我要上网搜一下”将会是一个坏的答案。“看起来一个递归的分治法可能有用”将会是一个好得多的答案。

　　这是一本易读的计算机算法导论书。它描述了一些重要的传统算法，并且说明了每一个算法在什么时候是适合的。它解释了如何分析算法从而理解它们的行为。最重要的，它教会了你创造自己新算法的技巧。

　　这里是本书中描述的一些有用的算法：

　　数值算法，比如随机化、分解因式、处理质数、数值积分熟练操作常见数据结构的方法，比如堆、树、平衡树、B树排序和搜索网络算法，比如最短路径、生成树、拓扑排序和流计算这里是本书中解释的一些常规的问题解决技巧：

　　暴力或者穷举搜索分治法回溯法递归分支界限贪心算法和爬山法最小花费算法缩小范围启发式算法为了帮助读者掌握这些算法，本书提供了一些练习，读者可以利用它们来探索自己的方法，以便修改书中的算法并把它们应用到新的情况中。这些练习也会帮助你巩固算法中的主要技巧。

　　最后，本书包含了解决面试中可能遇到的算法问题的技巧。算法技巧会让你解决许多面试中的难题。即使你不能用算法技巧解决每一个难题，至少表明你熟悉这些方法并且能用它们解决其他的问题。

　　算法选择本书中的每一个算法都是因为一个或多个下列原因而被选择的：

　　这个算法是有用的，并且有经验的程序员应该能理解它如何工作以及如何在程序中使用它。

　　这个算法展示了你可以应用到其他问题中的重要算法编程技巧。

　　计算机科学专业的学生普遍学习这个算法，所以这个算法或者它使用的技巧可能出现在一个技术性面试中。

　　当读者读完本书并做完练习后，将会有一个好的算法基础并掌握解决自己编程问题的技巧。

　　本书的目标人群本书主要针对三种读者：专业程序员、准备面试的程序员和学习编程的学生。

　　专业程序员将会发现本书中所描述的算法和技巧对于解决他们工作中遇到的难题是很有用的。即使遇到无法直接用书中的算法解决的问题，阅读本书中的算法也会让你从新的角度观察问题，从而发现新的解决办法。