置换选择排序的扫雪机模型

置换选择排序

置换选择排序是用于文件外排序的一种算法，其核心思想是：利用在内存工作区中建立的堆，对输入文件中的数据进行筛选，从而生成尽可能长的初始顺串。

扫雪机模型

扫雪机模型是一种用于解释置换选择排序生成初始顺串的平均长度的模型。

想象有一个圆形的操场，操场上有一台扫雪机正在进行扫雪。雪正在均匀地下着，这里的均匀指的是雪落在圆形操场的任意一点处的概率相同。当扫雪机铲雪到一定时间后，操场上雪的数量恒定，其后任意时刻其形状都如下图所示，是一个三角形。那么，在这种稳定的情况下，扫雪机每转操场一圈，它铲的雪是多少呢？我们设当雪的状态相对稳定时，操场上雪的数量为M，则从下图我们很容易看出：此时铲雪机每扫一圈，它铲的雪的数量（下图中的长方形） = 操场上现存的雪的数量（下图中深红色的三角形）的两倍 = 2M.

但是扫雪机模型和置换选择排序的关系在哪呢？我觉得这是理解扫雪机模型最关键的一点。我们可以做一个类比：

圆形操场类比为内存工作区中建立的堆，雪类比为待处理的数据；雪被扫雪机铲走意味着数据进入输出文件，成为输出顺串的一部分，雪没被扫雪机铲走意味着数据停留在内存工作区中，且不会在这一轮的置换选择排序中成为输出顺串的一部分；扫雪机扫一轮意味着一轮置换选择排序；

对于一个数据而言，当它从输入文件中被读出并进入内存工作区时，它有两种选择，一种是进入内存工作区的堆中，另一种是不进入堆中。注意到，进入堆中的数据一定会成为输出顺串的一部分，因此数据进入堆可以对应雪落在扫雪机还未经过的路径上；而未进入堆的数据可以视为雪落在扫雪机已经经过的路径上。由于输入文件的数据是等概率分布的，所以输入数据的均匀性可以对应雪均匀地落下。

因此，扫雪机模型与置换选择排序其实是有一种一一对应的关系。在一轮置换选择排序中，设不进入堆中的数据（对应操场中没有被铲走的雪）数量为M，则置换选择排序算法形成的初始顺串长度（对应操场中被铲走的雪） = 2M。