计算机程序设计艺术（第3卷 英文版·第2版）

出版时间：201009  出版社：人民邮电出版社  作者：Donald E.Knuth  页数：780  
Tag标签：无  

前言

本书是第1卷的第2章中有关信息结构内容的自然延续，因为它为其他基本结构化思想增加了线性有序数据的概念。书名中的“排序与查找”可能会使人误以为本书面向的只是从事一般性排序工作或信息检索工作的系统程序员。事实上，排序与查找为讨论众多重要的一般性问题提供了一个理想的框架：·好算法是怎么发现的？·如何改进给定的算法和程序？·如何从数学的角度分析算法的效率？·对于给定的任务，如何在不同的算法之间做出合理的选择？·在什么意义下，可以证明算法是“最可行的”？·计算理论同实际考虑如何相互影响？·如何将磁带、磁鼓或磁盘这样的外存有效应用于大型数据库？事实上，我认为程序设计的几乎所有重要的方面都与排序或查找有关！本卷包含整套书中的第5章和第6章。第5章讨论排序，这个大问题主要划分成两个部分，即内部排序和外部排序。此外，这一章还有几个辅助性小节，讨论了有关排列（5.1节）和最优排序方法（5.3节）的辅助理论。第6章讨论在表或文件中查找特定项的问题，该问题可以分为顺序查找、通过比较键进行查找、按数位性质进行查找以及散列法查找等，然后讨论了更难的辅键查找问题。这两章内容有着惊人的相互影响和很强的相似性。除了第2章介绍的信息结构外，本书还讨论了两种重要的信息结构，即优先队列（5.2.3节）和表示成平衡树的线性表（6.2.3节）。与第l卷和第2卷一样，本书包含了其他出版物所没有的许多内容。许多人曾经以书面或口头的形式向我表达了他们的思想，我希望在用自己的语言表述时没有过度地歪曲他们的原意。

内容概要

《计算机程序设计艺术》系列被公认为计算机科学领域的权威之作，深入阐述了程序设计理论，对计算机领域的发展有着极为深远的影响。本书是该系列的第3 卷，扩展了第1 卷中信息结构的内容，主要讲排序和查找。书中对排序和查找算法进行了详细的介绍，并对各种算法的效率做了大量的分析。　　本书适合从事计算机科学、计算数学等各方面工作的人员阅读，也适合高等院校相关专业的师生作为教学参考书，对于想深入理解计算机算法的读者，是一份必不可少的珍品。

作者简介

　Donald E.Knuth 
　　算法和程序设计技术的先驱者，是计算机排版系统TEX和METAFONT的发明者。 Donald.E.Knuth(唐纳德.E.克努特，中文名高德纳)是斯坦福大学计算机程序设计艺术的荣誉退休教授，Knuth教授获得了许多奖项和荣誉，包括美国计算机协会图灵奖(ACM Turing Award)

书籍目录

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 bibliography　  chapter 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 keys　　　　answers to exercises 　appendix a tables of numerical quantities 　1. fundamental constants (decimal)　  　2. fundamental constants (octal)　  　3. harmonic numbers, bernoulli numbers, fibonacci numbers appendix b index to notations　 index and glossary

章节摘录

插图：

媒体关注与评论

这一多卷本的鸿篇巨著被公认为是对经典计算机科学的权威论述，数十年来，前3卷一直是广大学生、研究人员和业内人士学习程序设计理论和实践的无价之宝。这是一部包含一切基础算法的宝典，是它教给了这一代软件开发人员关于计算机程序设计的绝大多数知识。　　——Byte杂志1995年9月刊无数的读者谈到过Knuth的著作对于自己的深刻影响。从事研究的人惊讶于他精美优雅的分析，而普通程序员则一直在卓有成效地利用书中提供的各种方案解决日常问题。这些书展现了作者的博观、清晰、精确和幽默，所有的人都钦佩不已。我简直说不清楚这些书给我的学习和娱乐带来了多少欢乐时光。我在各种场合一有空就仔细研读，在车上，在餐馆，上班时，回到家里……甚至有次观看我儿子的球赛，趁他没上场的时候，我还拿出来看了一阵子。　　——Charles Long它本来是当参考书写的，但有些人却发现每一卷都可以兴致勃勃地从头读到尾。有位中国的程序员甚至把它比做读诗。如果你自以为是一个很好的程序员，请去读读Knuth的《计算机程序设计艺术》吧……要是你真把它读下来了，就毫无疑问可以给我递简历了。　　——比尔·盖茨不管你的背景如何，只要你想认真地编写计算机程序。都有很好的理由把这套书的每一卷抱回家。便于研究和工作时随时翻阅。20年来Knuth第一次全部修订了这3卷。我发现，只要翻一翻这些书，就会立竿见影地“镇住”计算机。　　——Jonathan Laventhol

