JAVA算法（第3版·第1卷）

    书籍
    计算机书籍
《Java算法》用Java语言全面实现了当今最重要的计算机算法，并用大量图表和数学公式对算法进行了详尽的描述和分析。全书共分3卷，本书是其中的第1卷（第1至第4部分）。内容包括基本概念（第1部分）、数据结构（第2部分）、排序算法（第3部分）和查找算法（第4部分）。
本书概念清楚，内容翔实、新颖，由浅入深地描述了算法。本书可作为高等院校计算机相关专业本科生和研究生的教材和补充读物，也可供Java爱好者及相关领域工程技术人员参考。

Robert Sedgewick是斯坦福大学博士，现任普林斯顿大学计算机系教授。他是Adobe Systems公司总监，兼任Xerox PARC,IDA和INRIA等公司的研发顾问。他还与PhilippeFlajolet合著了《算法分析入门》一书。
赵文进 现就读于中国人民解放军电子工程学院，攻读博士学位。1999年硕士毕业于中国人民解放军电子工程学院计算机应用专业，1999年至2003年在中国人民解放军电子工程学院系统工程教研室任教，担任过《数据结构》、《离散数学》、《数据库系统》、《操作系统》等计算机主干课程的教学，并参与了很多专业资料及教材的翻译工作，作为主要翻译人员之一的《信息战与信息安全》已由电子工业出版社出版。

第1部分 基础部分
第1章 介绍
1.1 算法
1.2 事例：连通性
1.3 合并-查找算法
1.4 展望
1.5 主题总结
第2章 算法分析准则
2.1 实现和实验分析
2.2 算法分析
2.3 函数的增长
2.4 大O表示法
2.5 基本递归
2.6 算法分析示例
2.7 保证、预测和限制
第1部分的参考文献
第2部分 数据结构
第3章 基本数据结构
3.1 构建块
3.2 数组

　　 本书是3卷中的第1卷，整个3卷的内容纵览了当今使用的最重要的计算机算法。第1卷(第1～4部分)涵盖了基本概念(第1部分)、数据结构(第2部分)、排序算法(第3部分)和查找算法(第4部分)；第2卷(第5部分)涵盖了图形和图算法；第3卷(第6～8部分)涵盖了字符串(第6部分)、计算几何学(第7部分)以及高级算法和应用(第8部分)。
　　 本书不仅是目前最具广度和深度的介绍计算机经典算法(包括数据结构)的书，而且还是用标准的Java语言描述算法(书中还对每条表达语句进行了精确的描述)，而不是用C、C++、Pascal或伪代码来描述算法(这样的书已经很多了)。这些算法程序可以直接用在实际编程中，对编程人员、Java爱好者、学生以及从事计算机教学的教师来说是一本很好的参考书。
　　 本书的作者Robert Sedgewick教授在普林斯顿大学计算机系任教。他在Adobe系统公司担任总监职位，并担任过Xerox PARC、IDA和INRIA等项目的研究人员。他从斯坦福大学获得了博士学位，是算法宗师Donald E．Knuth的门下高徒。
　　 在翻译本书的过程中，译者深刻地体会到了本书的几大特色：
　　 · 由浅入深地介绍数据结构之上的经典算法，先给出基本实现，在此基础上，再进行详细分析，不断改进。
　　 · 对每个具体的议题，都给出很多Java程序的实现，并用性质和图表对分析进行说明和佐证。
　　 · 每一节后面都有大量习题，且这些习题根据目的的不同而分成几类，用不同的注释符进行标记(见书的前言部分)。读者可根据需要做相应的习题。
　　 本书原文中长句非常之多，在翻译的过程中，译者尽可能地在保留原文风格的基础上，把原著的意思准确、浅显地表达出来。整个翻译工作经历了炎热的夏天和严寒的冬天，其中的艰辛只有译者自知，但若本书的出版能为中国的计算机事业贡献一点力量，译者就深感付出的努力是值得的。
　　 感谢罗卫星、吴志勇、徐强、张勉、王康、任彪、钟高贤、朱鸿、赵亭、张敬业等参与了翻译工作。还要特别感谢车立红编辑对本书进行了细致的审稿工作，我们之间的合作非常愉快，对书中的每个疑点用E-mail传讯推敲，直到有一个满意的译文为止。同时，深深感谢我的家人对我工作的大力支持。
　　 赵文进
　　 2004年4月5日于合肥
　　

