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

“计算机科学既壮观又幽美，我尝试尽自己所能，以十分恰当的方式来解释我所了解的某些片断。很显然，我自己并没有任何超自然能力，但的确很喜欢讲述那些似乎静静地等待着人们去讲出来的故事。写书跟讲故事十分类似。” 

——图灵访谈之专访Donald E. Knuth 

《计算机程序设计艺术》系列著作被公认为是对经典计算机科学的经典论述，曾在1999年被《美国科学家》期刊评选为20世纪相当重要的12部学术专著之一。这一宏伟浩大的工程始于1962年，计划出版7卷，目前已经出版了4卷。数十年来，这本书一直是广大学生、研究人员和业内人士学习程序设计理论和实践的无价之宝，书中各处无不体现着作者渊博的学识、严谨的治学态度，以及深刻的洞察力。该套书自出版以来，广受众多科学家的赞许，并对无数读者产生了极其深远的影响。 

《计算机程序设计艺术》堪称计算机科学领域的瑰宝。从事研究的人惊艳于其精美优雅的分析，而普通程序员则一直在卓有成效地利用书中提供的各种方案解决日常问题。这些书展现了作者的博观、清晰和幽默，所有的人都钦佩不已。高德纳是算法和程序设计领域的先驱者，对计算机科学发展史也有着深入的研究，书中在介绍众多理论的同时，也给出了相关的历史和发展历程，成为本书的一大特色。

豆瓣评分9.0以上的编程书，了解一下？（下篇）

《计算机程序设计艺术》系列被公认为计算机科学领域的经典之作，深入阐述了程序设计理论，对计算机领域的发展有着极为深远的影响。本书为该系列的第3卷，全面讲述了排序和查找算法。书中扩展了卷1中数据结构的处理方法，并对各种算法的效率进行了大量的分析。

高德纳（Donald E. Knuth）知名计算机科学家，算法与程序设计技术的先驱者、斯坦福大学计算机系荣休教授、计算机排版系统TEX和METAFONT字体系统的发明人，因诸多成就以及大量富于创造力和具有深远影响的著作（19部书，160篇论文）而誉满全球。近些年，他将精力全部投入到《计算机程序设计艺术》七卷集的史诗般创作中。Knuth教授获得过许多奖项和荣誉，包括美国计算机协会图灵奖、美国国家科学奖章、美国数学学会的斯蒂尔奖，以及因发明先进技术于1996年荣获的京都奖。1996年，设立了以其名字命名的Donald E. Knuth奖，授予那些为计算机科学基础做出杰出贡献的人。

第5 章排序. . . . . . . . . 1

*5.1　排序的组合性质. . . 　8

*5.1.1　反序. . . . . . . 　8

*5.1.2　多重集的排列. . . 　16

*5.1.3　游程. . . . . .. .　36

5.2　内部排序. . . . . . .　56

5.2.1　插入排序. . . . . .　61

5.2.2　交换排序. . . . . .　81

5.2.3　选择排序. . . . . .　107

5.2.4　合并排序. . . . . .　123

5.2.5　分布排序. . . . . .　131

5.3　最优排序. . . . . . .　140

5.3.1　比较次数最少的排序.　140

*5.3.2　比较次数最少的合并. 153

*5.3.3　比较次数最少的选择. 161

*5.3.4　排序网络. . . .. .　171

5.4　外部排序. . . . . . .　194

5.4.1　多路合并和替代选择.　197

*5.4.2　多阶段合并. . . . 　208

*5.4.3　级联合并. . . . . 　226

*5.4.4　反向读取磁带. . . 　235

*5.4.5　振荡排序. . . . . 　245

*5.4.6　磁带合并的实践考虑. 250

*5.4.7　外部基数排序. . . . 269

*5.4.8　双磁带排序. . . . 273

*5.4.9　磁盘与磁鼓. . . . 　279

5.5　小结、历史与文献. . .　297

第6　章查找. . . . . . . .　306

6.1　顺序查找. . . . . . . 308

6.2　通过键的比较进行查找. .318

6.2.1　查找有序表. . . . . 318

6.2.2　二叉树查找. . . . .　332

6.2.3　平衡树. . . . . . .　358

6.2.4　多路树. . . . . . .　376

6.3　数字查找. . . . . . .　385

6.4　散列. . . . . . . . . .402

6.5　辅助键的查找. . . . . .437