第一章 算法设计和分析的原则 1
1.1 引言 1
1.2 分析算法的若干准则 2
算法一览表 5
1.3 搜索有序表——MEMBER（x,L） 8
1.4 在一个表中找最大元和次大元 12
1.5 在一个表中找最大元和最小元 13
1.6 分治法，递推方程和递推不等式 15
习题 18
注解和参考文献 21
第二章 整序 22
2.1 整序问题 22
2.2 一些比较整序算法 23
2.2.1 选择整序（selection sort） 23
2.2.2 插入整序（jnsertion sort） 24
2.2.3 冒泡整序（bubble sort） 24
2.2.4 歇尔整序（Shell sort） 25
2.2.5 快速整序（quick sort） 26
2.2.6 堆整序（heap sort） 29
2.3 比较整序的下界 32
2.4 归并整序（merge sorting） 34
2.5.1 带有足够大缓冲工作区（buffer）的线性时间算法 37
2.5 一个稳定的最优时空界限的整序算法——Z算法 37
2.5.2 非线性的原地归并算法 39
2.5.3 稳定的线性最优空间归并算法——Z算法 41
2.6 基数整序 44
2.6.1 桶整序 44
2.6.2 基数整序 45
2.6.3＊ 不等长字符串的字典整序 46
2.7 外部整序 49
2.7.1 归并整序 49
2.7.2 多路归并和替换选择 53
2.7.3 初始归并段的生成 55
2.7.4 多步归并整序 57
2.7.5 广义斐波拉奇数列 58
习题 59
注解和参考文献 60
3.1 二叉树搜索 61
第三章 搜索 61
3.2 2-3-4树 67
3.3 红-黑树 69
习题 72
注解和参考文献 73
第四章 集合运算 74
4.1 引言 74
4.2 散列 76
4.3 二叉树上实现集合操作 79
4.4 Union-Find程序 83
4.5 平衡树模式 90
4.6 字典与优先队列 91
4.7 可并堆 93
4.8 可毗连队列 94
习题 96
注解和参考文献 98
第五章 图的算法 99
5.1 基本概念 99
5.2 计算机中图的表示 100
5.3 图的遍历 101
5.4 强连通分支 106
5.5 双连通分支 108
5.6 两个中国人算法——回路判定 113
5.7 最小生成树 115
5.8 单源最短路径 119
5.9 所有点对之间的最短路径 121
510 传递闭包 122
习题 125
注解和参考文献 126
6.1 概述 127
第六章 串匹配 127
6.2 KMP算法 128
6.3 BM算法 132
6.4 RK算法 135
习题 137
注解和参考文献 138
第七章 几何问题算法 139
7.1 一些初等几何问题的算法 139
7.1.1 直线相交 139
7.1.2 倾角计算 140
7.1.3 是否包含在多边形内部 141
7.2 求凸包 142
7.2.1 卷包裹法 143
7.2.2 Graham扫描法 144
7.2.3 Floyed方法 146
7.3.1 水平与垂直线的相交问题 147
7.3 几何体相交问题 147
7.3.2 一般的直线相交问题 148
7.4 最近邻点问题 149
7.5 Voronoi图 152
习题 153
注解和参考文献 154
第八章 算法设计技术 155
8.1 分治法（Divide and Conquer） 155
8.2 贪心法（Greedy） 159
8.3 动态规划（Dynamic Programming） 162
8.4 回溯法（Backtracking） 169
8.5 分枝限界法（Branch and Bound） 174
习题 179
注解和参考文献 181
第九章 N？完全问题与近似算法 183
9.1 图灵机（Turing Machine） 183
9.2 不确定图灵机（Nondeterministic Turing Machine） 187
9.3 ？与N？类 191
9.4 COOK定理和N？完全问题 196
9.5 N？完全问题的近似算法 202
习题 209
注解和参考文献 210
第十章 概率算法和算法的概率分析 211
10.1 引言 211
10.2 概率算法的定义 212
10.3 求平面点集上最近点对的概率算法 212
10.4 判定素数的概率算法 217
10.4.1 概述 217
10.4.2 求二个整数的最大公约数的欧几里德辗转相除法 218
10.4.3 Fermat素数测试法 220
10.4.4 Miller和Rabin素数测试概率算法 221
10.5 ？ 222
10.6 Karp的有关算法概率分析的概念 222
习题 224
注解和参考文献 224
第十一章 VLSI中的并行算法 225
11.1 脉动方式的并行处理 225
11.2 分治方式的并行处理 233
11.3 计算模型和下界理论 241
习题 249
注解和参考文献 249
中文参考文献 250
Bibliograph 251