编辑推荐

《计算机程序设计艺术 卷3:排序与查找(英文版·第2版)》：《计算机程序设计艺术》系列著作对计算机领域产生了深远的影响。这一系列堪称一项浩大的工程，自1962年开始编写，计划出版7卷，目前已经出版了4卷。《美国科学家》杂志曾将这套书与爱因斯坦的《相对论》等书并列称为20世纪最重要的12本物理学著作。目前Knuth正将毕生精力投入到这部史诗性著作的撰写中。

用户评论 (总计50条)

•   在大学教材中的排序与查找一般不作深入解释，简单几个知名点的算法便把排序与查找一笔带过，看过高德纳的排序与查找，便是见识到了此算法的真义，算是有恍然大悟之感啊！
•   排序和超找算法的圣经
•   虽然英文版，但看起来还是能看懂，就是数学功底要深，每看完一点都觉得对数学和算法方面了解的深一点，很练脑子。
•   计算机科学圣经
•   算法的书看了不少，三驾马车也看完了，刚开始读大致翻了翻这本书给我的感觉就是根源的感觉
•   计算机工业的灵魂之作
•   算法上帝送给世人的礼物经典中的经典，神来之笔
•   包装很好，计算机专业必备
•   不错的计算机书籍
•   高德纳的经典著作，仰视吧，凡人
•   恰逢优惠活动，满300-100，立刻入手1、3、4卷（2卷暂缺没货），划算~塑封的，书保护的很好，纸箱很结实！赞！捧着牛津词典，啃下去~~~作者的文笔很好，英文并不晦涩，不愧大师之作！
•   有完美情怀，卷1还没看完，还是想把卷2，3给买齐了，以后有机会再看。
•   本来想买第一卷，结果错买成第三卷了，哎，也不错
•   随着研究IT技术书籍的深入，发现最终的参考资料都是本书。尤其是红黑树等对我帮助很大。
•   有时间好好拜读，需要有一定的数学功底，英语功底。书的内容自然犀利。。
•   收到书的时候无比激动，看书的感觉就是讲的无比深刻细致入微。
•   非常好，大师之作
•   拿本牛津查书，边看边做笔记。感觉英语水平提高不少
•   大家之作，经典，值得拥有
•   还没有来得及看，不过大师的作品错不了
•   这本还没读到，只是大概翻阅了一下，感觉大多是数学知识。
•   先复习一下数学，然后再看这本书吧，现在看不一定能看懂！
•   需要很好的数学基础
•   经典书籍，慢慢研读，纸张不错，经久耐用
•   读经典是需要时间的，经典是不需要评分的
•   经典书籍，值得品味
•   读完了，你就是牛人，有点难，正常
•   the colour is a little different (from vol 1),also it's 2nd edition (while vol 1 isrd).
•   大师的书,需要花时间慢慢研读
•   太难了，中文看起来都很吃力，何况英文。不过真是好资料
•   看着稍微口吃力，受益无限值得收蔵
•   可看、可学、可收藏。程序员必备利器
•   如果需要就买吧，呵呵。嗯，装帧印刷什么无懈可击
•   ACM图灵奖最年轻的一位活得真，我是奔着大牛的声望来的，想学好算法，希望大牛的书能让我不虚此行，打好我的算法基础。
•   书包装不错，印刷质量可以！回来慢慢阅读！
•   包裹做得很结实，但打开一看却发现书的侧面较脏，且外皮有破损，纸张的颜色略偏灰白色。偶有黑色斑点，印刷质量还算令人满意.本想买此书用于收藏, 现在来看，呃，还是放在案头作学习参考用吧.
•   书弄的很脏，包裹做得还行，侧面较脏，外皮破损
•   印刷质量很好,终于拜读到大师的作品,很激动,如果整套价钱能再优惠多点,打算整套买了
•   没什么可说的，绝对经典
•   好书，加上质量好，再加上原版图书，你怎么能不购买呢？
•   得有一定的算法\数学\英语基础才能看懂，为什么前两卷是第三版，第三卷出的是第二版？
•   经典中的经典，印刷精美，值得收藏！
•   经典作品，不过里面有一页装订错误 略不爽
•   是英文版，，慢慢啃，作者在这书上也费了不少心血阿
•   装订精美，不错！内容，呵呵，经典得没法说！后面题目有些很难！
•   满减的时候买的，攒起了4卷
•   这个没的说，经典名著，值得拥有
•   计算机程序设计艺术（卷3）：排序与查找
•   计算机科学的经典书籍
•   计算机的经典书籍