【学习笔记】数据结构（十一）

外部排序

外部排序 指的是大文件的排序，即待排序的记录存储在外存储器 上，在排序过程中需进行多次的内、外存之间的交换。

11.1 外存信息的存取

计算机一般有 两种存储器： 内存储器（主存）和外存储器（辅存）。

• 内存的信息可随机存取，且存取速度快，但价格贵、容量小。

• 外存储器包括磁带和磁盘（或磁鼓），前者为顺序存取的设备，后者为随机存取的设备。

1、磁带信息的存取

磁带是薄薄涂上一层磁性材料的一条窄带。

磁带不是连续运转的设备，而是一种启停设备（启停时间约为 5 毫秒），它可以根据读 ／写的需要随时启动和停止。由千读／写信息应在旋转稳定时进行，而磁带从静止状态启 动后，要经过一个加速的过程才能达到稳定状态；反之，在读／写结束后，从运动状态到完 全停止，要经过一个减速的过程。因此，在磁带上相邻两组字符组（记录）之间要留一空白 区，叫做 间隙 IRG(lnter Record Gap) 。

在每次写信息时， 将若干个字符组合并成一块后一次写入磁带。 于是，每个字符组间就没有 IRG,而变成 块间的间隙 IBG(lnter Block Gap) , 从而可以减少IRG 的数目，提高磁带的利用率，块的长度大于 IBG 的长度。

成块还可减少I/O操作。 因为一次1/0操作可把整个物理块都读到内存缓冲区中． 然后再从缓冲区中取出所需要的信息（一个字符组）。每当要读一个字符组时，首先要查 缓冲区中是否已有，若有，则不必执行I/O操作，直接从缓冲区读取即可。

在磁带上 读写一块信息所需的时间 由两部分组成： T_I/O = t_a + n · t_w

• t_a 为延迟时间，读／写头到达传输信息所在物理块起始位置所需时间；
• t_w 为传输一 个字符的时间。

缺点：

由于磁带是 顺序存取 的设备，则读／写信息之前先要进行顺序查找，并且当读／写头位于磁带尾端，而要读的信息在磁带始端时，尚需使磁带倒转运动。这是顺序存取设备的主要缺点，它使检索和修改信息很不方便。

2、磁盘信息的存取

磁盘是一种 直接存取 的存储设备(DASO)。它的容量大、速度快，存 取速度比磁带快得多。

磁盘可以是单片的，也可以由若干盘片组成盘组。每一片上有两个面。以 6 片盘组为例，由于最顶上和最低下盘片的外侧面不存信息，所以总共只有10个面可用来保存信 息。盘片装在一个主轴上，并绕主轴高速旋转，当磁道在读／写头下通过时，便可以进行信息的读／写。

把磁盘分为 固定头盘和活动头盘 ：

• 固定头盘的每 一道上都有独立的磁头，它是固定不动的，专负责读／写某一 道上的信息。
• 活动头盘的磁头是可移动的。盘组也是可变的。一个 面上只有一个磁头，它可以从该面上的一道移动到另一道。 磁头装在一个动臂上，不同面上的磁头是同时移动的，并处 于同一圆柱面上。各个面上半径相同的磁道组成一个圆柱 面，圆柱面的个数就是盘片面上的磁道数。

在磁盘上标明一个具体信息必须用一个三维地址：柱面号、盘面号、块号

• 柱面号确定读／写头的径向运动，
• 块号确定信息在盘片圆圈上的位置。

在磁盘上读写一块信息步骤：

• 首先必须找柱面，移动臂使磁头移 动到所需柱面上（称为定位或寻查）；
• 然后等待要访问的信息转到磁头之下；
• 最后，读／写所需信息。

在磁盘上读写一块信息所需的时间 由 3 部分组成： T_I/O = t_seek + t_la + t_wm

• t_seek 为寻查时间(seek time) , 即读／写头定位的时间；
• t_la 为等待时间(latency time), 即等待信息块的初始位置旋转到读写头下的时间；
• t_wm 为传输时间(transmission time)

内外存之间的数据交换原理：

11.2 外部排序的方法

外部排序基本上由两个相对独立的阶段组成:

• 按可用内存大小，将外存上含 n 个记录的文件分成若干长度为 l 的子文件或段(segment),依次读入内存并利用有效的内 部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串(run);
• 对这些归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止

