算法

算法

Sedgewick之巨著，与高德纳TAOCP一脉相承

几十年多次修订，经久不衰的畅销书

涵盖所有程序员必须掌握的50种算法

算法领域的经典参考书 众多图例实现图解算法和算法导论 基于Java语言实现算法和数据结构 熟练掌握算法设计与分析

内容简介

《算法（第 4 版）》全面讲述算法和数据结构的必备知识，具有以下几大特色。

• 1、 算法领域的经典参考书：Sedgewick 畅销著作的新版，反映了经过几十年演化而成的算法核心知识体系
• 2、内容全面：全面论述排序、搜索、图处理和字符串处理的算法和数据结构，涵盖每位程序员应知应会的 50 种算法
• 3、全新修订的代码：全新的 Java 实现代码，采用模块化的编程风格，所有代码均可供读者使用
• 4、与实际应用相结合：在重要的科学、工程和商业应用环境下探讨算法，给出了算法的实际代码，而非同类著作常用的伪代码
• 5、富于智力趣味性：简明扼要的内容，用丰富的视觉元素展示的示例，精心设计的代码，详尽的历史和科学背景知识，各种难度的练习，这一切都将使读者手不释卷
• 6、科学的方法：用合适的数学模型讨论算法性能，这些模型是在真实环境中得到验证的
• 7、与网络相结合：配套网站 algs4.cs.princeton.edu 提供了本书内容的摘要及相关的代码、测试数据、编程练习、教学课件等资源

作者简介

Robert Sedgewick，斯坦福大学博士，导师为 Donald E. Knuth，从 1985 年开始一直担任普林斯顿大学计算机科学系教授，曾任该系主任，也是 Adobe Systems 公司董事会成员，曾在 Xerox PARC、国防分析研究所（Institute for Defense Analyses）和法国国家信息与自动化研究所（INRIA）从事研究工作。他的研究方向包括解析组合学、数据结构和算法的分析与设计、程序可视化等。

Kevin Wayne，康奈尔大学博士，普林斯顿大学计算机科学系高级讲师，研究方向包括算法的设计、分析和实现，特别是图和离散优化。

目录

第 1 章　 基础

• 1.1　基础编程模型
• 1.1.1　Java 程序的基本结构
• 1.1.2　原始数据类型与表达式
• 1.1.3　 语句
• 1.1.4　 简便记法
• 1.1.5　 数组
• 1.1.6　 静态方法
• 1.1.7　 API
• 1.1.8　 字符串
• 1.1.9　 输入输出
• 1.1.10　 二分查找
• 1.1.11　 展望
• 1.2　 数据抽象
• 1.2.1　 使用抽象数据类型
• 1.2.2　 抽象数据类型举例
• 1.2.3　 抽象数据类型的实现
• 1.2.4　 更多抽象数据类型的实现
• 1.2.5　 数据类型的设计
• 1.3　 背包、队列和栈
• 1.3.1　 API
• 1.3.2　 集合类数据类型的实现
• 1.3.3　 链表
• 1.3.4　 综述
• 1.4　 算法分析
• 1.4.1　 科学方法
• 1.4.2　 观察
• 1.4.3　 数学模型
• 1.4.4　 增长数量级的分类
• 1.4.5　 设计更快的算法
• 1.4.6　 倍率实验
• 1.4.7　 注意事项
• 1.4.8　 处理对于输入的依赖
• 1.4.9　 内存
• 1.4.10　 展望
• 1.5　 案例研究：union-find 算法
• 1.5.1　 动态连通性
• 1.5.2　 实现
• 1.5.3　 展望

第 2 章　 排序

• 2.1　 初级排序算法
• 2.1.1　 游戏规则
• 2.1.2　 选择排序
• 2.1.3　 插入排序
• 2.1.4　 排序算法的可视化
• 2.1.5　 比较两种排序算法
• 2.1.6　 希尔排序
• 2.2　 归并排序
• 2.2.1　 原地归并的抽象方法
• 2.2.2　 自顶向下的归并排序
• 2.2.3　 自底向上的归并排序
• 2.2.4　 排序算法的复杂度
• 2.3　 快速排序
• 2.3.1　 基本算法
• 2.3.2　 性能特点
• 2.3.3　 算法改进
• 2.4　 优先队列
• 2.4.1　 API
• 2.4.2　 初级实现
• 2.4.3　 堆的定义
• 2.4.4　 堆的算法
• 2.4.5　 堆排序
• 2.5　 应用
• 2.5.1　 将各种数据排序
• 2.5.2　 我应该使用哪种排序算法
• 2.5.3　 问题的归约
• 2.5.4　 排序应用一览

