置换选择排序算法说明

发布时间：2022-07-10 11:56 所属栏目：51 来源：互联网

导读：上一节介绍了增加 k-路归并排序中的 k 值来提高外部排序效率的方法，而除此之外，还有另外一条路可走，即减少初始归并段的个数，也就是本章第一节中提到的减小 m 的值。 m 的求值方法为：m=n/l（n 表示为外部文件中的记录数，l 表示初始归并段中包含的记录数

　　上一节介绍了增加 k-路归并排序中的 k 值来提高外部排序效率的方法，而除此之外，还有另外一条路可走，即减少初始归并段的个数，也就是本章第一节中提到的减小 m 的值。
　　m 的求值方法为：m=⌈n/l⌉（n 表示为外部文件中的记录数，l 表示初始归并段中包含的记录数）

　　置换—选择排序算法的具体操作过程为：

　　首先从初始文件中输入 6 个记录到内存工作区中；
　　从内存工作区中选出关键字最小的记录，将其记为 MINIMAX 记录；
　　然后将 MINIMAX 记录输出到归并段文件中；
　　此时内存工作区中还剩余 5 个记录，若初始文件不为空，则从初始文件中输入下一个记录到内存工作区中；
　　从内存工作区中的所有比 MINIMAX 值大的记录中选出值最小的关键字的记录，作为新的 MINIMAX 记录；
　　重复过程 3—5，直至在内存工作区中选不出新的 MINIMAX 记录为止，由此就得到了一个初始归并段；

　　当选不出 MINIMAX 值时，表示一个归并段已经生成，则开始下一个归并段的创建，创建过程同第一个归并段一样，这里不再赘述。

　　在上述创建初始段文件的过程中，需要不断地在内存工作区中选择新的 MINIMAX 记录，即选择不小于旧的 MINIMAX 记录的最小值，此过程需要利用“败者树”来实现。

　　同上一节所用到的败者树不同的是，在不断选择新的 MINIMAX 记录时，为了防止新加入的关键字值小的的影响，每个叶子结点附加一个序号位，当进行关键字的比较时，先比较序号，序号小的为胜者；序号相同的关键字值小的为胜者。

（编辑：ASP站长网）