本节书摘来自异步社区《编程珠玑（第2版•修订版）》一书中的附录A 算法分类，作者【美】Jon Bentley，更多章节内容可以访问云栖社区“异步社区”公众号查看。

附录A 算法分类
编程珠玑（第2版•修订版）
本书涵盖了大学算法课中的许多内容，但侧重点不同——我们更强调应用和编码，而不强调数学分析。本附录将有关内容组织成更标准的提纲形式。

A.1　排序
问题定义。输出序列是输入序列的一个有序排列。如果输入是文件，则输出通常是另一个文件；如果输入是数组，则输出通常还是该数组。

应用。本列表仅表明了排序应用的多样性。

输出需求。有些用户需要得到有序的输出，例如1.1节所考虑的电话号码簿及月对账单；而二分搜索等函数的实现则要求有序的输入。
收集相同的项。程序员利用排序来收集相同的项：2.4节和2.8节的变位词程序收集同一变位词类中的单词，15.2节和15.3节的后缀数组收集相同的文本短语，其他例子见习题2.6、习题8.10和习题15.8。
其他应用。2.4节和2.8节的变位词程序将字母表顺序作为单词中字母的规范顺序，并进而将它作为变位词类的标识；习题2.7通过排序重新组织磁带上的数据。
通用函数。下列算法对任意n元序列进行排序。

插入排序。11.1节的程序对于最坏情况下的随机输入，运行时间为O(n2)。该节用表格给出了多个程序变体的具体运行时间。11.3节使用插入排序在O(n)时间内对一个本来就几乎有序的数组进行了排序。插入排序是本书中唯一稳定的排序算法：具有相同关键字的元素在输出序列和输入序列中的相对顺序保持不变。
快速排序。11.2节的简单快速排序算法在具有n个不同元素的数组上运行需要O(n log n)的时间。该算法是递归的，平均情况下需要对数大小的栈空间，最坏情况下需要O(n2)的时间和O(n)的栈空间。该算法对于所有元素都相同的数组，运行时间为O(n2)；11.3节的改进版本对任意数组的平均运行时间均为O(n log n)，该节表格中给出了几种具体实现的运行时间经验数据。C标准库函数qsort通常用本算法实现，本书的2.8节、15.2节、15.3节和答案1.1用到了该库函数。C++标准库函数sort通常也使用本算法，11.3节给出了该库函数的平均运行时间。
堆排序。14.4节的堆排序在任意n元数组上的运行时间都是O(n log n)。该算法不是递归的，且仅使用了固定大小的额外空间。答案14.1和14.2描述了更快的堆排序。
其他排序算法。1.3节介绍的归并排序算法对文件排序非常有效，习题14.4.d概述了一种归并算法。答案11.6给出了选择排序和希尔排序的伪代码。
答案1.3给出了几种排序算法的运行时间。

专用函数。这些函数能够在特定的输入上得到简短有效的程序。

基数排序。习题11.5中McIlroy的位串排序能够推广为在更大的字母表（例如字节）上对字符串进行排序。
位图排序。1.4节的位图排序利用到了如下事实：待排序的整数通常在小范围内，无重复元素也没有多余数据。答案1.2、1.3、1.5和答案1.6描述了实现细节和扩展。
其他排序。1.3节的多遍排序多次读取输入文件，用时间换取空间。第12章和第13章生成了随机整数的有序集合。
A.2　搜索
问题定义。搜索函数判断其输入是否为给定集合的成员，可能还要检索相关的信息。

应用。习题2.6中，Lesk的程序通过搜索电话号码簿，将（编码后的）姓名转换为电话号码。10.8节中Thompson的残局程序通过搜索棋盘来计算最优的走法。13.8节中McIlroy的拼写检查器通过搜索字典来判断单词是否拼写正确。其他应用跟函数一起介绍。

通用函数。下列算法对任意n元集合进行搜索。

