DS-07-08 外部排序

408 > ### 数据结构 > #### 外部排序（多路归并/置换-选择排序）

一、定位信息

维度	内容
章节归属	第7章排序
知识单元编号	DS-07-08
前置知识	DS-07-06 归并排序、文件与存储基础
后续衔接	DS-07-09 排序算法综合对比
考试大纲要求	理解外部排序的基本思想，掌握多路归并和置换-选择排序
预计学习时长	45分钟

二、知识点讲解

1. 外部排序的基本概念

外部排序是指待排序数据量太大，无法一次性装入内存，需要在排序过程中进行内、外存数据交换的排序方法。

核心思想：将外存上的数据分段读入内存，在内存中排序后写回外存，形成若干个有序段（初始归并段），然后通过多路归并将有序段逐步合并为一个完整的有序文件。

两个阶段：

生成初始归并段：将外存数据分段读入内存，排序后写回
多路归并：将多个归并段逐步合并

2. 外部排序的时间代价

外部排序的主要时间代价来自磁盘读写（I/O）。设：

文件总记录数：N
内存工作区大小：M（可容纳 M 个记录）
初始归并段数：⌈N/M⌉ = n

总 I/O 次数 = 2 × 文件大小 × 归并趟数

因子 2：每趟读一次 + 写一次
归并趟数 = ⌈log_k(n)⌉（k 路归并）

优化目标：减少归并趟数 → 增大 k（路数）或减少 n（初始归并段数）

3. 多路归并（k-way merge）

3.1 基本思想

将 k 个有序归并段合并为一个有序段。每趟从 k 个归并段的当前元素中选最小者输出。

3.2 朴素方法 vs 败者树

方法	每次选最小的比较次数	每趟总比较次数
朴素方法	k-1 次	(k-1) × (N-1) ≈ O(kN)
败者树	⌈log₂k⌉ 次	⌈log₂k⌉ × (N-1) ≈ O(N log k)

败者树（Loser Tree） 是一棵完全二叉树，用于高效地从 k 个元素中选出最小值。

3.3 败者树原理

败者树的叶节点存放各归并段的当前元素，内部节点记录败者（较大值）的编号，最终的胜者（最小值）在根节点之外的一个额外位置。

// 败者树的调整过程（简化伪代码）
void Adjust(LoserTree ls[], int k, int s) {
    // s 是新元素的编号（叶节点位置）
    // k 是败者树的路数
    int t = (s + k) / 2;  // t 是 s 的父节点
    while (t > 0) {
        if (Loser[ls[t]] < Loser[s]) {
            // s 败了，交换
            int temp = s;
            s = ls[t];
            ls[t] = temp;
        }
        t = t / 2;  // 向上
    }
    ls[0] = s;  // 最终胜者
}

3.4 败者树的时间复杂度

建立败者树：O(k)
每次调整（选出下一个最小值）：O(log₂k)
总时间：O(k + N × log₂k)

当 k 增大时：

归并趟数 ⌈log_k(n)⌉ 减少 → I/O 次数减少
但每次调整代价 ⌈log₂k⌉ 增大
存在最优的 k 值，需要权衡

4. 置换-选择排序（Replacement-Selection Sort）

4.1 动机

若初始归并段数 n 减少，则归并趟数减少。置换-选择排序可以在相同内存大小下生成更长的初始归并段，从而减少归并段数。

朴素方法：每个初始归并段长度 = M（内存大小）置换-选择排序：平均每个初始归并段长度 = 2M

4.2 基本思想

从输入文件读入 M 个记录到内存工作区
用最小堆（或类似结构）从工作区中选出关键字最小的记录输出到当前归并段
再从输入文件读入下一个记录，如果其关键字 ≥ 刚输出的记录，则加入当前归并段；否则标记为下一段的开始
重复直到工作区为空，当前归并段结束
开始新的归并段，重复上述过程

4.3 伪代码

void ReplacementSelection(ElementType input[], int N, int M) {
    // input: 输入文件，N 个记录
    // M: 内存工作区大小
    MinHeap heap;  // 最小堆，大小为 M
    int lastOutput = -∞;  // 上一次输出的关键字
    int segmentId = 0;    // 当前归并段编号

    // 初始化：读入 M 个记录建小根堆
    for (int i = 0; i < M && i < N; i++) {
        InsertHeap(heap, input[i]);
    }
    int nextIdx = M;  // 下一个要读入的记录下标

    while (!IsEmpty(heap)) {
        ElementType min = DeleteMin(heap);  // 取堆顶最小值
        if (min.key < lastOutput) {
            // 当前值比上一个输出小，属于下一个归并段
            segmentId++;
        }
        Output(min, segmentId);  // 输出到当前归并段
        lastOutput = min.key;

        if (nextIdx < N) {
            ElementType newRecord = input[nextIdx++];
            if (newRecord.key >= lastOutput) {
                // 可以加入当前归并段
                InsertHeap(heap, newRecord);
            } else {
                // 属于下一个归并段，暂不插入，等当前段结束
                // 实际实现中需要额外空间暂存
                InsertHeap(heap, newRecord);  // 仍插入堆但标记
            }
        }
    }
}

