050替代选择排序
替代选择排序（Replacement Selection）发明者故事
050替代选择排序
5W1H 故事
Who（谁）
替代选择算法（Algorithm R）由 Donald E. Knuth 在《计算机程序设计艺术》第三卷第5.4.1节正式命名和分析。其思想源于1950年代IBM工程师和磁带时代外部排序的工程实践，E. H. Friend于1956年在JACM上发表的论文《Sorting on Electronic Computer Systems》中首次系统描述了类似方法。Knuth对其进行了严格的概率分析，证明了平均归并段长度约为2M的经典结论。
What（什么）
替代选择排序是外部排序（External Sorting）第一阶段使用的算法，用于从原始输入数据流中生成初始归并段（initial runs）。与简单地将M个元素装满内存后输出相比，替代选择利用优先队列（最小堆），在输出一个元素后立即从输入流补充一个新元素，从而使每个归并段的平均长度达到约2M，显著减少归并段数量，提高整体外排序效率。
When（何时）
1956年Friend提出原始思想；1973年Knuth在TAOCP第三卷中给出了Algorithm R的完整描述，并通过概率论证明了平均段长为2M的结论（假设输入为随机排列时），这一结论对外部排序工程实践影响深远。
Where（何处）
算法在IBM大型机和磁带驱动器主导的计算环境中被开发和应用，后被Knuth在斯坦福大学的研究工作中系统化，收录于TAOCP第三卷第5.4.1节，成为数据库系统和操作系统I/O子系统中外部排序的理论基础。
Why（为何）
在外部存储设备（磁带、磁盘）主导的时代，内存极其有限，无法将所有数据载入内存排序。必须将数据分成多个有序的归并段分批写出，再多路归并得到最终有序结果。归并段越长，所需归并轮次越少，I/O代价越低。替代选择比朴素的内存填满-输出方式产生更长的归并段（平均2M），使得整个外排序过程更高效。
How（如何）
算法维护一个大小为M的最小堆（“活跃堆”）和一个"冻结集合"（下一段缓冲）。初始将M个元素载入堆。每次从堆顶取出最小元素输出到当前归并段；然后从输入流读入下一个元素：若该元素 ≥ 上次输出的元素，则将其加入活跃堆（继续当前段）；否则将其加入冻结集合（属于下一段）。当活跃堆为空时，当前归并段结束，冻结集合成为新的活跃堆，开始下一段。重复直到输入流耗尽。
自然语言需求定义
替代选择算法模拟外部排序的初始段生成过程：使用固定大小M的最小堆作为内存缓冲区，从输入序列逐元素读取数据，维护当前归并段的输出。每次将堆顶最小元素输出，并用输入流的下一个元素补充堆；若新元素小于上次输出的元素，则该元素被"冻结"（划归下一个归并段）；当活跃堆耗尽时结束当前归并段，冻结元素构成新堆开始下一段。算法最终输出若干个各自有序的归并段，且每个归并段内元素严格非递减。
验收标准表格
| 编号 | 测试场景 | 输入 | 期望输出 / 行为 | 验收条件 |
|---|---|---|---|---|
| TC-01 | 标准示例验证 | 堆大小M=3，输入[5,3,4,2,8,1,6,9,7] |
生成归并段数量 ≤ 3，每段内有序 | 段数与内容符合算法逻辑 |
| TC-02 | 每段有序性 | 任意随机输入 | 每个归并段内元素非递减 | 对每段逐对检查 |
| TC-03 | 已排序输入产生1段 | M=3，输入[1,2,3,4,5,6,7,8,9] |
恰好产生1个归并段 | 段数 == 1 |
| TC-04 | 逆序输入产生多段 | M=3，输入[9,8,7,6,5,4,3,2,1] |
产生尽可能多的归并段 | 段数 ≥ 3 |
| TC-05 | 所有元素覆盖 | 任意输入 | 所有输入元素出现在某个归并段中 | 各段元素并集 == 输入集合（含重复） |
| TC-06 | 平均段长约2M | M=10，输入100个随机数 | 归并段数量 ≤ 10（期望约5） | 段数合理（不超过输入数/M） |
| TC-07 | 边界：输入数 < M | M=5，输入[3,1,2] |
恰好1个归并段，内容有序 | 段数==1，内容正确 |
| TC-08 | 全相同元素 | M=3，输入[5,5,5,5,5] |
恰好1个归并段 | 段数==1 |
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
4
0- 0
已为社区贡献10条内容
所有评论(0)