外部排序所需总的时间＝内部排序（产生初始归并段）所需的时间(m * t_IS) + 外存信息读写的时间(d * t_IO) + 内部归并所需的时间(s * ut_mg）

• t_IS：为得到一个初始归并段进行内部排序所需时间的均值；
• m：为经过内部排序之后得到的初始归并段的个数I
• t_IO：是进行一次外存 读／写时间的均值；取决于所用的外存设备；
• d：为总的读／写次数
• ut_mg：对u 个记录进行内部归并所需时间；
• s ：为归并的趟数；

t_IO 比 t_mg大得多，所以提高外排的效率应主要 着眼于减少外存信息读写的次数d

假设在每个物理块可以容纳 200个记录，则每一趟归并需进行 50 次“读” 和 50 次“写"’

利用 2-路归并：4 趟 * 100 + 100 内部排序 = 500 次的读／写。

利用 5-路归并：2 趟 * 100 + 100 内部排序 = 300 次的读／写。

可见，对同一文件而言，进行外排时所需读／写外存的次数和归并的趟数 s成正比。

对m个初始归并段进行k-路平衡归并时，归并的趟数 s = ⌊ log_km ⌋ —— 可见，若增加 K 或减少m 便能减少s。

若能增加初始归并段的长度则可减少初始归并段数量m

例子：

11.3 多路平衡归并的实现 - 增加k

每一趟从m个归并段得到 ⌈m/k⌉ 归并段。这种归并方法称为 k-路平衡归并

使用k路平衡归并策略，选出一个最小元素需要对比关键字(k-1)次，所以增加k会导致内部归并所需时间增加

eg：8路平衡归并，从公企归并段中选出一个最小元素需要对比关键字7次

“败者树"(Tree of Loser)：可视为一棵完全二叉树)(根节点上多了一个结点)。k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。目的- 使k元素的关键字对比次数变少

#define _CRT_SECURE_NO_WARNINGS 1  // 禁用 Visual Studio 的安全警告（例如 scanf 的安全问题）
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 定义状态码，用于表示函数执行的成功或失败
#define OK 1
#define OVERFLOW -2
#define ERROR -1

// 栈的初始大小
#define STACK_INIT_SIZE 4

// 定义归并段的数量
#define K 5

// 定义最大键值和最小键值
#define MAXKEY INT_MAX  // 表示归并段结束的特殊键值
#define MINKEY INT_MIN  // 用于初始化败者树的虚拟键值

// 定义状态类型
typedef int Status;

// 定义栈的结构体
typedef struct {
    int* base;      // 栈的基地址（栈底）
    int* top;       // 栈顶指针
    int stacksize;  // 栈的当前容量
} SqStack;

// 定义键值类型
typedef int KeyType;

// 定义败者树，大小为 K
typedef int LoserTree[K];

// 定义外部节点结构体
typedef struct {
    KeyType key;  // 外部节点的键值
} ExNode, External[K + 1];  // 外部节点数组，大小为 K + 1（用于败者树）

/**
 * 初始化栈
 * @param S 栈的指针
 * @return 成功返回 OK，失败返回 OVERFLOW
 */
Status InitStack(SqStack* S) {
    S->base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));  // 分配栈的初始内存
    if (!S->base)
        exit(OVERFLOW);  // 内存分配失败，退出程序
    S->top = S->base;  // 初始化栈顶指针为栈底
    S->stacksize = STACK_INIT_SIZE;  // 初始化栈的容量
    return OK;  // 初始化成功
}

/**
 * 向栈中压入元素
 * @param S 栈的指针
 * @param e 要压入的元素
 * @return 成功返回 OK，失败返回 OVERFLOW
 */
Status Push(SqStack* S, int e) {
    // 如果栈已满，则需要扩容
    if (S->top - S->base >= S->stacksize) {
        int* new_base = (int*)realloc(S->base, (S->stacksize + STACK_INIT_SIZE) * sizeof(int));  // 重新分配内存
        if (!new_base) {
            return OVERFLOW;  // 内存分配失败，返回错误
        }
        S->base = new_base;  // 更新栈底指针
        S->stacksize += STACK_INIT_SIZE;  // 更新栈的容量
    }
    *S->top++ = e;  // 将元素压入栈顶，并移动栈顶指针
    return OK;  // 成功返回 OK
}

/**
 * 从栈中弹出元素
 * @param S 栈的指针
 * @param e 用于存储弹出元素的变量
 * @return 成功返回 OK，失败返回 ERROR
 */
Status Pop(SqStack* S, int* e) {
    if (S->top == S->base) {
        return ERROR;  // 如果栈为空，返回错误
    }
    *e = *(--S->top);  // 弹出栈顶元素，并移动栈顶指针
    return OK;  // 成功返回 OK
}

/**
 * 调整败者树的某个节点
 * @param ls 败者树
 * @param b 外部节点数组
 * @param s 当前要调整的节点索引
 */
void Adjust(LoserTree ls, External b, int s) {
    int t, tmp;
    // 计算当前节点的父节点索引
    t = (s + K) / 2;  // 公式：(s + K) / 2，用于找到父节点索引
    // 从当前节点向上调整到根节点
    while (t > 0) {
        // 如果当前节点的值大于父节点的值
        if (b[s].key > b[ls[t]].key) {
            tmp = s;  // 交换当前节点和父节点
            s = ls[t];
            ls[t] = tmp;
        }
        t = t / 2;  // 继续向上调整
    }
    ls[0] = s;  // 更新胜者节点（ls[0] 始终存储当前胜者）
}

