置换-选择排序(生成初始归并段)

核心主旨与大白话记忆

  • 为什么要这玩意? 传统的内存排序只能生成大小严格为 的归并段;置换-选择排序通过“动态腾挪”,能生成远大于内存容量 的归并段(平均长度可达 ),大大减少后面的归并趟数。
  • 大白话形象记忆(选秀淘汰制):

    内存只有 个名额。

    1. 每次从台上的 个人里选最小的(冠军)出道(输出);
    2. 台下新上来一个人填补空缺;
    3. 死标准:新来的人要是比刚才出道的冠军还要小,说明他如果现在出道就会“破坏递增排队秩序”,立刻被打入冷宫(冻结挂起),不能参与当前轮次比大小!
    4. 等台上所有人全部被打入冷宫,说明本轮选秀(归并段)结束!全员解冻,开启下一批!

一、置换-选择排序的“死操作流程”

考场死规则(3 秒判断)

  1. 选 MIN 输出:从内存可用元素中选最小的数输出到当前归并段;
  2. 填补空缺:输入流读入下一个新数;
  3. 冻结判定:
    • 新数 MIN 合格,继续留在台上参加当前归并段竞争!
    • 新数 MIN 冻结(打上冷宫标记 *),绝不参与当前段!
  4. 换段时机:当内存工作区 个记录全被冻结时,当前归并段结束 全员解冻,开启下一个新归并段。

二、经典真题全流程推演(手把手模拟)

题目条件:文件总记录数 ,内存工作区容量 。 输入流:51, 94, 37, 92 | 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 42, 8, 90, 166, 100

初始填充:

读入前 4 个数:内存池 。


【第一归并段(RUN 1)】

  1. 内存 ,最小是 37 输出 37;读入 14。
    • 冻结 14*。可用:。
  2. 最小是 51 输出 51;读入 63。
    • 可用。可用:。
  3. 最小是 63 输出 63;读入 15。
    • 冻结 15*。可用:。
  4. 最小是 92 输出 92;读入 99。
    • 可用。可用:。
  5. 最小是 94 输出 94;读入 48。
    • 冻结 48*。可用:。
  6. 最小是 99 输出 99;读入 56。
    • 冻结 56*。
  7. 内存全为冷宫数 RUN 1 结束!
    • RUN 1 内容:37, 51, 63, 92, 94, 99(长度为 6)。

【第二归并段(RUN 2)】

全员解冻:内存可用为 。

  1. 最小是 14 输出 14;读入 23( 可用)。
  2. 最小是 15 输出 15;读入 60( 可用)。
  3. 最小是 23 输出 23;读入 31( 可用)。
  4. 最小是 31 输出 31;读入 17( 冻结 17*)。
  5. 最小是 48 输出 48;读入 42( 冻结 42*)。
  6. 最小是 56 输出 56;读入 8( 冻结 8*)。
  7. 最小是 60 输出 60;读入 90( 可用)。
  8. 最小是 90 输出 90;读入 166( 可用)。
  9. 最小是 166 输出 166;读入 100( 冻结 100*)。
  10. 内存全为冷宫数 RUN 2 结束!
    • RUN 2 内容:14, 15, 23, 31, 48, 56, 60, 90, 166(长度为 9)。

【第三归并段(RUN 3)】

全员解冻:内存可用为 。 输入流此时已空,内存中剩下的 4 个数按自然升序输出:

  • 依次输出:8, 17, 42, 100
  • RUN 3 内容:8, 17, 42, 100(长度为 4)。

三、极高频考点总结(选择题与大题踩分点)

考察维度考场标准结论理由/场景
归并段最大可能长度原文件原本就完全单调递增,无任何元素被冻结,1 段直接吞下所有记录
归并段最小可能长度原文件完全单调递减,后续每个读入的数都被立刻冻结,输出完最初 个数立即换段
归并段平均长度在输入关键字随机分布时,数学期望平均长度约为
段长度是否固定不固定随输入数据的有序程度动态变化