4.4 效果分析

朴素方法：n = ⌈N/M⌉ 个归并段，每段长度 M
置换-选择排序：n 更少，每段平均长度 ≈ 2M
归并趟数从 ⌈log_k(⌈N/M⌉)⌉ 降到 ⌈log_k(⌈N/(2M)⌉)⌉

5. 最佳归并树

当各初始归并段长度不等时，归并的顺序会影响总的 I/O 次数。最佳归并树利用 Huffman 树的思想，使带权路径长度最小（即 I/O 次数最少）。

原则：短的归并段晚归并，长的归并段早归并。类似 Huffman 编码中频率低的编码长。

对于 k 路归并：

若 (n-1) mod (k-1) ≠ 0，则补充长度为 0 的虚段
每次取 k 个最短的归并段合并
重复直到只剩一个归并段

6. 外部排序关键技术对比表

技术	作用	效果
多路归并	减少归并趟数	趟数从 ⌈log₂n⌉ 降到 ⌈log_k(n)⌉
败者树	减少每次选最小的比较次数	从 O(k) 降到 O(log₂k)
置换-选择排序	减少初始归并段数	每段平均长度从 M 增到 2M
最佳归并树	优化归并顺序	减少总 I/O 次数

三、记忆辅助

外部排序 = 生成初始归并段 + 多路归并：两步走，先分段排序，再多路合并
瓶颈是 I/O：外部排序的时间主要花在磁盘读写上，不是 CPU 计算
败者树 = 高效选最小：从 k 个中选最小只需 log₂k 次比较，不是 k-1 次
置换-选择排序的意义：同样 M 大小的内存，生成的归并段更长（平均 2M），段数更少
最佳归并树 = Huffman 树：短段晚合并，长段早合并，最小化总 I/O

四、例题精解

例题 1：多路归并的归并趟数计算

题目：有 10000 个记录，内存可容纳 500 个记录。使用 4 路归并，需要几趟归并？如果改用 8 路归并呢？

第一步：审题 N=10000, M=500，分别计算 4 路和 8 路归并的趟数。

第二步：分析

初始归并段数 n = ⌈N/M⌉ = ⌈10000/500⌉ = 20

4 路归并：

趟数 = ⌈log₄(20)⌉ = ⌈log(20)/log(4)⌉ = ⌈2.16⌉ = 3 趟

8 路归并：

趟数 = ⌈log₈(20)⌉ = ⌈log(20)/log(8)⌉ = ⌈1.44⌉ = 2 趟

第三步：解答

4 路归并需要 3 趟
8 路归并需要 2 趟

第四步：总结 增加归并路数 k 可以减少归并趟数，但每趟的比较代价增加。使用败者树可以使每趟的比较代价从 O(k) 降到 O(log₂k)，从而支持更大的 k。

例题 2：置换-选择排序的效果

题目：有 24 个记录，内存工作区大小 M=6。使用朴素方法和置换-选择排序分别生成初始归并段，对比段数。

第一步：审题 N=24, M=6，比较两种方法的初始归并段数。

第二步：分析

朴素方法：

每段长度固定为 M = 6
段数 = ⌈24/6⌉ = 4 段

置换-选择排序：

每段平均长度 ≈ 2M = 12
段数 ≈ ⌈24/12⌉ = 2 段

（实际段数取决于数据分布，但平均约为朴素方法的一半）

第三步：解答

朴素方法：4 个归并段
置换-选择排序：约 2 个归并段

归并趟数（2 路归并）：

朴素方法：⌈log₂4⌉ = 2 趟
置换-选择排序：⌈log₂2⌉ = 1 趟

第四步：总结 置换-选择排序通过利用"记录可以属于不同归并段"的灵活性，在相同内存下生成更长的归并段，从而减少归并段数和归并趟数。

例题 3：败者树的建树与调整

题目：有 4 个归并段，当前元素分别为 (10, 25, 35, 15)。用败者树选出最小值，并写出调整过程。

