计算机程序设计艺术(第3卷)-排序和查找(英文影印版)

出版时间：2002-9  出版社：清华大学出版社  作者：（美）Donald E.Knuth  页数：780  
Tag标签：无  

内容概要

这是对第3卷的头一次修订，不仅是对经典计算机排序和查找技术的最全面介绍，而且还对第1卷中的数据结构处理技术作了进一步的扩充，通盘考虑了将大小型数据库和内外存储器。它遴选了一些经过反复检验的计算机方法，并对其效率做了定量分析。第3卷的突出特点是对“最优排序”一节作了修订，对排列论原理与通用散列法作了全新讨论。

作者简介

Donald.E.Knuth（唐纳德.E.克努特，中文名高德纳）是算法和程序设计技术的先驱者，是计算机排版系统TEX和METAFONT的发明者，他因这些成就和大量创造性的影响深远的著作(19部书和160篇论文)而誉满全球。作为斯坦福大学计算机程序设计艺术的荣誉退休教授，他当前正全神贯注于完

书籍目录

Chapter 5 Sorting　5.1 Combinatorial Properties of Permutations    5.1.1 Inversions    5.1.2 Permutations of a Multiset    5.1.3 Runs    5.1.4 Tableaux and Involutions　5.2 Internal sorting    5.2.1 Sorting by Insertion    5.2.2 Sorting by Exchanging    5.2.3 Sorting by Selection    5.2.4 Sorting by Merging    5.2.5 Sorting by Distribution　5.3 Optimum Sorting    5.3.1 Minimum-Comparison Sorting    5.3.2 Minimum-Comparison Merging    5.3.3 Minimum-Comparison Selection    5.3.4 Networks for Sorting　5.4 External Sorting    5.4.1 Multiway Merging and Replacement Selection    5.4.2 The Polyphase Merge    5.4.3 The Cascade Merge    5.4.4 Reading Tape Backwards    5.4.5 The Oscillating Sort    5.4.6 Practical Considerations for Tape Merging    5.4.7 External Radix Sorting    5.4.8 Two-Tape Sorting    5.4.9 Disks and Drums　5.5 Summary, History, and BibliographyChapter 6 Searching　6.1 Sequential Searching　6.2 Searching by Comparison of Keys　　6.2.1 Searching an Ordered Table　　6.2.2 Binary Tree Searching　　6.2.3 Balanced Trees　　6.2.4 Multiway Trees　6.3 Digital Searching　6.4 Hashing　6.5 Retrieval on Secondary KeysAnswers to ExercisesAppendix A: Tables of Numerical Quantities　1 Fundamental Constants (decimal)  2 Fundamental Constants (octal)  3 Harmonic Numbers, Bernoulli Numbers, Fibonacci NumbersAppendix B:Index to NotationsIndex and Glossary

用户评论 (总计10条)

