题5

题5

题目

[!error]+
【2023 统考真题】对含有 个记录的文件进行外部排序,采用置换-选择排序生成初始归并段时需要使用一个工作区,工作区中能保存 个记录。请回答:
若文件中含有 19 个记录, 其关键字依次是 51,94,37,92,14,63,15,99,48,56,23,60,31, 17,43,8,90, 166,100,则当 时,可生成几个初始归并段? 各是什么?

对任意的 ,生成的第一个初始归并段的长度最大值和最小值分别是多少?

分析

[!NOTE]+
置换选择排序的核心逻辑在于，minimax中维护一个最小元素，作为比较标准，每次取出最小的minimax标准（如果它比前一个minimax标准更大），直到当前准备取出的元素，比维护的mini更小，我们就在minimax中锁定这个元素
如何理解这个mini，mini是当前minimax区域中的最小，max是，移出的元素，必须比当前的mini大（max）

解

[!done]+
题42