当前位置：首页 > news >正文

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

news 来源：原创 2025/5/15 13:04:19

外部排序

文章目录

外部排序
- 11.1 外存信息的存取
- 11.2 外部排序的方法
- 11.3 多路平衡归并的实现 - 增加k
- 11.4 置换-选择排序 - 减少m
- 11.5 最佳归并树

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

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)算法

外部排序

文章目录

11.1 外存信息的存取

11.2 外部排序的方法

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

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

11.5 最佳归并树

相关文章：