第1部分 内分类方法 1
第1章 分类的基本概念与基本分类方法 1
1.1 引言 1
目录 1
1.2 分类过程 4
1.3 内分类的特性 5
1.4 基本算法 7
1.5 线性选择法 7
1.6 交换线性选择法：交换的用法 11
1.7 计数线性选择法 14
1.8 实现分类的各种考虑 18
第2章 交换分类法与线性插入分类法 24
2.1 交换分类法 24
2.2 线性插入分类法 33
2.3 基本比较分类法小结 38
3.1 引言 39
3.2 方法 39
第3章 Shell分类法 39
3.3 例子 40
3.4 距离的计算 43
3.5 延迟交换的Shell分类法 45
第4章 分类中的结构 47
4.1 结构的概念 47
4.2 二元树 47
4.3 二元树的值 50
4.4 树的第一个用途 51
4.5 比较次数与树形 55
4.6 划分子表 58
4.7 其它树 60
第5章 锦标赛分类法 61
5.1 概述 61
5.2 使用工作区的锦标赛分类法 63
5.3 最小存贮锦标赛分类法 76
5.4 锦标赛分类法的进一步讨论 85
6.2 中心插入分类法：“树” 92
6.1 概述 92
第6章 使用树结构的插入分类法 92
6.3 二元插入分类法：插入树 96
6.4 讨论：比较次数和传送次数 102
第7章 快速分类法 103
7.1 概述 103
7.2 方法 103
7.3 一个阶段的细述 105
7.4 阶段之间的操作 107
7.5 支点的选择 110
7.6 阶段结束的判别 111
7.7 快速分类法与其它分类法的联合使用 113
7.8 讨论 114
第8章 高次选择分类法 115
8.1 引言 115
8.2 二次选择分类法 115
8.3 高次选择分类法 124
9.2 多遍扫描的两路直接合并 125
9.1 引言：基本合并过程 125
第9章 内合并 125
9.3 两路自然合并 133
9.4 合并的进一步探讨 139
第10章 分布分类法 149
10.1 分布分类法 149
10.2 二进制交换分类法：方法 150
10.3 位分类法：基本方法 155
10.4 域分类 166
10.5 地址计算分类法 171
第11章 各种内分类方法的比较 176
11.1 引言 176
11.2 简单的研究 177
第2部分 外分类方法 184
第12章 外分类的分类阶段 184
12.1 外分类方法 184
12.2 分类／合并的性质 184
12.4 存贮管理：串的数目和大小 186
12.3 分类阶段诸要素 186
12.5 分类和输出的关系 193
12.6 分类和输入的关系 194
12.7 散布 196
12.8 分类的特性 198
12.9 最后评语 201
第13章 磁带合并 202
13.1 均衡磁带合并 202
13.2 反读均衡合并 205
13.3 不完全的均衡合并 207
13.4 非均衡的均衡合并 210
13.5 合并设计应考虑的问题 210
13.6 合并的I/O方式和系统特性 214
13.7 缓冲技术对合并的影响 215
13.8 输入缓冲技术 218
13.9 合并的实践 221
13.10 短评 223
14.2 正读多阶段合并：三带 226
第14章 多阶段磁带合并法 226
14.1 概述 226
14.3 多带多阶段合并 229
14.4 正读多阶段合并的散布 231
14.5 虚串法 234
14.6 反读多阶段合并 236
14.7 多阶段合并的内部效果 238
14.8 I/O子系统和多阶段合并 239
14.9 磁带使用中的灵活性 239
第15章 逐级合并法和折衷合并法 242
15.1 概述 242
15.2 正读逐级合并：散布和合并 242
15.3 逐级合并的级 243
15.4 反读逐级合并 245
15.5 逐级合并的串散布方法 246
15.9 补充说明 253
15.8 I/O子系统 253
15.7 逐级合并的内部效果 253
15.6 串的长度 253
15.10 折衷合并法 254
第16章 振荡合并法和交叉合并法 261
16.1 引言 261
16.2 振荡合并法 261
16.3 交叉合并法 267
17.2 合并方法的度量 272
17.1 引言 272
第17章 磁带合并综述 272
17.3 影响合并性能的因素 273
17.4 硬件与合并 277
17.5 各种合并方法的比较 279
第18章 随机存取分类 280
18.1 设备性质 280
18.2 基本合并概念 284
18.3 随机存取合并的补充考虑 303
19.1 通用分类 308
第3部分 分类系统 308
第19章 通用分类系统 308
19.2 基本结构 309
19.3 参数及其用法 310
19.4 其它参数 315
19.5 分类系统的表达 318
19.6 系统的决定 322
19.7 通用分类程序的开发和硬件 325
19.8 分类与软件 328
19.9 分类的计时 338
19.10 分类模拟 341
第20章 分类系统的特殊问题 342
20.1 浮动与虚拟存贮 342
20.2 多处理机 363
20.3 其它硬件 384
参考资料 387
附录A CACM算法的分类过程 396
附录B 用PL/1编码的分类过程 465