/**
 * 创建败者树
 * @param ls 败者树
 * @param b 外部节点数组
 */
void CreateLoserTree(LoserTree ls, External b) {
    int i;
    // 初始化外部节点的虚拟节点（用于处理特殊情况）
    b[K].key = MINKEY;  // 第 K 个外部节点的键值设置为 MINKEY
    // 初始化败者树的叶子节点（归并段的索引）
    for (i = 0; i < K; i++) {
        ls[i] = K;  // 初始化败者树的叶子节点为虚拟节点
    }
    // 从最后一个叶子节点开始调整败者树
    for (i = K - 1; i >= 0; i--) {
        Adjust(ls, b, i);  // 调整败者树
    }
}

/**
 * K 路归并
 * @param ls 败者树
 * @param b 外部节点数组
 * @param S 栈数组
 */
void K_merge(LoserTree ls, External b, SqStack* S) {
    int i, q;
    // 从每个栈中弹出第一个元素作为初始值
    for (i = 0; i < K; i++) {
        Pop(&S[i], &b[i].key);  // 从第 i 个栈中弹出第一个元素
    }
    // 创建败者树
    CreateLoserTree(ls, b);
    // 当胜者节点的值不为 MAXKEY 时，继续归并
    while (b[ls[0]].key != MAXKEY) {
        q = ls[0];  // 获取当前胜者节点（ls[0] 始终存储胜者索引）
        printf("%d ", b[q].key);  // 输出胜者节点的值
        // 从胜者节点的栈中弹出下一个元素
        Pop(&S[q], &b[q].key);
        // 调整败者树
        Adjust(ls, b, q);
    }
    printf("\n");  // 输出换行符
}

/**
 * 主函数
 */
void main() {
    int i, j;
    int e;
    SqStack S[K];  // 每个归并段对应一个栈
    LoserTree ls;  // 败者树
    External b;  // 外部节点数组
    // 初始化每个归并段的栈
    for (i = 0; i < K; i++) {
        InitStack(&S[i]);  // 初始化第 i 个栈
        Push(&S[i], MAXKEY);  // 将 MAXKEY 压入栈底，表示归并结束
        // 输入 3 个元素
        for (j = 0; j < 3; j++) {
            printf("S[%d] push: ", i);
            scanf("%d", &e);  // 从标准输入读取一个整数
            Push(&S[i], e);  // 将读取的整数压入栈中
        }
    }
    // 执行 K 路归并
    K_merge(ls, b, S);
}

11.4 置换-选择排序 - 减少m

m是外部文件经过内部排序之后 得到的初始归并段的个数，

m = ⌈n/l⌉, 其中 n 为外部文件中的记录数，l 为初始归并段中的记录数

注意事项：

• 当归并段为空时，选择工作区内最小数
• 当归并段不为空时，选择工作区内【大于归并段最大值的-归并段最后一个值】最小数
• 不能被放进归并段时，需重新创建一个归并段

11.5 最佳归并树

2路归并

多路归并

补充虚段

k路最佳归并树：

• 一定是一棵严格的 k叉树
• 只有度为0和度为k的结点

添加虚段的数量：

初始归并段数量 + 虚段数量 = n₀ = 度为0的结点数

度为k的结点数 = n_k

① 总结点数 = n = n₀ + n_k

② 叉的数量 = 分支结点 n_k * 每个分支结点发出的分叉数 k = 除根节点外的其他结点都被一个分叉连着 n - 1 即 n_k * k = n - 1

① 和 ② => n₀ =（k-1）n_k + 1 => n_k = (n₀ - 1) / (k - 1) 如果是“严格k叉树”一定能除得尽

① 若(初始归并段数量 -1) % (k-1)=0，说明刚好可以构成严格k叉树，此时不需要添加虚段

② 若(初始归并段数量 -1) % (k-1) = u ≠ 0，则需要添加虚段(k-1) - u个

例题：设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是()
A.1 B.2 C.3 D.4

（120 - 1）% (12 - 1) = 9; 则补充 (12 - 1) - 9 = 2

例题：已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权(外部)路径长度最小的是()
A.27 B.46 C.54 D.56

（6 - 1）% (3 - 1) = 1 ≠ 0; 需要补充的虚段个数是1；则变成【0，2，3，4，5，6，7】，WPL_min = (2+3)*3 + (4+5)*2 + (6+7)*1 = 15 + 18 + 13 = 46

参考：

教材：严蔚敏《数据结构》（C语言版）.pdf

视频：

外部排序

败者树

置换选择排序

博客：

多路平衡归并败者树(Tree of Loser)算法