顺序搜索。9.2节给出了在数组中进行顺序搜索的简单版本和调优版本。13.2节给出了数组和链表中的顺序搜索。本算法可用于给单词添加连字符（习题3.5）、平滑地理数据（9.2节）、表示稀疏矩阵（10.2节）、生成随机集合（13.2节）、存储压缩的字典（13.8节）、装箱问题（习题14.5）以及查找所有相同的文本短语（15.3节）。第3章的简介和习题3.1描述了两种比较愚蠢的顺序搜索实现。
二分搜索。2.2节介绍了这个大约需要log2n次比较来搜索一个有序数组的算法，相应的代码在4.2节给出。9.3节扩展了代码以查找许多相同项的首次出现，并对代码的性能进行了调优。算法的应用包括在预订系统（2.2节）、错误的输入行（2.2节）、输入单词的变位词（习题2.1）、电话号码（习题2.6）、线段交点的位置（习题4.7）、稀疏数组中项的索引（答案10.2）、随机整数（习题13.3）和短语（15.2节和15.3节）中搜索记录。习题2.9和习题9.9讨论了二分搜索和顺序搜索之间的折中。
散列。习题1.10对电话号码进行了散列，习题9.10对一组整数进行了散列，13.4节用箱对一组整数进行了散列，13.8节对字典中的单词进行了散列，15.1节通过散列方法对文档中的单词进行了计数。
二分搜索树。13.3节使用（非平衡的）二分搜索树来表示一组随机整数。通常用平衡树实现C++标准模板库中的set模板，我们在13.1节、15.1节和答案1.1中都用到了set模板。
专用函数。这些函数能够在特定的输入上得到简短有效的程序。

关键字索引。一些关键字可以用作数组的索引。13.4节的箱和位向量都使用整数关键字作为索引。用作索引的关键字包括电话号码（1.4节）、字符（答案9.6）、三角函数的参数（习题9.11）、稀疏数组的索引（10.2节）、程序计数器的值（习题10.7）、棋盘（10.8节）、随机整数（13.4节）、字符串的散列值（13.8节）和优先级队列中的整数值（习题14.8）。习题10.5利用关键字索引和数值函数节省了空间。
其他方法。9.1节描述了如何通过将常用元素保存在高速缓存中来减少搜索时间，10.1节描述了在理解问题背景的基础上简化对税收表格的搜索的过程。
A.3　其他集合算法
这些算法用于处理可能包含重复元素的n元集合。

优先级队列。对优先级队列可以进行插入任意元素和删除最小元素这两种操作。14.3节介绍了实现优先级队列的两种顺序结构，并给出了一个用堆高效实现优先级队列的C++类。习题14.4、习题14.5和习题14.8描述了其应用。

选择算法。在习题2.8中我们必须选择出集合中第k个最小的元素，答案11.9给出了一个有效的算法，其他算法见答案2.8、11.1和14.4.c。

A.4　字符串算法
2.4节和2.8节计算了字典中的变位词集合。答案9.6描述了几种对字符进行分类的方法。15.1节列出了文件中的不同单词并对每个单词进行了计数，在此过程中先后用到了C++标准模板库和定制的散列表。15.2节用后缀数组查找文本文件中最长的重复子串，15.3节使用了后缀数组的一种变体由马尔可夫模型生成随机文本。

A.5　向量和矩阵算法
2.3节和习题2.3、习题2.4讨论了交换向量中子序列的算法，答案2.3给出了相应的代码。习题2.5描述了一种交换向量中非相邻子序列的算法。习题2.7利用排序对磁带上的矩阵进行转置操作。习题4.9、习题9.4和习题9.8描述了计算向量中最大值的程序。10.3节和14.4节描述了共享空间的向量算法和矩阵算法。3.1节、10.2节和13.8节讨论了稀疏向量和稀疏矩阵，习题1.9描述了一种对稀疏向量进行初始化的方案（该方案用在10.2节中）。第8章描述了计算向量最大和子序列的5种算法，该章中有几个问题跟向量与矩阵有关。

A.6　随机对象
对生成伪随机整数的函数的使用贯穿全书，这些函数在答案12.1中实现。12.3节描述了一个“打乱”数组中元素的算法。12.1节到12.3节描述了选择集合中随机子集的几种算法（另见习题12.7和习题12.9）。习题1.4给出了该算法的应用。答案12.10给出了从一组数量未知的对象中随机选择一个的算法。

A.7　数值算法
答案2.3给出了计算两个整数的最大公约数的欧几里得算法。习题3.2讨论了对常系数线性递归求值的算法。习题4.9给出了计算正整数次幂的高效算法代码。习题9.11通过查表计算三角函数。答案9.12描述了对多项式求值的Horner方法。习题11.1和习题14.4.b描述了如何对大型浮点数集合求和。

本文仅用于学习和交流目的，不代表异步社区观点。非商业转载请注明作译者、出处，并保留本文的原始链接。