•   本书是计算机方面的一本经典巨著,从计算机基础原理到程序设计原理及算法都是深入的讲解,书很长,要用心看.很多当前学习的教科书上的算法都来自于这里.
•   计算机不朽的名著，可惜没有中文版。。。
•   还差的二卷
•   真正的经典，值得收藏
•   不用说了，此书很经典。送书速度还可以
•   　　本科时候对于这本书慕名很久，可是当时由于没时间没钱，所以拖到现在才把这一套买过来开始看。现在看了快半个月了，在这里写一下体会。
  　　高老爷子在六十年代的时候就开始写这本书，当时只是受wesley出版社之邀写一下关于编译器的内容。高老爷子当时就接下来这个任务，可是一旦开笔就发现收不住了，内容也不仅限于编译这方面，直接把当时重要点的算法全都包含了。按照老爷子的计划，他这套书要出七卷，而编译是最后一卷，现在才出到第四卷a-组合算法。此外由于高老爷子当年写这套书的时候，计算机科学还基本处于蛮荒时代，各路汇编语言群雄并起，谁要是用高级语言都不好意思跟人打招呼。第一卷出现在1968年，第二卷出现在1969年，第三卷出现在1973年。而c语言在1972年才诞生在贝尔实验室，1976年才被广泛接受，pascal也是出现在60年代末。这之前高级点的语言也就是什么fortran,PL/I,combo之类的，基本都是一些领域特定的语言，对于描述算法这方面没啥帮助。于是高老爷子自己编了一个汇编语言-MIX,这个汇编语言跟现在的汇编有很大的出入，最要命的是他的数据存储格式在现在看来是完全无法理解的。三十多年后，高老爷子觉得MIX这个祸害再存在下去简直就是让他丢脸，因此重新设计了一个更符合现代样式的mmix来替代mix。其实我觉得直接用c来替代mix多好，毕竟c有指针有位操作，而且这样写出来的程序更好理解。mmix的特别之处是有256个通用寄存器，因此函数调用的时候可以不去劳烦内存栈来保存当前信息，直接把这些寄存器当作一个寄存器栈。
  　　事实上完全没必要去懂这些汇编语言，如果读者的目标只是去了解算法的话。因为高老爷子非要加进这个汇编语言，是为了算法性能分析的简便。其实完全架空汇编来进行算法分析也是可以的，但是这样可能需要更多的参数。如果真的想学mmix的话，则需要看mmixware这本书，里面介绍了许多底层的东西，值得一看。
  　　 谈完了令人不爽的汇编，接下来谈下数学。数学在这套书里是非常重要的，很多章节都有很多内容是对数学爱好者准备的。对于数学基础，老爷子在开头谦虚的说不需要多少，有个高中水平加上我的第一章就可以搞定了。于是你自信满满的开向第一章，于是你跪了。对于数学方面，个人推荐离散数学加上具体数学加上微积分加上概率论与统计加上生成函数论(mother function)。学了这些之后，再去把第一章乱棍打死吧。如果数学没掌握好，到后面那些一大串一大串的数学符号就会像唐僧念经一样的折磨你。
  　　 谈完数学，那就谈算法吧。其实这本书里面算法没谈很多，全书基本就是在进行算法性能分析，连常数项都不放过。算法一般就先用一点文字介绍一下，然后伪代码似的描述一下流程，然后是mix代码写一下，然后再用实际数据跑一遍，然后就开始连篇累牍的数学分析了。如果不是对算法性能了解要求很苛刻，而只是想了解一下算法的思想和实现及应用的话，推荐使用其他的书。下面就对应各章说一下相应的参考书吧。
  　　 第二章：基本数据结构及动态内存分配。基本数据结构方面随便哪本书都讲烂了，个人推荐一下算法导论，因为里面有红黑树、斐波那契堆、b树、二项堆。动态内存分配这边，书里对于伙伴法和链接法分析的头头是道，不过当前应用的主要是红黑树或者avl。linux是红黑，windows是avl；这两个都是有源代码可以查的。linux的内核源代码随便哪个发行版里面都有，windows则可以参考wrk和windows内核原理与实现。
  　　 第三章：随机数生成。第四章：算术。随机数生成基本没有书会提到这方面的内容，现有的见过的几本提到此内容的书也是直接把本书当作最主要的参考文献来看的。而且高老爷子对于验证数据的随机性方面着墨很多，这些内容基本上就是权威了。其实如果真的去看里面关于随机性的介绍估计得烦死，推荐大家看一下线性同余那些内容就行了。毕竟这一章头一页就说了通过纯数学操作来生成随机数都是不科学的，真的要随机数咱们还得去自然界找答案。算术里面关于浮点数的那些部分基本可以作废，因为不是按照ieee754标准来的，不过作业里面有些内容是跟这个标准有关的，推荐做一下，那些问题的提出人都是这个标准的制定者。如果想了解一下ieee754的话，推荐看一下csapp里面相应的章节。除了浮点数这部分，这一章剩下的内容主要包括最大公因数算法及其扩展、质数理论、多项式操作、快速乘法及最快幂乘。关于质数方面可以参考一下clrs的数论那章，多项式乘法及大数乘法也可以参考clrs里面的快速傅里叶变换那章。最快幂乘的应用范围也就是RSA加密了，如果做加密的同学可以试图去了解一下。多项式除法及多项式因式分解这两个内容我没怎么关注，读者自己去看吧。
  　　 第五章：排序。对于内部排序的话，这里可以拿高老爷子的徒弟Robert Sedgewick写的c算法来看，而且这本c算法里面的图非常形象，但是严格的算法性能分析还是得靠这本。其实clrs也相当不错，里面的练习也很好。但是对于外部排序，本书介绍的十分详尽，有好几节的内容，而在c算法中也就四五页。对于外部排序有需要的同志就下大力气研究一下本书吧，虽然我不知道在当前内存条件下这个东西还有什么大用场。
  　　 第六章：搜索。这里面最重要的内容就是hash了。推荐读者重点看一下这一节。可以通过算法导论来辅助学习，相对来说算法导论里面就分析的直接了当。顺便推荐一个相关的链接：http://www.cnblogs.com/egmkang/archive/2012/01/18/2325474.html 第七章：生成所有排列和组合。其实里面排列组合的内容只占一半。开头的二进制技巧那一节对于我等新手来说很好玩，其实对于这部分内容可以直接看一下《hacker's delight》，里面的东西还更多。对于BDD这一节，我是因为没有接触过此内容，因此这里对我的吸引力并不大，加上高老爷子书的排版及其令人发指，我就压根没看完这一节。对于排列和组合部分，书中对于流程的描述非常令人发指，很难让我理解他在说什么，得看好几次，远逊于算法导论。此外本章最大的缺点就是里面描述的那些算法很多都不是最佳的。本书出版之后又出来了几篇论文，对于排列生成、组合生成、集合划分、集合的固定子集数划分、包含重复元素的集合固定子集数划分等内容都有了线性时间的算法。
  　　 第七章续：图算法。可以直接拿c算法的第二部分图算法去看。如果想研究更多的话，需要参考一下离散数学里面的图论，及计算几何学的内容。
  　　 第八章：递归。第九章：词法分析。第十章：语法分析。第六册：上下文无关文法。这部分内容用编译原理加上hopcroft的形式语言自动机与计算导论就可以cover掉，高老爷子在这里应该玩不出什么花样。
  　　 第七册：编译器技术。现代体系的优化编译器和高级编译器设计，一个对应向量机，一个对应标量机。这两本书已经走到了顶峰，没必要看其他的了。
  　　 最后加一下算法思想：对于只想研究算法的设计与应用而不想把大好青春浪费在算法分析上的同志们来说，算法导论和算法设计是不二选择。
  　　 对于本套图书，希望买了的人先把这套书基本过一遍，给自己留一个初步的映像。数学分析部分可以掠过不看，只需要知道这些数学分析在分析什么就行。毕竟要是都看完的话需要好几年的时间。看完这一遍就基本可以把它放在书架上陈列了，别指望坐公交的时候闲的没事翻，太重了，也太二了。等到将来的工作涉及到其中的一部分内容的时候再拿出来仔细翻吧。
  　　
•   这套书不是用来学习算法的，重点是在习题部分。个人目前可以做到大概30分级别。个人方法论还需要修炼提升，希望两年内能做到35分这个级别。
  　　
•   的确，算法分析已经到了连篇累牍的程度。让我感觉这不是在看一本计算机科学的书，完全就是超高级组合离散概率统计。给我两年，我情愿去做编译器的后端优化。
•   人各有志，每个人的追求不一样，对这套书的感觉也不一样。我是把它作为一种实践方式，用以修炼我的方法论。实际上第四卷对于我的目的来说更合适。
•   这本书的写作风格和艺术造诣无出其右