计算机程序设计艺术（第3卷 英文版·第2版）
豆瓣
排序与查找
Donald E.Knuth
简介
《计算机程序设计艺术》系列被公认为计算机科学领域的权威之作，深入阐述了程序设计理论，对计算机领域的发展有着极为深远的影响。本书是该系列的第3卷，扩展了第1卷中信息结构的内容，主要讲排序和查找。书中对排序和查找算法进行了详细的介绍，并对各种算法的效率做了大量的分析。 本书适合从事计算机科学、计算数学等各方面工作的人员阅读，也适合高等院校相关专业的师生作为教学参考书，对于想深入理解计算机算法的读者，是一份必不可少的珍品。
contents
Chapter 5 Sorting 1
*5.1. Combinatorial Properties of Permutations 11
*5.1.1. Inversions 11
*5.1.2. Permutations of a Multiset 22
*5.1.3. Runs 35
*5.1.4. Tableaux and Involutions 47
5.2. Internal sorting 73
5.2.1. Sorting by Insertion 80
5.2.2. Sorting by Exchanging 105
5.2.3. Sorting by Selection 138
5.2.4. Sorting by Merging 158
5.2.5. Sorting by Distribution 168
5.3. Optimum Sorting 180
5.3.1. Minimum-Comparison Sorting 180
*5.3.2. Minimum-Comparison Merging 197
*5.3.3. Minimum-Comparison Selection 207
*5.3.4. Networks for Sorting 219
5.4. External Sorting 248
5.4.1. Multiway Merging and Replacement Selection 252
*5.4.2. The Polyphase Merge 267
*5.4.3. The Cascade Merge 288
*5.4.4. Reading Tape Backwards 299
*5.4.5. The Oscillating Sort 311
*5.4.6. Practical Considerations for Tape Merging 317
*5.4.7. External Radix Sorting 343
*5.4.8. Two-Tape Sorting 348
*5.4.9. Disks and Drums356
5.5. Summary, History, and Bibliography 380
Chapter 6 Searching 392
6.1. Sequential Searching 396
6.2. Searching by Comparison of Keys 409
6.2.1. Searching an Ordered Table 409
6.2.2. Binary Tree Searching 426
6.2.3. Balanced Trees 458
6.2.4. Multiway Trees 481
6.3. Digital Searching 492
6.4. Hashing 513
6.5. Retrieval on Secondary Keys 559
Answers to Exercises 584
Appendix A Tables of Numerical Quantities 748
1. Fundamental Constants (decimal) 748
2. Fundamental Constants (octal) 749
3. Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers 750
Appendix B Index to Notations 752
Index and Glossary 757
