第九章 外排序

进行外排序的原因：

  • 内存是有限的
  • 数据是海量的，需要外存的支持
  • 外排序本质借助内排序完成，进行许多次内外存之间的数据交换

9.1 主存储器和外存储器

9.2 文件的组织与管理

9.3 外排序

  • 把外存中的数据划分为若干段，每次读入内存一段并按照 内排序 方法进行排序，已排序的段或子文件叫做 顺串或归并段

外排序的基本过程

  • 置换选择排序：把外存文件初始化为尽可能长的有序顺串集
  • 归并排序：把顺串集合逐趟归并排序，形成全局有序的外存文件

外排序的时间组成

  • 产生初始顺串的内排序所需时间
  • 初始化顺串和归并过程所需的读写（I/O）时间
  • 内部归并所需要的时间
  • 关键：减少外存的 I/O 次数

9.3.1 置换选择排序

输入文件 -> 输入缓冲区 -> RAM -> 输出缓冲区 -> 输出顺串文件

  • 将文件生成若干尽可能少、尽可能长的顺串，借助在 RAM 中的堆来完成

置换选择算法

  1. 初始化最小堆：目的是提高 RAM 中排序的效率
    • （a）从缓存区读 M 个记录放到数组 RAM 中
    • （b）设置初始堆尾标志：LAST = M - 1（读入 RAM 的最后一个记录）
    • （c）建立一个最小值堆
  2. 重复以下步骤，直至堆空（结束条件：LAST < 0）
    • (a) 把具有最小关键码的记录（根节点）送到输出缓冲区
    • (b) 设 R 是输入缓冲区中的下一条记录
      • 如果（R 的关键值码 不小于 已输出的关键值码） 把 R 放到根节点
      • 否则 把 LAST 位置的记录放到根节点处，把 R 放到 LAST 位置，LAST = LAST - 1（减小堆的大小，刚存入的 R 不在现有堆中，由下一顺串处理）
    • (c) 重新排列堆，筛出根节点

算法分析

  • 一次顺串结束后，RAM 中填满了不能处理的数据，建成堆可以下次顺串处理
  • 大小是 M 的堆，生成顺串最小长度是 M，平均长度是 2M

算法实现

// 初始化输入输出文件
initFiles(inputFile, outputFile, in, out);
// 初始化堆的数据，读入n个数据
initMinHeapArry(inputFile, n, A);
// 建立最小值堆
MinHeap<Elem> H(A, n, n);
// 初始化inputbuffer，读入部分数据
initInputBuffer(input, inputFile);

for (int last = n - 1; last >= 0; ) {
     Elem mval = H.heapArray[0]; // 堆的最小值
     sendToOutputBuffer(input, output, iptF, optF, mval);
     Elem r;
     input.read(r); // 从输入缓冲区读入一个记录

     if (!less(r, mval)) {
          H.heapArray[0] = r;
     } else { // 否则用 last 位置记录代替根结点，把 r 放到 last
          H.heapArray[0] = H.heapArray[last];
          H.heapArray[last] = r;
          last--;
          H.setSize(last + 1);
     }

     if (last >= 0)
          H.SiftDown(0); // 堆调整
}
endUp(output, inputFile, outputFile);

9.3.2 归并排序

产生顺串 -> 归并排序

算法分析

  • 所需读写外存次数与归并趟数有关
  • 假设 m 个初始顺串，每次对 k 个顺串进行归并，则归并趟数为 ceil(logk m)
  • 为了减少归并趟数，两个方面入手：
    • 减少初始顺串的个数 m
    • 增加每次归并的顺串个数 k
  • 实现方式：使用最佳归并树
    • 最佳归并树：一个 Huffman 树，每个叶子结点表示一个顺串，结点的权值为该顺串的长度
    • 归并时，每次选择 k 个最小权值的结点进行归并

9.3.3 多路归并树

  • 赢者树
  • 败者树
  • 目的：减少比较次数，提高归并效率

赢者树的归并实现

  • 用完全二叉树作为存储结构
    • 叶子结点存放 k 个顺串的当前元素，非叶子结点存放其子结点中关键字较小者
    • 叶子结点用数组 L[0..n] 表示，非叶子结点用数组 B[0..n-1] 表示
      • 数组 B 中存储的是叶子结点在数组 L 中的下标
  • 赢者树的过程
    • 从树的最底层开始，比较每对叶子结点的关键字，将较小者上升到其父结点
    • 重复此过程，直到比较到根结点，根结点存放的是 k 个叶子结点中关键字最小的元素
    • 在过程中 B 数组存放的是每次比较的赢者的下标（也就是相应的顺串）
    • 每次输出根结点的元素后，从相应顺串中读入下一个元素，重新调整赢者树