第 3 章　查找

• 3.1　符号表
• 3.1.1　API
• 3.1.2　有序符号表
• 3.1.3　用例举例
• 3.1.4　无序链表中的顺序查找
• 3.1.5　有序数组中的二分查找
• 3.1.6　对二分查找的分析
• 3.1.7　预览
• 3.2　二叉查找树
• 3.2.1　基本实现
• 3.2.2　分析
• 3.2.3　有序性相关的方法与删除操作
• 3.3　平衡查找树
• 3.3.1　2-3 查找树
• 3.3.2　红黑二叉查找树
• 3.3.3　实现
• 3.3.4　删除操作
• 3.3.5　红黑树的性质
• 3.4　散列表
• 3.4.1　散列函数
• 3.4.2　基于拉链法的散列表
• 3.4.3　基于线性探测法的散列表
• 3.4.4　调整数组大小
• 3.4.5　内存使用
• 3.5　应用
• 3.5.1　我应该使用符号表的哪种实现
• 3.5.2　集合的 API
• 3.5.3　字典类用例
• 3.5.4　索引类用例
• 3.5.5　稀疏向量

第 4 章　 图

• 4.1　 无向图
• 4.1.1　 术语表
• 4.1.2　 表示无向图的数据类型
• 4.1.3　 深度优先搜索
• 4.1.4　 寻找路径
• 4.1.5　 广度优先搜索
• 4.1.6　 连通分量
• 4.1.7　 符号图
• 4.1.8　 总结
• 4.2　 有向图
• 4.2.1　 术语
• 4.2.2　 有向图的数据类型
• 4.2.3　 有向图中的可达性
• 4.2.4　 环和有向无环图
• 4.2.5　 有向图中的强连通性
• 4.2.6　 总结
• 4.3　 最小生成树
• 4.3.1　 原理
• 4.3.2　 加权无向图的数据类型
• 4.3.3　 最小生成树的 API 和测试用例
• 4.3.4　 Prim 算法
• 4.3.5　 Prim 算法的即时实现
• 4.3.6　 Kruskal 算法
• 4.3.7　 展望
• 4.4　 最短路径
• 4.4.1　 最短路径的性质
• 4.4.2　 加权有向图的数据结构
• 4.4.3　 最短路径算法的理论基础
• 4.4.4　 Dijkstra 算法
• 4.4.5　 无环加权有向图中的最短路径算法
• 4.4.6　 一般加权有向图中的最短路径问题
• 4.4.7　 展望

第 5 章　 字符串

• 5.1　 字符串排序
• 5.1.1　 键索引计数法
• 5.1.2　 低位优先的字符串排序
• 5.1.3　 高位优先的字符串排序
• 5.1.4　 三向字符串快速排序
• 5.1.5　 字符串排序算法的选择
• 5.2　 单词查找树
• 5.2.1　 单词查找树
• 5.2.2　 单词查找树的性质
• 5.2.3　 三向单词查找树
• 5.2.4　 三向单词查找树的性质
• 5.2.5　 应该使用字符串符号表的哪种实现
• 5.3　 子字符串查找
• 5.3.1　 历史简介
• 5.3.2　 暴力子字符串查找算法
• 5.3.3　 Knuth-Morris-Pratt 子字符串查找算法
• 5.3.4　 Boyer-Moore 字符串查找算法
• 5.3.5　 Rabin-Karp 指纹字符串查找算法
• 5.3.6　 总结
• 5.4　 正则表达式
• 5.4.1　 使用正则表达式描述模式
• 5.4.2　 缩略写法
• 5.4.3　 正则表达式的实际应用
• 5.4.4　 非确定有限状态自动机
• 5.4.5　 模拟 NFA 的运行
• 5.4.6　 构造与正则表达式对应的
• 5.5　 数据压缩
• 5.5.1　 游戏规则
• 5.5.2　 读写二进制数据
• 5.5.3　 局限
• 5.5.4　 热身运动：基因组
• 5.5.5　 游程编码
• 5.5.6　 霍夫曼压缩

第 6 章　 背景

索引