一、置换选择排序

1、磁盘排序过程：
􀂄 （1）文件分成若干尽可能长的初始顺串；
􀂄 （2）逐步归并顺串归，最后形成一个已排序的文件。

2、置换选择算法

置换选择排序的核心思想是利用最小值堆（或最大值堆）对数据进行处理。每输出一个最小值（或最大值），就从缓冲区中读入下一个数。

置换选择算法的效果：如果堆的大小是M，一个顺串的最小长度就是M个记录，至少原来在堆中的那些记录将成为顺串的一部分。最好的情况下，例如输入已经被排序，有可能一次就把整个文件生成为一个顺串。

扫雪机模型：扫雪机模型显示扫雪机在环绕一圈过程中的行为。根据“扫雪机”模型的分析，可以预计平均情况下顺串总长度是数组长度的两倍。

采用置换选择算法排序的一个例子：