(72)王道数据结构-置换-选择排序

原文地址:置换-选择排序

基本概念

生成初始归并段时，我们把含有 n 个记录的文件传入内存，按照给定的 内排序算法 或 置换-选择排序算法 划分成 m 个规模较小的有序的记录段。

实现过程

1.把含有 n 个记录的文件，按内存大小 w 分成若干长度为 w 的子文件（归并段）

2.分别将各子文件（归并段）调入内存，采用有效的内排序方法排序后送回外存。产生 n/w 个初始归并段

算法思想

前提条件

1.该数必须大于当前初始归并段中任意数字

2.该数是符合条件1的可选数中最小的一个

如果符合上述条件，则将该数加入当前初始归并段，直到内存缓冲区中的所有记录都比当前初始归并段最大的记录小时，就生成了一个初始归并段。重复上述过程，生成多个初始归并段，直到文件的所有记录都被归入某个初始归并段

具体步骤

1.首先从初始文件中输入 l 个记录到内存工作区中

2.从内存工作区中选出关键字最小的记录，将其记为 MINIMAX 记录

3.将 MINIMAX 记录输出到归并段文件中

4.此时内存工作区中还剩余 l-1 个记录，若初始文件不为空，则从初始文件中输入下一个记录到内存工作区中

5.从内存工作区中的所有比 MINIMAX 值大的记录中选出值最小的关键字的记录，作为新的 MINIMAX 记录

6.重复过程 3—5，直至在内存工作区中选不出新的 MINIMAX 记录为止，由此就得到了一个初始归并段

7.重复 2—6，直至内存工作为空，由此就可以得到全部的初始归并段