败者树的归并实现

  • 败者树与赢者树类似，但非叶子结点存放的是其子结点中的败者，获胜者则去参加下一轮比较
  • 败者树比赢者树多了一个结点，在赢者树的根节点前增加一个结点，存放最终的获胜者
  • 败者树的调整过程
    • 每次输出根结点的获胜者后，从相应顺串中读入下一个元素
    • 从该叶子结点开始，沿路径向上比较，将败者存放在相应的非叶子结点中，直到到达根结点，更新最终的获胜者
  • 优点：每次调整只需 log(k) 次比较，只需要和内部结点比较，只需更改该路径上的结点
败者树的初始化实现
template<class T>
void LoserTree<T>::Initialize(T A[], int size,
     int (*winner)(T A[], int b, int c),
     int (*loser)(T A[], int b, int c)) {
     int i, s;
     n = size;
     L = A;
     // 初始化成员变量
     for (s = 1; 2 * s <= n - 1; s += s);      // 计算倒数第2层节点数
     LowExt = 2 * (n - s);
     offset = 2 * s - 1;

     // 最底层外部结点比赛
     for (i = 2; i <= LowExt; i += 2)
          Play((offset + i) / 2, i - 1, i, winner, loser);

     // 处理其余外部结点
     if (n % 2) {  // n 为奇数，内部结点和外部结点比一次
          // 暂存在父中的左胜者与外部右子结点比
          Play(n / 2, B[(n - 1)], LowExt + 1, winner, loser);
          i = LowExt + 3;
     } else
          i = LowExt + 2;

     // 剩余外部结点的比赛
     for (; i <= n; i += 2)
          Play((i - LowExt + n - 1) / 2, i - 1, i, winner, loser);
}
败者树的生成

沿叶节点（由小到大）所在子树的右分支向上比赛，右分支路径节点编号为奇

template<class T>
void LoserTree<T>::PLAY(int p, int lc, int rc, int(*winner)(T A[], int b, int c), 
int(*loser)(T A[], int b, int c)) {
     B[p] = loser(L, lc, rc);                                          
     // 败者索引放在 B[p] 中
     int temp1, temp2;
     temp1 = winner(L, lc, rc);                                   
     while (p > 1 && p % 2) {                                        
          // p 为奇数向上比赛
          temp2 = winner(L, temp1, B[p / 2]);     // 胜者与父比较
          B[p / 2] = loser(L, temp1, B[p / 2]);         
          // 败者留下
          temp1 = temp2;
          p /= 2;
     } // while
     B[p / 2] = temp1; 
}

败者树的调整

void LoserTree<T>::RePlay(int i, int (*winner)(T A[], int b, int c), 
                           int (*loser)(T A[], int b, int c)) {
    int p;
    if (i <= LowExt) 
        // 用于计算父结点索引的临时变量
        // 确定父结点的位置
        p = (i + offset) / 2;
    else  
        p = (i - LowExt + n - 1) / 2;

    B[0] = winner(L, i, B[p]);  // B[0]中保存胜者的索引
    B[p] = loser(L, i, B[p]);   // B[p]中保存败者的索引

    for (; (p / 2) >= 1; p /= 2) {  // 沿路径向上比赛
        int temp; 
        // 临时存放赢者的索引
        temp = winner(L, B[p / 2], B[0]);
        B[p / 2] = loser(L, B[p / 2], B[0]);
        B[0] = temp;
    }
}

9.3.4 多路归并的效率

假设对 k 个顺串进行归并：

  • 原始方法（每次线性查找最小值）
    • 每次找到最小值需要 Θ(k)
    • 生成一个大小为 n 的顺串总时间为 Θ(k · n)
  • 败者树方法（Loser Tree）
    • 初始化包含 k 个选手的败者树需要 Θ(k) 时间
    • 读入一个新值并重构败者树需要 Θ(log k) 时间
    • 因此产生一个大小为 n 的顺串总时间为 Θ(k + n · log k)

总结：败者树将每次选择最小值的复杂度从 Θ(k) 降为 Θ(log k)，当 n 很大时能显著提高归并效率。