详情
本书是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者以其独有的洞察力和创造力，引导读者理解这些问题并学会解决方法，而这些正是程序员实际编程生涯中至关重要的。本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序，对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述，为复杂的编程问题提供了清晰而完备的解决思路。本书对各个层次的程序员都具有很高的阅读价值。
Jon Bentley 世界著名计算机科学家，被誉为影响算法发展的十位大师之一。他先后任职于卡内基-梅隆大学（1976~1982）、贝尔实验室（1982~2001）和Avaya实验室（2001年至今）。在卡内基-梅隆大学担任教授期间，他培养了包括Tcl语言设计者John Ousterhout、Java语言设计者James Gosling、《算法导论》作者之一Charles Leiserson在内的许多计算机科学大家。2004年荣获Dr. Dobb's程序设计卓越奖。
本书是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley以其独有的洞察力和创造力，引导读者理解这些问题并学会解决方法，而这些正是程序员实际编程生涯中至关重要的。本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序，对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述，为复杂的编程问题提供了清晰而完备的解决思路。本书对各个层次的程序员都具有很高的阅读价值。
Authorized translation from the English language edition, entitled Programming Pearls, Second Edition, 0201657880 by Jon Bentley, published by Pearson Education, Inc., publishing as Addison Wesley, Copyright © 2000 by Lucent Technologies.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from Pearson Education, Inc.
CHINESE SIMPLIFIED language edition published by PEARSON EDUCATION ASIA LTD. and POSTS & TELECOM PRESS Copyright © 2015.
本书中文简体字版由Pearson Education Asia Ltd.授权人民邮电出版社独家出版。未经出版者书面许可，不得以任何方式复制或抄袭本书内容。
本书封面贴有Pearson Education（培生教育出版集团）激光防伪标签，无标签者不得销售。
版权所有，侵权必究。
黄倩 中国科学院计算技术研究所博士研究生，毕业于南京大学，目前主要从事视频处理等方面的研究工作。
钱丽艳 北京大学信息科学技术学院基础实验教学研究所软件实验室主任、工程师，毕业于国防科技大学，目前主要从事数值计算、程序设计等方面的研究工作。
刘田 北京大学信息科学技术学院软件研究所副教授、中国电子学会电路与系统分会图论与系统优化专业委员会秘书长、中国计算机学会和中国电子学会高级会员，毕业于中国科学技术大学，目前主要从事算法分析和计算复杂度、量子信息处理等方面的研究工作，翻译出版了多部国外著名离散数学和计算机理论教材。
本书作者Jon Bentley是美国著名的程序员和计算机科学家，他于20世纪70年代前后在很有影响力的《ACM通讯》（Communications of the ACM）上以专栏的形式连续发表了一系列短文，成功地总结和提炼了自己在长期的计算机程序设计实践中积累下来的宝贵经验。这些短文充满了真知灼见，而且文笔生动、可读性强，对于提高职业程序员的专业技能很有帮助，因此该专栏大受读者欢迎，成为当时该学术期刊的王牌栏目之一。可以想象当时的情形颇似早年金庸先生在《明报》上连载其武侠小说的盛况。后来在ACM的鼓励下，作者经过仔细修订和补充整理，对各篇文章的先后次序做了精心编排，分别在1986年和1988年结集出版了Programming Pearls（《编程珠玑》）和More Programming Pearls（《编程珠玑（续）》）这两本书，二者均成为该领域的名著。《编程珠玑（第2版）》在2000年问世，书中的例子都改用C语言书写，并多处提到如何用C++和Java中的类来实现。《编程珠玑（续）》虽未再版，例子多以Awk语言写成，但其语法与C相近，容易看懂。
作者博览群书，旁征博引，无论是计算机科学的专业名著，如《计算机程序设计艺术》，还是普通的科普名著，如《啊哈！灵机一动》，都在作者笔下信手拈来、娓娓道出，更不用说随处可见的作者自己的真知灼见了。如果说《计算机程序设计艺术》这样的巨著代表了程序员们使用的“坦克和大炮”一类的重型武器，这两本书则在某种程度上类似于鲁迅先生所说的“匕首与投枪”一类的轻型武器，更能满足职业程序员的日常需要。或者说前者是武侠小说中提高内力修为的根本秘籍，后者是点拨临阵招数的速成宝典，二者同样都是克敌制胜的法宝，缺一不可。在无止境地追求精湛技艺这一点上，程序员、数学家和武侠们其实是相通的。
在美国，这两本书不仅被用作大学低年级数据结构与算法课程的教材，还用作高年级算法课程的辅助教材。例如，美国著名大学麻省理工学院的电气工程与计算机科学开放式核心课程算法导论就将这两本书列为推荐读物。这两本书覆盖了大学算法课程和数据结构课程的大部分内容，但是与普通教材的侧重点又不一样，不强调单纯从数学上来进行分析的技巧，而是强调结合实际问题来进行分析、应用和实现的技巧，因此可作为大学计算机专业的算法、数据结构、软件工程等课程的教师参考用书和优秀课外读物。书中有许多真实的历史案例和许多极好的练习题以及部分练习题的提示与解答，非常适合自学。正如作者所建议的那样，阅读这两本书时，读者需要备有纸和笔，最好还有一台计算机在手边，边读边想、边想边做，这样才能将阅读这两本书的收益最大化。
人民邮电出版社引进版权，同时翻译出版了《编程珠玑（第2版）》和《编程珠玑（续）》，使这两个中译本珠联璧合，相信这不仅能极大地满足广大程序员读者的需求，还有助于提高国内相关课程的授课质量和学生的学习兴趣。
本书主要由黄倩和钱丽艳翻译，刘田审校，翻译过程中得到了张怀勇先生的帮助，在此表示感谢。由于本书内容深刻，语言精妙，而译者的水平和时间都比较有限，错误和不当之处在所难免，敬请广大读者批评指正。
计算机编程有很多方面。Fred Brooks在《人月神话》一书中为我们描绘了全景，他的文章强调了管理在大型软件项目中所起的关键作用。而Steve McConnell在《代码大全》一书中更具体地传授了良好的编程风格。这两本书所讨论的是好软件的关键因素和专业程序员应有的特征。遗憾的是，仅仅熟练地运用这些可靠的工程原理，不见得一定能够如期完成软件并顺利运行。
本书描述了计算机编程更具魅力的一面：在可靠的工程之外，在洞察力和创造力范围内结晶而出的编程珠玑。正如自然界中的珍珠来自于磨砺牡蛎的细沙一样，这些编程珠玑来自于磨砺程序员的实际问题。书中的程序都很有趣，传授了重要的编程技巧和基本的设计原理。
本书大部分内容最初发表在《ACM通讯》中我主持的“编程珠玑”专栏。这些内容经过汇总和修订，在1986年结集出版，成为本书的第1版。第1版的13篇文章中，有12篇都在本版中做了大幅修订；此外，本版还补充了3篇新的内容。
阅读本书所需的唯一背景知识就是某种高级语言的编程经验。书中偶尔会出现一些高级技术（如C++中的模板等），对此不熟悉的读者可以跳过这些内容，基本上不影响阅读。
本书每一章都独立成篇，各章之间却又有着逻辑分组。第1章至第5章构成本书的第一部分，这部分回顾了编程的基本原理：问题定义、算法、数据结构以及程序验证和测试。第二部分围绕效率这个主题展开。效率问题有时本身很重要，又永远都是进入有趣编程问题的绝佳跳板。第三部分用这些技术来解决排序、搜索和字符串等重要问题。
阅读本书的一个提示：不要读得太快。要仔细阅读，一次读一章。要尝试解答书中提出的问题——有些问题需要集中精力思考一两小时才会变得容易。然后，要努力解答每章末尾的习题：当读者写下答案时，从本书学到的大部分知识就会跃然纸上。如有可能，要先与朋友和同事讨论一下自己的思路，再去查阅本书末尾的提示和答案。每章末尾的“深入阅读”并不算是学术意义上的参考文献表，而是我推荐的一些好书，这些书是我个人藏书的重要部分。
本书是为程序员而写的。我希望书中的习题、提示、答案和深入阅读对每个人都有用。本书已用作算法、程序验证和软件工程等课程的教材。附录A中的算法分类可供实际编程人员参考，该附录同时还说明了如何在算法和数据结构课程中使用本书。
本书第1版中的伪代码程序其实都已实现，但当时未公开。在本版中，我重写了所有的老程序，并且编写了差不多等量的新代码。代码中包含许多对函数进行测试、调试和计时的脚手架程序。该网站还提供了其他相关的材料。由于现在许多的软件都能在线获得，因此本版的一个新增内容就是：如何评估和使用软件组件。
本书的程序采用了简洁的代码风格：短变量名，很少空行，很少或没有错误检测。这种风格不适用于大型软件项目，却有助于表达算法的核心思想。第5章第1个习题的答案给出了这种风格的更多细节。
本书包含几个实际的C和C++程序，其余大多数函数都用伪代码来表示，这样既节省了空间，又避免了烦琐的语法。记号for i = [0,n)表示在从0至n-1的范围内对i进行迭代。在这类 for 循环中，左圆括号和右圆括号代表开区间（不包括端点值），而左方括号和右方括号代表闭区间（包括端点值）。表达式function(i, j)仍表示用参数i和j调用函数，而array[i,j]仍表示访问数组元素。
本版所提供的许多程序的运行时间都基于“我的计算机”——一台128 MB内存、运行Windows NT 4.0操作系统的400 MHz Pentium II。我测试了这些程序在其他几台机器上的运行时间，书中记录了我观察到的一些显著的差异。所有的实验都使用了最高级别的编译器优化。建议读者在自己的计算机上对这些程序计时，我敢打赌读者将会发现相似比率的运行时间。
我希望你们在翻阅本版时的第一感觉是“看起来很眼熟啊”，而过几分钟又得出结论“以前从来没读过”。
本版与第1版主题相同，但涉及的范围更广。计算技术已经在数据库、网络和用户界面等重要领域取得了长足的进展。大多数程序员应当都熟悉这些技术。但是，这些领域的中心仍然是那些核心编程问题，这些问题还是本书的主题。相对于第1版而言，本版可以比喻为一条稍微长大了的鱼，游进了一个大得多的池塘。
第1版第4章关于实现二分搜索的一节内容经过扩充成为本版中关于测试、调试和计时的第5章。第1版第11章经过扩充，在本版中分成了第12章（还讨论原来的问题）和第13章（讨论集合表示）。第1版第13章描述的在64 KB地址空间运行的拼写检查器已被删除，但其要点仍保留在13.8节中。新增的第15章讨论字符串问题。本版在第1版的各章中插入了许多新节，同时删除了一些旧节。新增的习题、答案以及4个附录使得本版篇幅比第1版增加了25%。
本版保留了许多原有的实例研究，因为它们具有历史价值。有些老故事则用现代术语做了改写。
对许多人给予我的诸多帮助，我一直心存感激。Peter Denning和Stuart Lynn最早设想在《ACM通讯》上开设专栏。Peter在计算机学会（ACM）内做了大量的工作，促成了该专栏，并动员我来主持这个专栏。ACM总部员工（特别是Roz Steier和Nancy Adriance）在本书各篇文章最初发表时给予大力协助。我要特别感谢ACM鼓励我以目前这种经过修订的形式来出版各篇文章；还要特别感谢《ACM通讯》的众多读者，他们对原始各篇文章的评论使得这个扩充版本成为必要的和可能的。
Al Aho、Peter Denning、Mike Garey、David Johnson、Brian Kernighan、John Linderman、Doug McIlroy和Don Stanat都非常仔细地读过每一章，尽管时间期限常常很紧。我还要感谢以下诸位的宝贵意见：Henry Baird、Bill Cleveland、David Gries、Eric Grosse、Lynn Jelinski、Steve Johnson、Bob Melville、Bob Martin、Arno Penzias、Marilyn Roper、Chris Van Wyk、Vic Vyssotsky和Pamela Zave。Al Aho、Andrew Hume、Brian Kernighan、Ravi Sethi、Laura Skinger和Bjarne Stroustrup在本书的成书过程中给予了无法估量的帮助，而西点军校EF 485课程的学员实际核对了倒数第二稿①。再次谢谢诸位。
Dan Bentley、Russ Cox、Brian Kernighan、Mark Kernighan、John Linderman、Steve McConnell、Doug McIlroy、Rob Pike、Howard Trickey和Chris Van Wyk都非常仔细地阅读过本版。我还要感谢以下诸位的宝贵意见：Paul Abrahams、Glenda Childress、Eric Grosse、Ann Martin、Peter McIlroy、Peter Memishian、Sundar Narasimhan、Lisa Ricker、Dennis Ritchie、Ravi Sethi、Carol Smith、Tom Szymanski和Kentaro Toyama。感谢Addison-Wesley出版社的Peter Gordon和他的同事们帮助筹划了本版。
Jon Bentley
于新泽西州Murray Hill
1985年12月
1999年 8 月
①原作者在给译者的电子邮件中指出，他曾在西点军校授课，用本书草稿作为教材，EF为Engineering Fundamentals（工程基础）系的缩写。——译者注
这一部分的5章回顾程序设计的基础知识。第1章介绍一个问题的历史，我们把仔细的问题定义和直接的程序设计技术结合起来，得到优美的解决方案。这一章揭示了本书的中心思想：对实例研究的深入思考不仅很有趣，而且可以获得实际的益处。
第2章讨论3个问题，其中重点强调了如何由算法的融会贯通获得简单而高效的代码。第3章总结数据结构在软件设计中所起到的关键作用。
第4章介绍一个编写正确代码的工具——程序验证。在第9章、第11章和第14章中生成复杂（且快速）的函数时，大量使用了程序验证技术。第5章讲述如何把这些抽象的程序变成实际代码：使用脚手架程序来探测函数，用测试用例来测试函数并度量函数的性能。
本部分内容
第1章 开篇
第2章 啊哈! 算法
第3章 数据决定程序结构
第4章 编写正确的程序
第5章 编程小事
一位程序员曾问我一个很简单的问题：“怎样给一个磁盘文件排序？”想当年我是一上来就犯了错误，现在，在讲这个故事之前，先给大家一个机会，看看能否比我当年做得更好。你会怎样回答上述问题呢？
我错就错在马上回答了这个问题。我告诉他一些有关如何在磁盘上实现归并排序的简要思路。我建议他深入研究算法教材，他似乎不太感冒。他更关心如何解决这个问题，而不是深入学习。于是我告诉他在一本流行的程序设计书里有磁盘排序的程序。那个程序有大约200行代码和十几个函数，我估计他最多需要一周时间来实现和测试该代码。
我以为已经解决了他的问题，但是他的踌躇使我返回到了正确的轨道上。其后就有了下面的对话，楷体部分是我的问题。
为什么非要自己编写排序程序呢？为什么不用系统提供的排序功能呢？
我需要在一个大系统中排序。由于不明的技术原因，我不能使用系统中的文件排序程序。
需要排序的内容是什么？文件中有多少条记录？每条记录的格式是什么？
文件最多包含1000万条记录，每条记录都是7位的整数。
等一下，既然文件这么小，何必非要在磁盘上进行排序呢？为什么不在内存里进行排序呢？
尽管机器有许多兆字节的内存，但排序功能只是大系统中的一部分，所以，估计到时只有1 MB的内存可用。
你还能告诉我其他一些与记录相关的信息吗？
每条记录都是7位的正整数，再无其他相关数据。每个整数最多只出现一次。
这番对话让问题更明确了。在美国，电话号码由3位“区号”后再跟7位数字组成。拨打含“免费”区号800（当时只有这一个号码）的电话是不收费的。实际的免费电话号码数据库包含大量的信息：免费电话号码、呼叫实际中转到的号码（有时是几个号码，这时需要一些规则来决定哪些呼叫在什么时间中转到哪里）、主叫用户的姓名和地址等。
这位程序员正在开发这类数据库的处理系统的一小部分，需要排序的整数就是免费电话号码。输入文件是电话号码的列表（已删除所有其他信息），号码重复出现算出错。期望的输出文件是以升序排列的电话号码列表。应用背景同时定义了相应的性能需求。当与系统的会话时间较长时，用户大约每小时请求一次有序文件，并且在排序未完成之前什么都干不了。因此，排序最多只允许执行几分钟，10秒钟是比较理想的运行时间。
对程序员来说，这些需求加起来就是：“如何给磁盘文件排序？”在试图解决这个问题之前，先将已知条件组织成一种更客观、更易用的形式。
输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。
输出：按升序排列的输入整数的列表。
约束：最多有（大约）1 MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。
请花上一分钟思考一下该问题的规范说明。现在你打算给程序员什么样的建议呢？
显而易见的方法是以一般的基于磁盘的归并排序程序为起点，但是要对其进行调整，因为我们是对整数进行排序。这样就可以将原来的200行程序减少为几十行，同时也使得程序运行得更快，但是完成程序并使之运行可能仍然需要几天的时间。
另一种解决方案更多地利用了该排序问题的特殊性。如果每个号码都使用7字节来存储，那么在可用的1 MB存储空间里大约可以存143 000个号码。如果每个号码都使用32位整数来表示的话，在1 MB存储空间里就可以存储250 000个号码。因此，可以使用遍历输入文件40趟的程序来完成排序。在第一趟遍历中，将0至249 999之间的任何整数都读入内存，并对这（最多）250 000个整数进行排序，然后写到输出文件中。第二趟遍历排序250 000至499 999之间的整数，依此类推，到第40趟遍历的时候对9 750 000至9 999 999之间的整数进行排序。对内存中的排序来说，快速排序会相当高效，而且仅仅需要20行代码（见第11章）。于是，整个程序就可以通过一两页纸的代码实现。该程序拥有所期望的特性——不必考虑使用中间磁盘文件；但是，为此所付出的代价是要读取输入文件40次。
归并排序读入输入文件一次，然后在工作文件的帮助下完成排序并写入输出文件一次。工作文件需要多次读写。
40趟算法读入输入文件多次，写输出文件仅一次，不使用中间文件。
下图所示的方案更可取。我们结合上述两种方法的优点，读输入文件仅一次，且不使用中间文件。
只有在输入文件中的所有整数都可以在可用的1 MB内存中表示的时候才能够实现该方案。于是问题就归结为是否能够用大约800万个可用位来表示最多1 000万个互异的整数。考虑一种合适的表示方式。
由是观之，应该用位图或位向量表示集合。可用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合。例如，可以用如下字符串来表示集合{1, 2, 3, 5, 8, 13}：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0代表集合中数值的位都置为1，其他所有的位都置为0。
在我们的实际问题中，每个7位十进制整数表示一个小于1 000万的整数。我们使用一个具有1 000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。（那个程序员后来找到了200万个稀疏位，习题5研究了最大存储空间严格限制为1 MB的情况。）这种表示利用了该问题的三个在排序问题中不常见的属性：输入数据限制在相对较小的范围内；数据没有重复；而且对于每条记录而言，除了单一整数外，没有任何其他关联数据。
若给定表示文件中整数集合的位图数据结构，则可以分三个自然阶段来编写程序。第一阶段将所有的位都置为0，从而将集合初始化为空。第二阶段通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。第三阶段检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出文件。令n为位向量中的位数（在本例中为10 000 000），程序可以使用伪代码表示如下：
/* phase 1: initialize set to empty */
for i = [0, n)
bit[i] = 0
/* phase 2: insert present elements into the set */
for each i in the input file
bit[i] = 1
/* phase 3: write sorted output */
for i = [0, n)
if bit[i] == 1
write i on the output file（回想在前言中所提到的，for i=[0, n)表示在从0至n-1的范围内对i进行迭代。）
这个实现概要已经足以解决那个程序员的问题了。习题2、习题5和习题7描述了他会遇到的一些实现细节。
那个程序员打电话把他的问题告诉我，然后我们花了大约一刻钟时间明确了问题所在，并找到了位图解决方案。他花了几小时来实现这个几十行代码的程序。该程序远远优于我们在电话刚开始时所担心的需要花费一周时间编写的几百行代码的那个程序。而且程序执行得很快：磁盘上的归并排序可能需要许多分钟的时间，该程序所需的时间只比读取输入和写入输出所需的时间多一点点——大约10秒钟。答案3包含了对完成该任务的几种不同程序的计时细节。
从这些事实中可以总结出该实例研究所得到的第一个结论：对小问题的仔细分析有时可以得到明显的实际益处。在该实例中，几分钟的仔细研究可以大幅削减代码的长度、程序员时间和程序运行时间。Chuck Yeager将军（第一个超音速飞行的人）赞扬一架飞机的机械系统时用的词是“结构简单、部件很少、易于维护、非常坚固”，该程序拥有同样的属性。然而，当规范说明的某些因素发生改变时，该程序的特殊结构将很难修改。除了需要精巧的编程以外，该实例阐明了如下一般原理。
正确的问题。明确问题，这场战役就成功了90%——我很庆幸程序员没有满足于我给出的第一个程序。一旦正确理解了问题，习题10、习题11和习题12的答案都会很优雅。在查看提示和答案以前，请努力思考这些问题。
位图数据结构。该数据结构描述了一个有限定义域内的稠密集合，其中的每一个元素最多出现一次并且没有其他任何数据与该元素相关联。即使这些条件没有完全满足（例如，存在重复元素或额外的数据），也可以用有限定义域内的键作为一个表项更复杂的表格的索引，见习题6和习题8。
多趟算法。这些算法多趟读入其输入数据，每次完成一步。在1.3节已经见到了一个40趟算法，习题5鼓励读者去完成一个两趟算法。
时间—空间折中与双赢。编程文献和理论中充斥着时间—空间的折中：通过使用更多的时间，可以减少程序所需的空间。例如，答案5中的两趟算法让程序运行时间加倍从而使空间减半。但我的经验常常是这样的：减少程序的空间需求也会减少其运行时间。①空间上高效的位图结构显著地减少了排序的运行时间。空间需求的减少之所以会导致运行时间的减少，有两个原因：需要处理的数据变少了，意味着处理这些数据所需的时间也变少了；同时将这些数据保存在内存中而不是磁盘上，进一步避免了磁盘访问的时间。当然了，只有在原始的设计远非最佳方案时，才有可能时空双赢。
简单的设计。Antoine de Saint-Exupéry是法国作家兼飞机设计师，他曾经说过：“设计者确定其设计已经达到了完美的标准不是不能再增加任何东西，而是不能再减少任何东西。”更多的程序员应该使用该标准来检验自己完成的程序。简单的程序通常比具有相同功能的复杂的程序更可靠、更安全、更健壮、更高效，而且易于实现和维护。
程序设计的阶段。这个实例揭示了12.4节详细描述的设计过程。
部分习题的提示和答案可以在本书后面找到。
1．如果不缺内存，如何使用一个具有库的语言来实现一种排序算法以表示和排序集合？
2．如何使用位逻辑运算（如与、或、移位）来实现位向量？
3．运行时效率是设计目标的一个重要组成部分，所得到的程序需要足够高效。在你自己的系统上实现位图排序并度量其运行时间。该时间与系统排序的运行时间以及习题1中排序的运行时间相比如何？假设n为10 000 000，且输入文件包含1 000 000个整数。
4．如果认真考虑了习题3，你将会面对生成小于n且没有重复的k个整数的问题。最简单的方法就是使用前k个正整数。这个极端的数据集合将不会明显地改变位图方法的运行时间，但是可能会歪曲系统排序的运行时间。如何生成位于0至n-1之间的k个不同的随机顺序的随机整数？尽量使你的程序简短且高效。
5．那个程序员说他有1 MB的可用存储空间，但是我们概要描述的代码需要1.25 MB的空间。他可以不费力气地索取到额外的空间。如果1 MB空间是严格的边界，你会推荐如何处理呢？你的算法的运行时间又是多少？
6．如果那个程序员说的不是每个整数最多出现一次，而是每个整数最多出现10次，你又如何建议他呢？你的解决方案如何随着可用存储空间总量的变化而变化？
7．[R. Weil]本书1.4节中描述的程序存在一些缺陷。首先是假定在输入中没有出现两次的整数。如果某个数出现超过一次的话，会发生什么？在这种情况下，如何修改程序来调用错误处理函数？当输入整数小于零或大于等于n时，又会发生什么？如果某个输入不是数值又如何？在这些情况下，程序该如何处理？程序还应该包含哪些明智的检查？描述一些用以测试程序的小型数据集合，并说明如何正确处理上述以及其他的不良情况。
8．当那个程序员解决该问题的时候，美国所有免费电话的区号都是800。现在免费电话的区号包括800、877和888，而且还在增多。如何在1 MB空间内完成对所有这些免费电话号码的排序？如何将免费电话号码存储在一个集合中，要求可以实现非常快速的查找以判定一个给定的免费电话号码是否可用或者已经存在？
9．使用更多的空间来换取更少的运行时间存在一个问题：初始化空间本身需要消耗大量的时间。说明如何设计一种技术，在第一次访问向量的项时将其初始化为0。你的方案应该使用常量时间进行初始化和向量访问，使用的额外空间应正比于向量的大小。因为该方法通过进一步增加空间来减少初始化的时间，所以仅在空间很廉价、时间很宝贵且向量很稀疏的情况下才考虑使用。
10．在成本低廉的隔日送达时代之前，商店允许顾客通过电话订购商品，并在几天后上门自取。商店的数据库使用客户的电话号码作为其检索的主关键字（客户知道他们自己的电话号码，而且这些关键字几乎都是唯一的）。你如何组织商店的数据库，以允许高效的插入和检索操作？
11．在20世纪80年代早期，洛克希德公司加利福尼亚州桑尼维尔市工厂的工程师们每天都要将许多由计算机辅助设计（CAD）系统生成的图纸从工厂送到位于圣克鲁斯市的测试站。虽然仅有40公里远，但使用汽车快递服务每天都需要一个多小时的时间（由于交通阻塞和山路崎岖），花费100美元。请给出新的数据传输方案并估计每一种方案的费用。
12．载人航天的先驱们很快就意识到需要在外太空的极端环境下实现顺利书写。民间盛传美国国家宇航局（NASA）花费100万美元研发出了一种特殊的钢笔来解决这个问题。那么，前苏联又会如何解决相同的问题呢？
这个小练习仅仅是令人痴迷的程序说明问题的冰山一角。要深入研究这个重要的课题，参见Michael Jackson②的Software Requirements & Specifications一书（Addison-Wesley出版社1995年出版）。该书用一组独立成章却又相辅相成的短文，以令人愉悦的方式阐述了这个艰涩的课题。
在本章所描述的实例研究中，程序员的主要问题与其说是技术问题，还不如说是心理问题：他不能解决问题，是因为他企图解决错误的问题。问题的最终解决，是通过打破他的概念壁垒，进而去解决一个较简单的问题而实现的。James L. Adams所著的Conceptuel Blockbusting一书（第3版由Perseus出版社于1986年出版）研究了这类跳跃，该书通常是触发创新性思维的理想选择。虽然该书不是专为程序员而写的，其中的许多内容却特别适用于编程问题。Adams将概念壁垒定义为“阻碍解题者正确理解问题或取得答案的心智壁垒”。习题10、习题11和习题12激励读者去打破一些这样的壁垒。
①折中在所有的工程领域中都存在。例如，汽车设计者可能会通过增加沉重的部件，用行驶里程的减少来换取更快的加速。但双赢是更好的结果。我对自己驾驶过的一辆小轿车做过一番研究，我观察到：“轿车基本结构重量的减少会使各底盘部件重量的进一步减少——甚至消除了对某些底盘部件的需求，例如转向助力系统。”
②Michael Jackson（1936—），软件工程先驱。他于20世纪70年代提出了影响深远的面向数据结构的Jackson方法。 ——编者注
研究算法给实际编程的程序员带来许多好处。算法课教给学生完成重要任务的方法和解决新问题的技术。在后续的章节中将会看到，先进的算法工具有时候对软件系统影响很大——减少开发时间，同时使执行速度更快。
算法与其他那些深奥的思想一样重要，但在更一般的编程层面上具有更重要的影响。在《啊哈!灵机一动》一书中（本章的标题就借鉴了它），Martin Gardner①描述了深得我心的一个思想：“看起来很困难的问题也可以有一个简单的、意想不到的答案。”与高级的方法不同，算法的啊哈！灵机一动并非只有在大量的研究以后才能出现；任何愿意在编程之前、之中和之后进行认真思考的程序员都有机会捕捉到这灵机一动。
好了，泛泛的话讲得够多啦。本章将围绕三个小问题展开。在继续阅读以前，请先试着解决它们。
A．给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的数——为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？
B．将一个n元一维向量向左旋转②i个位置。例如，当n=8且i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转?
C．给定一个英语字典，找出其中的所有变位词集合。例如，“pots”“stop”和“tops”互为变位词，因为每一个单词都可以通过改变其他单词中字母的顺序来得到。
我想到的一个数在1到100之间，你来猜猜看。50？太小了。75？太大了。如此，游戏进行下去，直到你猜中我想到的数为止。如果我的整数位于1到n之间，那么你可以在log2n次之内猜中。如果n是1 000，10次就可以完成；如果n是100万，则最多20次就可以完成。
这个例子引出了一项可以解决众多编程问题的技术：二分搜索。初始条件是已知一个对象存在于一个给定的范围内，而一次探测操作可以告诉我们该对象是否低于、等于或高于给定的位置。二分搜索通过重复探测当前范围的中点来定位对象。如果一次探测没有找到该对象，那么我们将当前范围减半，然后继续下一次探测。当找到所需要的对象或范围为空时停止。
在程序设计中二分搜索最常见的应用是在有序数组中搜索元素。在查找项50时，算法进行如下探测。
众所周知，二分搜索程序要正确运行很困难。在第4章中我们将详细研究其代码。
顺序搜索在搜索一个具有n个元素的表时，平均需要进行n/2次比较，而二分搜索仅仅进行不超过log2n次的比较就可以完成。这在系统性能上会造成巨大的差异。下面的故事来自于《ACM通讯》的实例研究“TWA Reservation System”。
我们有一个执行线性搜索的程序，可以在1秒钟内对一块非常巨大的内存块完成100次搜索。随着网络的增长，处理每条消息所需的平均CPU时间上升了0.3毫秒，这对我们来说是巨大的变化。我们发现问题的根源是线性搜索。把程序改为使用二分搜索以后，该问题消失了。
我在许多系统中也遇到过相同的问题。程序员在开始的时候使用简单的顺序搜索数据结构，这在开始的时候通常都足够快。当搜索变得太慢的时候，对表进行排序并使用二分搜索通常可以消除瓶颈。
但是二分搜索的故事并没有在快速搜索有序数组这里终止。Roy Weil将该技术应用于清理一个约1000行的输入文件，其中仅包含一个错误行。很不幸，肉眼看不出错误行。只能通过在程序中运行文件的一个（起始）部分并且观察到离奇错误的答案来辨别，这将会花费几分钟的时间。他的前任调试人员试图通过每次运行整个程序中的少数几行程序来找出错误行，但只在取得解决方案的道路上前进了一点点。Weil是如何仅仅运行10次程序就找到罪魁祸首的呢？
经过前面的热身，我们现在来攻克问题A。输入为顺序文件（考虑磁带或磁盘——虽然磁盘可以随机读写，但是从头至尾读取文件通常会快得多）。文件包含最多40亿个随机排列的32位整数，而我们需要找出一个不存在于该文件中的32位整数。（至少缺少一个整数，因为一共有232也就是4 294 967 296个这样的整数。）如果有足够的内存，可以采用第1章中介绍的位图技术，使用536 870 912个8位字节形成位图来表示已看到的整数。然而，该问题还问到在仅有几百字节内存和几个稀疏顺序文件的情况下如何找到缺失的整数？为了采用二分搜索技术，就必须定义一个范围、在该范围内表示元素的方式以及用来确定哪一半范围存在缺失整数的探测方法。如何来实现呢？
我们采用已知包含至少一个缺失元素的一系列整数作为范围，并使用包含所有这些整数在内的文件表示这个范围。灵机一动的结果是通过统计中间点之上和之下的元素来探测范围：或者上面或者下面的范围具有至多全部范围的一半元素。由于整个范围中有一个缺失元素，因此我们所需的那一半范围中必然也包含缺失的元素。这些就是解决该问题的二分搜索算法所需要的主要想法。在翻阅答案查看Ed Reingold是如何做的以前，请尝试将这些想法组织起来。
对于二分搜索技术在程序设计中的应用来说，这些应用仅仅是皮毛而已。求根程序使用二分搜索技术，通过连续地对分区间来求解单变量方程式（数值分析家称之为对分法）。当答案11.9中的选择算法区分出一个随机元素以后，就对该元素一侧的所有元素递归地调用自身（这是一种随机二分搜索）。其他使用二分搜索的地方包括树数据结构和程序调试（当程序没有任何提示就意外中止时，你会从源代码中哪一部分开始探测来定位错误语句呢？）。在上述的每个例子中，分析程序并对二分搜索算法做些许修改，可以带给程序员功能强大的啊哈！灵机一动。
二分搜索是许多问题的解决方案，下面研究一个有几种解决方案的问题。问题B仅使用几十字节的额外空间将一个n元向量x在正比于n的时间内向左旋转i个位置。该问题在应用程序中以各种不同的伪装出现。在一些编程语言中，该功能是向量的一个基本操作。更重要的是，旋转操作对应于交换相邻的不同大小的内存块：每当拖动文件中的一块文字到其他地方时，就要求程序交换两块内存中的内容。在许多应用场合下，运行时间和存储空间的约束会很严格。
可以通过如下方式解决该问题：首先将x的前i个元素复制到一个临时数组中，然后将余下的n－i个元素向左移动i个位置，最后将最初的i个元素从临时数组中复制到x中余下的位置。但是，这种办法使用的i个额外的位置产生了过大的存储空间的消耗。另一种方法是定义一个函数将x向左旋转一个位置（其时间正比于n）然后调用该函数i次。但该方法又产生了过多的运行时间消耗。
要在有限的资源内解决该问题，显然需要更复杂的程序。有一个成功的方法有点像精巧的杂技动作：移动x[0]到临时变量t，然后移动x[i]至x[0]，x[2i]至x[i]，依此类推（将x中的所有下标对n取模），直至返回到取x[0]中的元素，此时改为从t取值然后终止过程。当i为3且n为12时，元素按如下顺序移动。
如果该过程没有移动全部元素，就从x[1]开始再次进行移动，直到所有的元素都已经移动为止。习题3要求读者将该思想还原为代码，务必小心。
从另外一面考察这个问题，可以得到一个不同的算法：旋转向量x其实就是交换向量ab的两段，得到向量ba。这里a代表x中的前i个元素。假设a比b短，将b分为bl和br，使得br具有与a相同的长度。交换a和br，也就将ablbr转换为brbla。序列a此时已处于其最终的位置，因此现在的问题就集中到交换b的两部分。由于新问题与原来的问题具有相同的形式，我们可以递归地解决之。使用该算法可以得到优雅的程序（答案3描述了Gries和Mills的迭代解决方案），但是需要巧妙的代码，并且要进行一些思考才能看出它的效率足够高。
问题看起来很难，除非最终获得了啊哈！灵机一动：我们将问题看作是把数组ab转换成ba，同时假定我们拥有一个函数可以将数组中特定部分的元素求逆。从ab开始，首先对a求逆，得到arb，然后对b求逆，得到arbr。最后整体求逆，得到(arbr)r。此时就恰好是ba。于是，我们得到了如下用于旋转的代码，其中注释部分表示abcdefgh向左旋转三个位置以后的结果。
reverse(0,i-1) /* cbadefgh */
reverse(i,n-1) /* cbahgfed */
reverse(0,n-1) /* defghabc */Doug McIlroy③给出了将十元数组向上旋转5个位置的翻手例子。初始时掌心对着我们的脸，左手在右手上面。
翻转代码在时间和空间上都很高效，而且代码非常简短，很难出错。Brian Kernighan④和P. J. PlaugerBrian Kernighan⑤在其1981年出版的Software Tools in Pascal一书中，就使用该代码在文本编辑器中实现了行的移动。Kernighan报告称在第一次执行的时候程序就正确运行了，而他们先前基于链表的处理相似任务的代码则包含几个错误。该代码用在几个文本处理系统中，其中包括我最初用于录入本章内容的文本编辑器。Ken Thompson⑥在1971年编写了编辑器和这种求逆代码，甚至在那时就主张把该代码当作一种常识。
现在我们来讨论问题C。给定一本英语单词字典（每个输入行是一个由小写字母组成的单词），要求找出所有的变位词分类。研究这个问题可以举出许多理由。首先是技术上的：获得这个问题的解决方案需要既具有正确的视角又能使用正确的工具。第二个理由更具有说服力：你总不想成为聚会中唯一一个不知道“deposit”“dopiest”“posited”和“topside”是变位词的人吧？如果这些理由还嫌不够，可以看一下习题6描述的现实系统中的一个相似的问题。
解决这个问题的许多方法都出奇地低效和复杂。任何一种考虑单词中所有字母的排列的方法都注定了要失败。单词“cholecystoduodenostomy”（我的字典中单词“duodenocholecystostomy”的一个变位词）有22！种排列，少量的乘法运算表明22! ≈ 1.1241021。即使假设以闪电一样的速度每百亿分之一秒执行一种排列，这也要消耗1.1109 秒。经验法则“π秒就是一个纳世纪”（见7.1节）指出1.1×109是数十年。而比较所有单词对的任何方法在我的机器上运行至少要花费一整夜的时间——在我使用的字典里有大约230 000个单词，而即使是一个简单的变位词比较也将花费至少1 微秒的时间，因此，总时间估算起来就是
230 000单词×230 000比较/单词×1微秒/比较=52 900×106微秒=52 900秒≈14.7小时
你能够找到同时避免上述缺陷的方法吗？
我们获得的啊哈！灵机一动就是标识字典中的每一个词，使得在相同变位词类中的单词具有相同的标识。然后，将所有具有相同标识的单词集中在一起。这将原始的变位词问题简化为两个子问题：选择标识和集中具有相同标识的单词。在进一步阅读之前，先好好想想这些问题。
对第一个问题，我们可以使用基于排序的标识⑦：将单词中的字母按照字母表顺序排列。“deposit”的标识就是“deiopst”，这也是“dopiest”和其他任何在该类中的单词的标识。要解决第二个问题，我们将所有的单词按照其标识的顺序排序。我所知道的关于该算法的最好描述就是Tom Cargill的翻手表示：先用一种方式排序（水平翻手），再用另一种方式排序（垂直翻手）。2.8节描述了该算法的一个实现。
排序。排序最显而易见的用处是产生有序的输出，该输出既可以是系统规范要求的一部分，也可以是另一个程序（也许是一个二分搜索程序）的前期准备工作。但是在变位词问题中，排序并不是关注的焦点。排序是为了将相等的元素（本例中为标识）集中到一起。这些标识产生了另外一个排序应用：将单词内字母排序使得同一个变位词类中的单词具有标准型。通过给每条记录添加一个额外的键，并按照这些键进行排序，排序函数可以用于重新排列磁盘文件中的数据。在第三部分，我们还会多次回顾排序这个主题。
二分搜索。该算法在有序表中查找元素时极为高效，并且可用于内存排序或磁盘排序。唯一的缺陷就是整个表必须已知并且事先排好序。基于该简单算法的思想在许多应用程序中都有应用。
标识。当使用等价关系来定义类时，定义一种标识使得类中的每一项都具有相同的标识，而该类以外的其他项则没有该标识，这是很有用的。对单词中的字母排序可以产生一个用于变位词类的标识。其他标识通过排序给出。然后使用一个计数来代表重复的次数（于是标识“mississippi”可以写成“i4m1p2s4”或将1省略——“i4mp2s4”）。也可以使用一个包含26个整数的数组来标识每个字母出现的次数。标识的其他应用包括：美国联邦调查局用来索引指纹的方法，以及用来识别读音相同但是拼写不同的名字的Soundex启发式方法：
| 名字 |
Soundex标识 |
|---|---|
| Smith |
s530 |
Knuth⑧在其The Art of Computer Programming, Volume 3: Sorting and Sear ching⑨一书的第6章描述了Soundex方法。
问题定义。第1章指出确定用户的真实需求是程序设计的根本。本章的中心思想是问题定义的下一步：使用哪些基本操作来解决问题？在本章的每个例子中，啊哈！灵机一动都定义了一个新的基本操作使得问题得到简化。
问题解决者的观点。优秀程序员都有点懒：他们坐下来并等待灵机一动的出现而不急于使用最开始的想法编程。当然，这必须通过在适当的时候开始写代码来加以平衡。真正的技能就在于对这个适当时候的把握，这只能来源于解决问题和反思答案所获得的经验。
1．考虑查找给定输入单词的所有变位词问题。仅给定单词和字典的情况下，如何解决该问题？如果有一些时间和空间可以在响应任何查询之前预先处理字典，又会如何？
2．给定包含4 300 000 000个32位整数的顺序文件，如何找出一个出现至少两次的整数？
3．前面涉及了两个需要精巧代码来实现的向量旋转算法。将其分别作为独立的程序实现。在每个程序中，i和n的最大公约数如何出现？
4．几位读者指出，既然所有的三个旋转算法需要的运行时间都正比于n，杂技算法的运行速度显然是求逆算法的两倍。杂技算法对数组中的每个元素仅存储和读取一次，而求逆算法需要两次。在实际的计算机上进行实验以比较两者的速度差异，特别注意内存引用位置附近的问题。
5．向量旋转函数将向量ab变为ba。如何将向量abc变为cba？（这对交换非相邻内存块的问题进行了建模）。
6．20世纪70年代末期，贝尔实验室开发出了“用户操作的电话号码簿辅助程序”，该程序允许雇员使用标准的按键电话在公司电话号码簿中查找电话号码。
要查找该系统设计者的名字Mike Lesk⑩，可以按“LESK*M*”（也就是“5375*6*”），随后，系统会输出他的电话号码。这样的服务现在随处可见。该系统中出现的一个问题是，不同的名字有可能具有相同的按键编码。在Lesk的系统中发生这种情况时，系统会询问用户更多的信息。给定一个大的名字文件（例如标准的大城市电话号码簿），如何定位这些“错误匹配”呢？（当Lesk在这种规模的电话号码簿上做实验时，他发现错误匹配发生的概率仅仅是0.2%。）如何实现一个以名字的按键编码为参数，并返回所有可能的匹配名字的函数？
7．在20世纪60年代早期，Vic Vyssotsky与一个程序员一起工作，该程序员需要转置一个存储在磁带上的4 000×4 000的矩阵（每条记录的格式相同，为数十字节）。他的同事最初提出的程序需要运行50小时。Vyssotsky如何将运行时间减少到半小时呢？
8．[J. Ullman]给定一个n元实数集合、一个实数t和一个整数k，如何快速确定是否存在一个k元子集，其元素之和不超过t？
9．顺序搜索和二分搜索代表了搜索时间和预处理时间之间的折中。处理一个n元表格时，需要执行多少次二分搜索才能弥补对表进行排序所消耗的预处理时间？
10．某一天，一个新研究员向托马斯·爱迪生报到。爱迪生要求他计算出一个空灯泡壳的容积。在使用测径仪和微积分进行数小时的计算后，这个新员工给出了自己的答案——150 cm3。而爱迪生在几秒钟之内就计算完毕并给出了结果“更接近155”。他是如何实现的呢？
8.8节列出了算法方面的几本好书。
我的变位词程序按三个阶段的“管道”组织，其中一个程序的输出文件作为下一个程序的输入文件。第一个程序标识单词，第二个程序排序标识后的文件，而第三个程序将这些单词压缩为每个变位词类一行的形式。下面是一个仅有6个单词的字典的处理过程。
输出包括三个变位词类。
下面的C语言sign程序假定没有超过100个字母的单词，并且输入文件仅包含小写字母和换行符。（因此我使用了一个一行的命令对字典进行预处理，将其中的大写字母改为小写字母。）
int charcomp(char *x, char *y) { return *x - *y;}
#define WORDMAX 100
int main(void)
{ char word[WORDMAX], sig[WORDMAX];
while (scanf("%s", word) !=EOF) {
strcpy(sig, word);
qsort(sig, strlen(sig), sizeof(char), charcomp);
printf("%s %s\n", sig, word);
}
return 0;
}while循环每次读取一个字符串到word中，直至文件末尾为止。strcpy函数复制输入单词到单词sig中，然后调用C标准库函数qsort对单词sig中的字母进行排序（参数是待排序的数组、数组的长度、每个待排序项的字节数以及比较两个项的函数名。在本例中，待比较项为单词中的字母）。最后，printf语句依次打印标识、单词本身和换行符。
系统sort程序将所有具有相同标识的单词归拢到一起。squash程序在同一行中将其打印出来。
int main(void)
{ char word[WORDMAX], sig[WORDMAX], oldsig[WORDMAX];
int linenum = 0;
strcpy(oldsig, "");
while (scanf("%s %s", sig, word) != EOF) {
if (strcmp(oldsig, sig) !=0 && linenum >0)
printf("\n");
strcpy(oldsig, sig);
linenum++;
printf("%s ", word);
}
printf("\n");
return 0;
}大部分工作都是使用第二个printf语句来完成的。对每一个输入行，该语句输出第二个字段，后面跟一个空格。if语句捕捉标识之间的差异。如果sig与oldsig（其上一次的值）不同，那么就打印换行符（文件中的第一条记录除外）。最后一个printf输出最后一个换行符。
在使用小输入文件对这些简单部分进行测试后，我通过下面的命令构建了变位词列表：
sign < dictionary | sort | squash >gramlist该命令将文件dictionary输入到程序sign，连接sign的输出至sort，连接sort的输出至squash，并将squash的输出写入文件gramlist。程序的运行时间为18秒：sign用时4秒、sort用时11秒而squash用时3秒。
我在一个包含230 000个单词的字典上运行了该程序。然而，不包括众多的-s和-ed后缀。以下是一些很有趣的变位词类。
subessential suitableness
canter creant cretan nectar recant tanrec trance
caret carte cater crate creat creta react recta trace
destain instead sainted satined
adroitly dilatory idolatry
least setal slate stale steal stela tales
reins resin rinse risen serin siren
constitutionalism misconstitutional① Martin Gardner（1914—），美国著名的科普作家，主持《科学美国人》的数学游戏专栏25年，写作了大量文章和图书，有世界影响。——编者注
②即循环移位。——审校者注
③Doug McIlroy（1932—），著名计算机科学家，美国工程院院士，现为达特茅斯学院兼职教授。他于1968年第一个提出了软件组件的概念。他参与设计了PL/I和C++语言、Multics和Unix操作系统。Unix上许多工具是他开发的，包括diff、echo、sort、spell和join等，管道实现也由他首创。他曾长期担任贝尔实验室计算技术研究部主任，并曾任ACM图灵奖主席。——编者注
④Brian Kernighan（1942—）著名计算机科学家，现为普林斯顿大学教授。他与人合作创造了Awk和AMPL编程语言，对Unix和C语言的设计也有很大贡献。他还与人合写了多部计算机名著，包括与Ritchie合著的The C Programming Language。——编者注
⑤P. J. Plauger，著名C/C++语言专家，现为著名标准库开发商Dinkumware总裁。他曾担任ISO C标准委员会负责人，著有名著《C标准库》（中文版由人民邮电出版社出版）。——编者注
⑥Ken Thompson（1943—），著名计算机科学家，1983年图灵奖得主。现为Google杰出工程师。他是Unix操作系统的主要设计者，并设计了C语言的前身B语言。——编者注
⑦该变位词算法是由许多人各自独立发现的，至少可以追溯到20世纪60年代中期。
⑧Don Knuth（1938—），中文名高德纳，著名计算机科学家，斯坦福大学荣休教授。因对算法分析和编程语言设计领域的贡献获1974年图灵奖。他是名著The Art of Computer Programming的作者，设计了TEX排版系统。——编者注
⑨该书第2版英文影印版已由清华大学出版社引进出版，中文书名《计算机程序设计艺术 第3卷 排序和查找》，中译版已由国防工业出版社出版，中文书名《计算机程序设计艺术 第3卷 排序与查找》。——编者注
⑩Mike Lesk，著名程序员，ACM会士，美国工程院院士，现任Rutgers大学教授兼系主任。他在贝尔实验室工作期间开发了大量工具，包括lex、uucp和stdio.h的前身。他领导了美国NSF数字图书馆计划，该计划支持了斯坦福大学搜索引擎研究项目，促生了Google。——编者注
⑪边栏在杂志的文章中是处在正文之外的，通常是页边上的一列。它们本质上不是专栏的一部分，仅仅提供了关于材料的一些观点。在本书中，它们作为每章的最后一节出现，用“（边栏）”来标记。
本书涵盖了大学算法课中的许多内容，但侧重点不同——我们更强调应用和编码，而不强调数学分析。本附录将有关内容组织成更标准的提纲形式。
问题定义。输出序列是输入序列的一个有序排列。如果输入是文件，则输出通常是另一个文件；如果输入是数组，则输出通常还是该数组。
应用。本列表仅表明了排序应用的多样性。
通用函数。下列算法对任意n元序列进行排序。
答案1.3给出了几种排序算法的运行时间。
专用函数。这些函数能够在特定的输入上得到简短有效的程序。
问题定义。搜索函数判断其输入是否为给定集合的成员，可能还要检索相关的信息。
应用。习题2.6中，Lesk的程序通过搜索电话号码簿，将（编码后的）姓名转换为电话号码。10.8节中Thompson的残局程序通过搜索棋盘来计算最优的走法。13.8节中McIlroy的拼写检查器通过搜索字典来判断单词是否拼写正确。其他应用跟函数一起介绍。
通用函数。下列算法对任意n元集合进行搜索。
专用函数。这些函数能够在特定的输入上得到简短有效的程序。
这些算法用于处理可能包含重复元素的n元集合。
优先级队列。对优先级队列可以进行插入任意元素和删除最小元素这两种操作。14.3节介绍了实现优先级队列的两种顺序结构，并给出了一个用堆高效实现优先级队列的C++类。习题14.4、习题14.5和习题14.8描述了其应用。
选择算法。在习题2.8中我们必须选择出集合中第k个最小的元素，答案11.9给出了一个有效的算法，其他算法见答案2.8、11.1和14.4.c。
2.4节和2.8节计算了字典中的变位词集合。答案9.6描述了几种对字符进行分类的方法。15.1节列出了文件中的不同单词并对每个单词进行了计数，在此过程中先后用到了C++标准模板库和定制的散列表。15.2节用后缀数组查找文本文件中最长的重复子串，15.3节使用了后缀数组的一种变体由马尔可夫模型生成随机文本。
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种算法，该章中有几个问题跟向量与矩阵有关。
对生成伪随机整数的函数的使用贯穿全书，这些函数在答案12.1中实现。12.3节描述了一个“打乱”数组中元素的算法。12.1节到12.3节描述了选择集合中随机子集的几种算法（另见习题12.7和习题12.9）。习题1.4给出了该算法的应用。答案12.10给出了从一组数量未知的对象中随机选择一个的算法。
答案2.3给出了计算两个整数的最大公约数的欧几里得算法。习题3.2讨论了对常系数线性递归求值的算法。习题4.9给出了计算正整数次幂的高效算法代码。习题9.11通过查表计算三角函数。答案9.12描述了对多项式求值的Horner方法。习题11.1和习题14.4.b描述了如何对大型浮点数集合求和。
