计算机程序设计艺术 第3卷 排序与查找 （第2版）

　　[center][a href="#" onclick='winpop(7544);return false;'][img src=/computers/ebook/7544/cover.gif border=0][/a][/center]
　　
　　 卷3为分拣和搜索，这是本书的第1个修订版，它是对计算机分拣和搜索的一流技术的最全面的研究，它扩展了卷1中数据结构的处理方法，将大小数据库以及内存和外部存储都包含在内。本书包括对计算机方法仔细检查的选择方案，和其效率的大量分析。本书该版的独特之处在于优化了的分拣，以及对通用散列法和排列法的新的理论论述。
　　
　　 [a href="http://www.china-pub.com/computers/common/info.asp?id=7469" target="_blank"][b]《计算机程序设计艺术（英文影印版）》（1-3卷精装全套）[/b][/a]
　　
　　 [a href="http://www.china-pub.com/computers/bookinfo/hy.htm" target="_blank"]翻译《计算机程序设计艺术》经过的片断回忆苏运霖[/a]

第5章 排序
5．1 排列的组合性质
5．1．1 反序
5．1．2 多重集合的排列
5．1．3 路段
5．1．4 图表和对合
5．2 内部排序
5．2．1 通过插入进行排序
5．2．2 通过交换进行排序
5．2．3 通过选择进行排序
5．2．4 通过合并进行排序
5．2．5 通过分布进行排序
5．3 最优排序
5．3．1 极少比较排序
5．3．2 极少比较合并
5．3．3 极少比较选择
5．3．4 排序网络
5．4 外部排序
5．4．1 多路合并和替代选择
5．4．2 多阶段合并

　　 cookery is become on art，a noble science；cooks are gentlemen
　　 烹调法成了一种艺术，一门高深的科学；厨师是有教养的人。
　　 --TITUS LIVUS，Ab Urbe Condito XXXIX,vi（Robert Burton, Anatomy of Melancholy 1,2,2,2）
　　 本书形成了第1卷第2章关于信息结构内容的自然续篇，因为它为第1卷的基本结构化思想增加了线性有序数据的概念。
　　 本书书名"排序与查找"可能给人以印象，仿佛它仅仅是为那些关。已通用排序程序编制或信息检索应用的系统程序员编写的。然而，事实上排序与查找的领域还提供了一个理想的园地，以讨论范围广泛而且很重要的一般性问题：
　　 如何发现好的算法？
　　 如何改进给定的算法或程序？
　　 如何从数学上分析算法的效率？
　　 ·对于相同的任务，人们如何在不同的算法之间进行合理的选择？
　　 ·在什么意义之下，可以证明某个算法是"振好"的？
　　 ·计算理论同实际考虑如何相互影响，
　　 ·像磁带、磁鼓或磁盘这样的外存，如何能有效地用于大型数据库？
　　 其实，我确信，程序设计的每一个重要方面，实际上都离不开排序或查找！
　　 本卷由全套书的第5章和第6章组成。第5章讨论的是排序；这是一个很大的课题，已经把它主要划分成两大部分，即内部排序和外部排序。还有补充的几节，提出了关于排列（5．1节）和最优排序算法（5．3节）的辅助理论。第6章讨论了在表或文件中查找特定项目的问题；这又细分成顺序查找、通过键码（key）比较查找、按数字性质查找、"散列"查找等几种方法，而后考虑了比较困难的辅键码（secondary key）查找问题。在这两章之间存在着令人惊奇的相互影响以及强烈的类似。除了在第2章中所讨论的信息结构以外，这里还讨论了信息结构的两种重要的变形，即优先队列（5．2．3小节）和表示成平衡树的线性表（6．2．3小节）。
　　 和第1卷及第2卷一样，本书包括了大量在其它出版物上从未出现过的许多内容。许多人善意地写信或口头向我表达了他们的看法，我希望，当我以我自己的文字来表现这些内容的时候，我没有很糟糕地曲解它们。
　　 我未曾有时间系统地查找专利文献；确实，我蔑视当前寻求算法专利的倾向（参见5．4．5小节）。如果某人把在本书中未曾引用的有关专利的一个副本寄给我，那我将在未来的版本中恭敬地弓佣它。然而我要鼓励人们继续发扬悠久的数学传统，把最新发现的算法投进公众领域。与其防范地人从某个人对计算机科学的贡献中获益，不如寻求其它更好的谋生手段。因为它与防范自己的计算机成果被他人利用相比会给人们带来更好的生活。
　　 在我从教学工作上退休下来之前，我曾把这本书用作大学三年级至研究生层次数据结构第二门课的教材，并省略掉了大部分数学内容。我也曾使用本书的数学部分作为研究生层次算法分析课程的基础，并特别强调了5．l，5．2．2，6．3和6．4诸节。关于具体的计算复杂性方面的研究生课程也可以以5．3节和5．4．4小节，以及第2卷的4．3．3，4．6．3和4．6．4诸小节为基础。
　　 除了偶尔讨论第1卷中说明的MIX计算机外，本书的绝大部分内容都是独立、自成体系的。附录B包含有对于所使用的数学记号的概述，其中的一些记号同传统的数学书中找到的记号有些差别。
　　 第2版前言
　　 这个新版本是同第五卷及第2卷的第3版相匹配的。那两卷的出版用上了TEX和METAFONT系统，使我得以庆祝这两个专门为本套书开发的出版系统的完成。