置换-选择排序(生成初始归并段)
核心主旨与大白话记忆
- 为什么要这玩意? 传统的内存排序只能生成大小严格为 的归并段;置换-选择排序通过“动态腾挪”,能生成远大于内存容量 的归并段(平均长度可达 ),大大减少后面的归并趟数。
- 大白话形象记忆(选秀淘汰制):
内存只有 个名额。
- 每次从台上的 个人里选最小的(冠军)出道(输出);
- 台下新上来一个人填补空缺;
- 死标准:新来的人要是比刚才出道的冠军还要小,说明他如果现在出道就会“破坏递增排队秩序”,立刻被打入冷宫(冻结挂起),不能参与当前轮次比大小!
- 等台上所有人全部被打入冷宫,说明本轮选秀(归并段)结束!全员解冻,开启下一批!
一、置换-选择排序的“死操作流程”
考场死规则(3 秒判断)
- 选 MIN 输出:从内存可用元素中选最小的数输出到当前归并段;
- 填补空缺:输入流读入下一个新数;
- 冻结判定:
- 新数 MIN 合格,继续留在台上参加当前归并段竞争!
- 新数 MIN 冻结(打上冷宫标记
*),绝不参与当前段!- 换段时机:当内存工作区 个记录全被冻结时,当前归并段结束 全员解冻,开启下一个新归并段。
二、经典真题全流程推演(手把手模拟)
题目条件:文件总记录数 ,内存工作区容量 。
输入流:51, 94, 37, 92 | 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 42, 8, 90, 166, 100
初始填充:
读入前 4 个数:内存池 。
【第一归并段(RUN 1)】
- 内存 ,最小是 37 输出 37;读入
14。- 冻结 14*。可用:。
- 最小是 51 输出 51;读入
63。- 可用。可用:。
- 最小是 63 输出 63;读入
15。- 冻结 15*。可用:。
- 最小是 92 输出 92;读入
99。- 可用。可用:。
- 最小是 94 输出 94;读入
48。- 冻结 48*。可用:。
- 最小是 99 输出 99;读入
56。- 冻结 56*。
- 内存全为冷宫数 RUN 1 结束!
- RUN 1 内容:
37, 51, 63, 92, 94, 99(长度为 6)。
- RUN 1 内容:
【第二归并段(RUN 2)】
全员解冻:内存可用为 。
- 最小是 14 输出 14;读入
23( 可用)。 - 最小是 15 输出 15;读入
60( 可用)。 - 最小是 23 输出 23;读入
31( 可用)。 - 最小是 31 输出 31;读入
17( 冻结 17*)。 - 最小是 48 输出 48;读入
42( 冻结 42*)。 - 最小是 56 输出 56;读入
8( 冻结 8*)。 - 最小是 60 输出 60;读入
90( 可用)。 - 最小是 90 输出 90;读入
166( 可用)。 - 最小是 166 输出 166;读入
100( 冻结 100*)。 - 内存全为冷宫数 RUN 2 结束!
- RUN 2 内容:
14, 15, 23, 31, 48, 56, 60, 90, 166(长度为 9)。
- RUN 2 内容:
【第三归并段(RUN 3)】
全员解冻:内存可用为 。 输入流此时已空,内存中剩下的 4 个数按自然升序输出:
- 依次输出:
8, 17, 42, 100 - RUN 3 内容:
8, 17, 42, 100(长度为 4)。
三、极高频考点总结(选择题与大题踩分点)
| 考察维度 | 考场标准结论 | 理由/场景 |
|---|---|---|
| 归并段最大可能长度 | 原文件原本就完全单调递增,无任何元素被冻结,1 段直接吞下所有记录 | |
| 归并段最小可能长度 | 原文件完全单调递减,后续每个读入的数都被立刻冻结,输出完最初 个数立即换段 | |
| 归并段平均长度 | 在输入关键字随机分布时,数学期望平均长度约为 | |
| 段长度是否固定 | 不固定 | 随输入数据的有序程度动态变化 |