外部排序

无法将所有记录一次性读入内存，无法采用内排序一次性将排序完成

外存信息的定位和存取受其物理特性的限制，无法利用内存可以随机存取的特点，如：

– 希尔排序中，相隔di的记录关键字可作比较；

– 堆排序中，完全二叉树中的父R[i]与子R[2i]、R[2i+1]可比；

– 快速排序中，需正向和逆向访问记录序列

外部信息存取

磁带：

顺序存取设备，只适用于存储顺序文件

ta：用于磁头定位在物理块起始位置的时间

tw：传输一个字符的时间

磁盘：

直接存取设备，适用于各类存储形式的文件

[工作原理]

磁盘可以是单片的，或有若干个盘片组成盘组

磁道：盘片上的同心圆

柱面：各盘面上半径相同的磁道合在一起

扇区：每个磁道等分为若干扇区(块)

读取信息的过程：

柱面号  移动磁头

盘面号(磁道号)   选定所用磁头

扇区/块号   磁盘一直高速旋转，磁头等待开始位置

tseek：磁头定位到磁道的时间

tla：等待时间

外部排序基本方法—归并排序法

预处理阶段

根据缓冲区的大小将外存上含有n个记录的文件

1. 分成若干长度为L的子文件
2. 依次读入内存并利用有限的内部排序算法对它们进行排序
3. 并将排序后得到的有序子文件重新写回外存，通常称这些有序子文件为“初始归并段”

对初始归并段进行多路合并(多路归并)

对初始归并段进行多次2-路归并排序，直至最后在外存上得到整个有序文件为止（原理同内排序的2路归并排序）

（其实就是将分开的部分两两合并，尽量保证每一组都相同，如果不同则在下一次合并中大小合）

归并中的所有次数都要计入读写过程，但是非归并的组则不需要

时间

外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间

tIO值是外存操作时间，远远大于tIS和tmg。

外部排序总时间，即取决于读写外存的次数d

提高外排序效率(缩短总时间)的途径

假设待排记录序列含m个初始归并段，外排时采用 k-路归并，则归并趟数s=[logkm]

优化目标：
减少合并趟数s，以减少I/O次数

方向1

减少m：在内存受限的情况下，扩大初始归并段长度（大于内存容纳数量），从而减少初始归并段个数m

采用置换-选择排序方法建立初始归并段；

方向2

增加k：进行基于败者树的多路(k路，k>2)归并。

多路(k路)平衡归并（增加k的值）

假设待排记录序列含m个初始归并段，外排时采用 k-路归并，则归并趟数s=[logkm]

归并时采用简单选择排序从k个记录中选择一个关键字最小的记录时的比较次数为c（简单选择，即为k-1）

采用树形选择排序（胜者树、败者树方法），选关键字最小的记录，此时c=log2k，则 C总=log2m，与k无关

这里重新声明一下树形选择排序：

树形选择排序，称为胜者树，即树中保留两两比较的胜者。

重构胜者树时，从胜者所在的归并段中补充一个新数据到胜者原叶子结点，再从此叶子结点向根方向依次比较更新一遍。这样从根结点至新补入记录的叶结点的路径上的所有结点都必须更新。

败者树与胜者树只在显示时不一样

败者树的特点：记录败者，胜者参加下一轮比赛

败者树的优点：重构时修改结点较少。

归纳

胜者树的特点：胜者留在树中，在两两比较后，在树结构中记录胜者，从叶子结点依次比到根，最后的胜者在根。

败者树的特点：在树结构中记录败者，胜者向上走，参加下一轮比赛，从叶子结点依次比到根，在根上记录最后一次的败者，胜者输出

败者树中保存的是多路归并段的归并段号，便于补充记录值

• 归并段号作为索引 ：当某个归并段的最小（或最大）元素被取出后，可以通过归并段号找到该归并段，并补充新的元素。败者树中的归并段号提供了这个信息。
• 便于更新 ：每当某个归并段的元素被取出并替换成下一个元素时，败者树中的相应叶子节点会被更新，且更新会沿着树的路径向上调整，以保持树的选择性质（即每次能够选出当前最小或最大元素）。而归并段号便于在更新过程中快速找到和修改相应的归并段。

败者树内存中实现说明

采用败者树来实现置换-选择排序：

1、对每个记录加入段号来记录其可能归属的归并段，初始进入败者树的WA个记录的段号为1；

2、当新记录FI进入败者树时，和minimax比较小时（即不会进入当前外存中的初始归并段了），新记录的段号为当前段号加一；否则为当前段号（即可以进入当前外存中的初始归并段）。

3、记录进行两两比较时，按“段号不同，段大为败；段号相同，key大为败”的比较规则进行比较并最终确定胜者，并修改minmax值为胜者的key值。

置换-选择排序（减少m的值）

k路归并和选择排序的结合，但它并不完全是传统意义上的 置换-选择排序

1. 初始准备：
   • 将外部数据集分成若干块，每一块包含最多 k 条记录，并将每块数据加载到内存中。每一块数据会被 局部排序 （可以使用内部排序算法，如快速排序、归并排序等），得到一组有序的归并段。
   • 这些有序归并段就被写回到外部存储中。现在外部存储中有多个小的有序归并段。
2. 归并阶段：
   • 设定一个初始的最小值 minimax，通常可以初始化为无穷大。
   • 加载归并段 ：从外部存储中选择 k 个有序的归并段，将它们加载到内存中。
3. 选择最小值并输出：
   • 在内存中的这 k 个记录中，找到 大于当前 minimax 的最小值 ，称为新的候选值。
   • 如果找到一个新的候选值，将这个值更新为 minimax，并将其输出到外部存储。
4. 更新归并段：
   • 一旦 minimax 被选出并输出，将该归并段中当前选出的元素替换为该归并段中的下一个记录。然后更新最小值，并继续查找。
   • 如果某个归并段中所有记录都已经输出且没有新的候选值可用，则该归并段已经被完全处理，并从内存中移除。
5. 处理归并段：
   • 如果在当前内存中的 k 个记录中， 没有任何记录大于当前 minimax ，说明这些记录无法再合并进已经排好的归并段。此时，将这些记录作为一个完整的归并段处理，并将其写回到外部存储。
   • 继续重复步骤 2 到 5，直到所有记录都被处理完毕。
6. 完成排序：
   • 直到所有的归并段都被完全处理并且输出完成时，数据已经完全排序好。最终的排序结果会被存储回外部存储中。

排序效果

• 初始排序段的长度不等
• 当输入文件记录的关键字大小随机分布时，初始归并段的长度为内存工作区大小w的两倍

缓冲区并行操作

使输入、输出和内部归并三种操作同时进行（硬件间的并行）

最佳归并树（k叉哈夫曼树）

进行k路归并时，初始归并段的不同搭配，会导致归并过程中I/O的次数不同。

例：

所有叶结点加权外通路长度的2倍

构造

附加(k-1)-(m-1)mod (k-1) 个长度为0的虚段

• 合并最小的 k 个节点 ：
• 从最小堆中取出频率最小的 k 个节点。
• 创建一个新的内部节点，其频率为这 k 个节点的频率和。
• 将这个新的内部节点插入到最小堆中。
• 重复 ：继续执行步骤 2，直到最小堆中只剩下一个节点，即最终构成了一个完整的树。
• 构造编码 ：类似二叉哈夫曼树，通过遍历树的每一条路径，可以为每个符号生成一个编码。通常，向左的分支记为 0，向右的分支记为 1。