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

　　第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

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

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