8.7.4 置换选择排序

教材导航 · 第8章

原书定位

印刷页P389起,对应PDF第401页。下文为目视整理的知识提要;完整内容见原书对照。

用于生成较长的初始归并段。内存工作区保存若干候选,每次输出不小于本段最后输出值的最小候选,再读入一条新记录;新记录过小则冻结到下一段,不能接进当前有序段。

当前段没有可用候选时结束,解冻并生成下一段,可用败者树或堆实现选择。初始段长度取决于输入顺序,通常不等长;随机模型下平均约为工作区容量的 2 倍,不是固定恰好 2 倍。已递增输入可形成一个很长的段,递减输入则段长接近工作区容量。

置换选择生成初始归并段

置换选择生成初始归并段,原书P390。

对应练习

8.7 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P389,PDF第401页

原书对照,原书P390,PDF第402页