第一步：审题 4 路归并，叶节点为各段当前元素，用败者树选最小。

第二步：分析

初始叶节点（归并段编号 0~3）：

段 0: 10
段 1: 25
段 2: 35
段 3: 15

建败者树（内部节点记录败者编号）：

        [1]          败者：段1(25)
       /    \
    [3]      [2]     败者：段3(15), 段2(35)
    /  \    /  \
   10  25  35  15    段0 段1 段2 段3

第 1 层：段0(10) vs 段1(25)，段1 败 → 内部节点[3] = 1，胜者段0 第 2 层：段2(35) vs 段3(15)，段2 败 → 内部节点[2] = 2，胜者段3 第 3 层：段0(10) vs 段3(15)，段3 败 → 内部节点[1] = 3，胜者段0

最终胜者：段 0（值 10），输出 10

调整：段 0 读入下一个元素（假设为 20）

段0(20) vs 段1(25) → 段1 败 → [3] = 1
段0(20) vs 段3(15) → 段0 败 → [1] = 0
胜者：段 3（值 15）

第三步：解答 第一次选出最小值 10（段 0），调整后选出次小值 15（段 3）。每次调整只需 ⌈log₂4⌉ = 2 次比较。

第四步：总结 败者树的每次调整只需沿树的高度向上比较，时间复杂度 O(log₂k)。这使得多路归并即使路数 k 很大，效率也很高。

五、考情分析

年份	题型	考点	难度
中频	计算题	归并趟数的计算	★★★
中频	选择题	败者树的原理	★★☆
低频	分析题	置换-选择排序的过程	★★★
低频	计算题	最佳归并树的构造	★★★

命题趋势：

外部排序的考查频率低于内部排序，但属于大纲要求内容
归并趟数计算是最常见的题型
败者树的原理和调整过程偶尔考查
置换-选择排序和最佳归并树考查频率较低

六、易错点

归并段数的计算：n = ⌈N/M⌉，不是 N/M（要向上取整）
归并趟数的底数：k 路归并的趟数是 ⌈log_k(n)⌉，不是 ⌈log₂(n)⌉
败者树 vs 胜者树：败者树的内部节点记录的是败者（较大值），不是胜者
置换-选择排序的平均段长：不是 2M（这是理想情况），实际取决于数据分布
I/O 次数的计算：每趟读一次写一次，所以是 2 × 文件大小 × 趟数
最佳归并树的虚段：k 路归并时，若 (n-1) mod (k-1) ≠ 0，需要补充虚段

七、来源标注

《数据结构（C语言版）》严蔚敏，第11章外部排序
《数据结构》王道考研，第7章 7.7节外部排序
408考试大纲：数据结构部分-外部排序
《算法导论》Thomas H. Cormen，第23章最小生成树（败者树相关）

DS-07-08 外部排序 ​

408 > ### 数据结构 > #### 外部排序（多路归并/置换-选择排序） ​

一、定位信息 ​

二、知识点讲解 ​

1. 外部排序的基本概念 ​

2. 外部排序的时间代价 ​

3. 多路归并（k-way merge） ​

3.1 基本思想 ​

3.2 朴素方法 vs 败者树 ​

3.3 败者树原理 ​

3.4 败者树的时间复杂度 ​

4. 置换-选择排序（Replacement-Selection Sort） ​

4.1 动机 ​

4.2 基本思想 ​

4.3 伪代码 ​

4.4 效果分析 ​

5. 最佳归并树 ​

6. 外部排序关键技术对比表 ​

三、记忆辅助 ​

四、例题精解 ​

例题 1：多路归并的归并趟数计算 ​

例题 2：置换-选择排序的效果 ​

例题 3：败者树的建树与调整 ​

五、考情分析 ​

六、易错点 ​

七、来源标注 ​

DS-07-08 外部排序

408 > ### 数据结构 > #### 外部排序（多路归并/置换-选择排序）

一、定位信息

二、知识点讲解

1. 外部排序的基本概念

2. 外部排序的时间代价

3. 多路归并（k-way merge）

3.1 基本思想

3.2 朴素方法 vs 败者树

3.3 败者树原理

3.4 败者树的时间复杂度

4. 置换-选择排序（Replacement-Selection Sort）

4.1 动机

4.2 基本思想

4.3 伪代码

4.4 效果分析

5. 最佳归并树

6. 外部排序关键技术对比表

三、记忆辅助

四、例题精解

例题 1：多路归并的归并趟数计算

例题 2：置换-选择排序的效果

例题 3：败者树的建树与调整

五、考情分析

六、易错点

七、来源标注