Chapter 09 外排序

9.0 引言

• 内存是一种有限的资源, 现实世界的数据是海量的, 需要外部存储器的支持
• 外存文件的排序本质上还是借助内排序完成, 需要多次内外村之间的数据交换

9.1 计算机存储器

9.2 文件的组织与管理

参见 ICS

9.3 外排序

• 根据内存大小, 将外存中的数据文件划分成若干段, 每次读入一段用内排序方法进行排序.
• 已排好序的段称为 顺串或归并段
• 顺串写回外存等待进一步处理, 让出内存空间处理文件的其它未排序段

9.3.1 置换选择排序

• 将文件生成若干初始顺串 (顺串越长越好, 个数越少越好)
• 借助 RAM 中的堆完成

流程:

• 初始化最小堆, 从缓冲区读 \(M\) 个记录到数组中, 设置堆尾标志 \(\text{LAST}=M-1\), 建立最小堆
• 重复以下步骤直至堆空:
  (a) 将具有最小关键码值的记录送到输出缓冲区
  (b) 设 \(R\) 是输入缓冲区下一条记录
  (i) 若 \(R\) 的关键码不小于刚输出的关键码, 将 \(R\) 放到根节点.
  (ii) 否则, 使用 \(\text{LAST}\) 位置替代根节点, 把 \(R\) 放到 \(\text{LAST}\) 位置并设置 LAST=LAST-1
  (c) 重新调整堆

算法结束后, RAM 填满了不能处理的数据, 直接建成堆留待下一顺串处理.

平均顺串长度:

\[ Avg(M)=\frac{1}{2}(Avg(M)+1)+\frac{1}{2}(Avg(M-1)+1) \]

\[ Avg(M)=Avg(M-1)+2 \]

因此 \(Avg(M)=2M\)

9.3.2 归并排序

二路归并: 合并树高 \(\lceil \log_2m\rceil\)+1, 进行 \(\lceil \log_2m\rceil\) 遍扫描. 两个输入缓冲区, 一个输出缓冲区

通过减少顺串个数和增加同时归并的顺串数量可以减少归并趟数.

最佳归并树: K 叉 Huffman 树

总访外次数: Huffman 树叶节点带权路径和 \(\times 2\) (读+写)

在做 K 路归并的时候, 每次都要做 k-1 次比较, 代价较大, 因此诞生两种选择树: 赢者树和败者树

9.3.3 赢者树

用完全二叉树作为存储结构. 叶节点用数组 \(L[1..n]\) 表示, 内部节点用 \(B[1..n-1]\) 表示, \(B\) 实际存放的是 \(L\) 的索引.

9.3.3 败者树

败者树用父结点记录左右子结点进行比赛的败者, 而让胜者去参加更高阶段的比赛.

新增根节点 B[0] 存储整个比赛的胜者.

相比赢者树, 败者树更新的时候只需要和父节点比较即可. 相比胜者树比较次数不变但少了一次寻址 (不用访问兄弟节点)