置换-选择排序的作用

在外部排序中，初始归并段越少，后续归并趟数越少。

若用普通方法生成初始归并段，内存工作区能容纳 $L$ 个记录，则每个初始归并段最多只有 $L$ 个记录。若文件共有 $N$ 个记录，初始归并段数量约为：

$$
r=\lceil N/L\rceil
$$

置换-选择排序的目标是：在内存工作区大小不变的情况下，生成更长的初始归并段，从而减少 $r$。

基本思想

置换-选择排序维护一个内存工作区 WA，每次从 WA 中选择当前归并段能接上的最小记录输出。

核心变量是 MINIMAX：

  • MINIMAX 表示当前归并段最后输出的关键字；
  • 能接在当前归并段后面的记录必须满足关键字 $\ge \text{MINIMAX}$；
  • 若新读入记录的关键字 $< \text{MINIMAX}$，它不能放入当前归并段，只能留到下一个归并段。

操作过程

  1. 从初始待排序文件 FI 中读入 $L$ 个记录，填满内存工作区 WA。
  2. 从 WA 中选出关键字最小的记录，输出到初始归并段输出文件 FO。
  3. 把刚输出的关键字记为 MINIMAX。
  4. 从 FI 读入下一个记录，放入刚腾出的工作区位置。
  5. 若新记录关键字 $\ge \text{MINIMAX}$，它仍可参与当前归并段。
  6. 若新记录关键字 $< \text{MINIMAX}$，它被冻结，留到下一个归并段。
  7. 若 WA 中所有未冻结记录都小于 MINIMAX，当前归并段结束；输出归并段结束标志，解冻工作区记录，开始下一个归并段。

为什么能生成更长的初始归并段

普通方法一次只把 $L$ 个记录读入内存，内部排序后写成一个归并段，所以归并段长度被 $L$ 限制。

置换-选择排序则边输出、边读入新记录：

  • 若新读入记录能接在当前归并段后面，就继续留在当前归并段；
  • 只有不能接上的记录才冻结到下一段。

因此一个初始归并段可能包含远多于 $L$ 个记录。随机输入下，平均初始归并段长度通常可接近 $2L$。

手算规则

手算置换-选择排序时，不需要模拟底层文件读写，只抓住三件事：

规则 判断
当前段能输出谁 在 WA 中选关键字 $\ge \text{MINIMAX}$ 的最小记录
新读入记录能否加入当前段 看它是否 $\ge \text{MINIMAX}$
何时结束当前段 WA 中没有任何记录能接在当前段后面
小于 `MINIMAX` 的记录不是丢弃

它只是不能放入当前归并段，会被冻结，等下一个归并段开始时再参与选择。

# 小结
考点 记法
目的 减少初始归并段数量
关键结构 初始待排序文件 FI、输出文件 FO、内存工作区 WA
关键变量 MINIMAX，当前归并段最后输出的关键字
能加入当前段的条件 新记录关键字 $\ge \text{MINIMAX}$
当前段结束条件 WA 中所有记录都不能接在当前段后面
优势 初始归并段长度可超过内存工作区容量