置换-选择算法

为什么要引入置换-选择排序

我们都知道，减少初始归并段个数r可以减少归并趟数S。若总的记录个数为n，每个归并段的长度为t，则归并段的个数为r=[n/t]。采用内部排序方法得到的各个初始归并段长度都相同（除最后一段外），它依赖于内部排序时可用内存空间工作区的大小。因此，必须探索新的方法，用来产生更长的初始归并段，这就是引入置换-选择算法的原因。

算法实现步骤

选择内存缓冲区中的一个数，该数需要符合以下的条件：

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

其具体步骤如下：

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