　　 本书是3卷中的第1卷，整个3卷的内容涵盖了当今使用的最重要的计算机算法。第1卷(第1～4部分)介绍了基本概念(第1部分)、数据结构(第2部分)、排序算法(第3部分)、查找算法(第4部分)；第2卷(第5部分)介绍了图和图算法；第3卷(第6～8部分)(尚未出版)介绍了字符串(第6部分)、计算几何学(第7部分)、高级算法和应用(第8部分)。
　　 在学生已经具备了基本的编程技能并熟悉计算机系统之后，且在他们上计算机科学或计算机应用高级领域的专业课程之前，可将这3卷书作为计算机科学早期课程的教材。由于这3卷书包括了有用算法的实现和这些算法性能的详细信息，所以它们也适用于自学，或作为从事计算机系统开发和应用程序开发人员的参考书。这套书的作者的视野广阔，因此很适合把这些书作为该领域的入门书籍。
　　 这3卷书的前期版本多年来一直被世界各地的学生和编程人员广泛使用，第3版由这3卷书构成。我完全重写了这一版的内容，并增加了数千个新习题、上百幅新图、许多新程序以及对所有图和程序的详细注释。新版书不仅涵盖了一些新议题，而且对一些经典算法提供了更详细的解释。贯彻全书的对抽象数据类型新的强调使程序使用范围更广，并且更适用于现代面向对象的编程环境。读过以前版本的读者将会在这一版书中发现许多新信息；所有的读者都将发现新版书中提供了许多有利于理解基本概念的教学资料。
　　 这套书不仅适用于编程人员和计算机科学专业的学生，也适用于想让计算机运行得快一些或想解决一些较大问题的计算机使用者。我们所考虑的算法代表着近50年发展起来的一种知识体系，这种知识体系对各种应用来说是有效使用计算机的基础。从物理中的N体模拟问题到分子生物学中的基因序列问题，这里所描述的基本方法已成为科学研究要素：从数据库系统到因特网搜索引擎，它们已成为现代软件系统的基本部分。随着计算机应用的范围越来越广，基本算法的影响也随之增大。本书的目的是作为一种资源来使用，无论学生和专业人员从事什么样的计算机应用，当有需要时，他们都可以了解并明智地使用这些基本算法。本书范围
　　 本书(第1卷)包含16章，分为4大部分：基本概念、数据结构、排序和查找。本书对算法的描述是为了让读者理解范围尽可能广的基础算法的基本特性。这些算法已广泛使用多年，对编程人员和计算机科学专业的学生来说，它代表的是一种基本的知识体系。第2卷的内容是关于图算法的，第3卷由3个附加部分构成，包括字符串、几何学和一些高级主题。编写这套书的目的是把来自这些领域的基本方法汇集在一起，以提供用计算机解决问题的已知的最佳方法。
　　 如果你已经上过计算机科学的一两门课程或已有相当的编程经验，就会对本书非常感兴趣：一门课是用高级语言编程，如Java，C和C++；可能还有一门课是讲授编程系统的基本概念。因此，本书的读者对象是熟悉现代编程语言和现代计算机系统基本特性的任何人。书中会给出一些补充背景知识的参考书。
　　 支持分析结果的大多数数学材料是自包含的(或标注为超过本书范围)。尽管精通数学知识肯定是有用的，但阅读这套书并不需要具备专门的数学知识。
　　教学使用
　　 如何教授本书有很大的灵活性，这取决于教师的喜好和学生的准备情况。书中有足够的基础材料可用来给初学者教授数据结构，也有足够多的高级材料用来给高层次的学生作教学资料。有的教师会侧重于算法的实现和实际问题；而有的教师则可能希望侧重于分析和理论概念。
　　 数据结构和算法的基本课程会强调第2部分的基本数据结构，以及在第3部分和第4部分的实现中的使用。算法设计和分析的课程会强调第1部分和第5章的基础内容，然后研究第3部分和第4部分中的算法获得好的渐近性能的方法。软件工程课程会略掉数学内容和高级算法内容，而强调如何把本书中算法的实现集合成大的程序或系统。算法课程会采取纵览的方法，并介绍所有这些领域的概念。
　　 这本书的早期版本是基于其他编程语言的，已被很多学院或大学作为计算机科学专业的第二门或第三门课的教材，并用作其他课程的补充读物。在普林斯顿大学，我们的经验是：由于本书的覆盖范围广泛，因此可作为计算机科学专业学生的专业入门书，在后期课程中再进行拓展，这些后期课程有算法分析、系统编程和理论计算机科学；同时也为其他学科越来越多的学生提供了大量的技术，他们能很快地利用好这些技术。
　　 第3版中几乎所有的习题都是新增加的，它们分为几种类型。一些习题用来检验对书中内容的理解，只要求读者根据例子来做习题或应用书中描述的概念；一些习题是有关算法的实现和整理的，或通过使用经验研究方法来比较算法的变体以了解其特性；还有一些习题虽然不太适合本书，但可作为重要信息储存起来。阅读并思考这些习题对每位读者都是有益的。
　　实用算法
　　 如果想更有效地使用计算机，可以把本书作为参考书或自学用书。有编程经验的人可在书中找到所需要的相关主题的信息。虽然在某些情况下，一个章节中的算法会使用前一章中的算法，但在很大程度上可以单独阅读书中的章节。
　　 本书研究的算法是有可能用在实践中的算法。书中提供了商业工具的有关信息，以便于读者放心地实现、调试、运行算法，从而解决问题或为应用程序提供相应的功能。书中包括所讨论的方法的全部实现，并且还给出了一套统一的例子以及对例子中程序的操作描述，因为我们是使用真正的代码而非伪代码编写算法，所以可以直接使用这些程序。本书的主页上提供了程序列表。可以用很多方法使用这些能运行的程序来帮助学习算法。可以阅读程序代码，检查--下自己对算法细节了解多少，或看看它是如何解决初始化问题、边界条件和其他一些棘手的情况的。运行程序，看看算法运行时的实验性能，并把结果与书中相应的表格做比较，或尝试自己所做的修改。
　　 书中详细讨论了算法的特性和适用的情况所具有的特点，以及它与算法分析和理论计算机科学的联系。在合适的时候，会给出实验和分析结果宋证明为什么某些算法比别的算法更好；在比较有趣时，会描述所讨论的实际算法与纯理论结果之间的联系。全书综合讨论了算法性能和实现的具体信息。
　　编程语言
　　 本书实现所有算法的编程语言都是Java语言。程序中使用了大量标准的Java语句，书中还对每个表达语句进行了精确的描述。
　　 我和Mike Schidlowsky开发了用Java编程的风格，它基于抽象数据类型，因为我们都认为这是把算法和数据结构表示为实际程序的一种有效方法。我们尽量让程序更加优美、紧凑、有效、便于移植。在全书中尽可能保持风格的一致，这样一来，类似的程序看起来也是相似的。
　　 对于本书的一些算法，相似性与语言无关：举一个最突出的例子，无论是用Ada，Algol-60，Basic，C，C++，Fortran，Java，Mesa，Modula-3，Pascal，PostScript，Smalltalk还是用其他编程语言来描述快速排序算法，或在已证明它是一种有效的排序方法的环境中运行，快速排序就是快速排序。一方面，我们的代码吸取了用这些和许多其他语言实现算法的经验(本书的C和C++版也有)：另一方面，这些语言的一些特性也吸取了本书所考虑的算法和数据结构的设计者的经验。