数据结构教程（第5版）课后题参考答案，第十一章外排序

### 数据结构教程（第5版）课后题参考答案，第十一章外排序 #### 外排序概述 在计算机科学领域，**外排序**是一种处理数据量远远超过内存容量的数据排序算法。它通常应用于数据库管理和大数据处理场景。外排序算法需要在磁盘和其他外部存储设备与内存之间进行频繁的数据交换，因此设计时需要考虑磁盘I/O操作的成本。 #### 外排序的两个相对独立阶段 - **产生初始归并段**：这一阶段的任务是将大量数据分割成多个小段，这些小段可以在内存中进行排序，并存储回磁盘。通过这种方式，可以有效地利用有限的内存资源处理大规模数据。 - **多路归并排序**：一旦产生了足够数量的初始归并段，接下来的步骤就是将这些段按照一定的策略合并成更大的有序段，最终达到整个数据集有序的目的。 #### 示例分析 考虑一组关键字集合`T=(12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18)`，假设内存工作区可容纳4个记录，采用置换-选择排序算法生成初始归并段。 - **置换-选择排序算法**：这是一种适合于生成初始归并段的算法。其基本思想是在内存中选择最小值，输出到归并段中，然后继续读入新的记录，重复这一过程直至完成一个完整的归并段。 根据题目给出的数据，具体步骤如下： 1. **初始状态**：读入前四个记录`12, 2, 16, 30`。内存工作区状态为`12, 2, 16, 30`，最小值`2`输出到归并段1，此时归并段1的状态为`{2}`。 2. **后续步骤**：每读入一个新记录，都需要重新排序内存中的记录并选出新的最小值，将其输出到相应的归并段。 3. **生成过程**：按照以上规则，最终生成两个初始归并段：归并段1为`{2, 8, 12, 16, 28, 30}`；归并段2为`{4, 6, 10, 18, 20}`。 #### 归并段的生成规则 对于任意一组关键字集合`T=(k1, k2, …, kn)`，其中`k1 > k2 > … > kn`，当内存工作区大小为`m`时，采用置换-选择排序方法产生的初始归并段的数量为`⌈n/m⌉`个。 - **过程解释**：首先读入`m`个记录，采用败者树选择出最小记录，并输出到第一个归并段中。随后继续读入新记录，重复选择过程，直至完成一个完整的归并段。这样不断循环，直至所有记录都被处理完毕。 - **败者树的应用**：败者树是一种特殊的二叉树结构，主要用于从一组数据中找出最小值。在每次归并段的生成过程中，都会使用败者树来选择出当前内存工作区中的最小记录。 #### 多路平衡归并 - **定义**：多路平衡归并是一种高效的归并策略，它的目标是最小化归并的趟数。归并树中每个节点都是平衡的，即每个节点的所有子树高度相差不超过1。 - **目的**：通过优化归并的方式，减少所需的总归并趟数，从而提高排序效率。 - **实现**：每趟归并会将一定数量的初始归并段合并为更少的归并段，直至整个数据集完全有序。例如，假设初始归并段个数为`m`，归并路数为`k`，则第一趟归并将`m`个初始归并段归并为`⌈m/k⌉`个归并段。 #### 败者树及其应用 - **定义**：败者树是一种特殊的二叉树结构，主要用于在一组数据中快速选择出最小值。 - **作用**：在多路归并过程中，败者树被用来从各个归并段中选出当前最小值，以便进行下一步的归并操作。 - **结点数量**：用于`k`路归并的败者树共有`2k-1`个结点，包括`k`个叶子结点和`k-1`个非叶结点。 #### 多路平衡归并的实际应用 假设一个文件经过内排序后得到80个初始归并段。 1. **最少趟数**：为了在3趟内完成排序，至少需要5路归并。这是因为根据归并趟数计算公式`s=⌈log_k m⌉=3`，得到`k³≥80`，解得`k≥5`。 2. **限定文件数量**：如果操作系统要求一次只能处理15个文件（包括输入和输出文件），那么最多可以支持14路归并。在这种情况下，只需要2趟即可完成排序。具体地，由`s=⌈log_{14} 80⌉=2`得出结论。如果限定排序趟数为2趟，则可取的最低路数为9，因为`9²≥80`。 通过对给定数据和问题的详细分析，我们可以清楚地了解到外排序的基本概念、关键技术和应用场景。通过实际示例的学习，有助于深入理解外排序的核心原理和技术要点。