【数据结构】置换-选择排序、最佳归并树

【数据结构】外部排序、败者树

承接上文小结里的内容。可用“置换—选择排序”进一步减少初始归并段数量。

1. 置换-选择排序

1. 外部排序

用于内部排序的内存工作区 WA 可容纳l个记录，则每个初始归并段也只能包含l个记录。若文件共有n个记录，则初始归并段的数量r=n/l。

优化：可以用一片更大的内存区域来进行内部排序，如：可容纳18个记录。

2. 置换-选择排序

说明：每置换出去一个数，则在MINIMAX中记录，并重新让一个元素进入工作区WA，重新进行置换。但是要注意，置换出去的数不能小于MINIMAX。当工作区WA的数满了，即工作区WA中的数都比MINIMAX更小的时候，则说明此归并段结束，进入下一个归并段，依次循环，直到所有元素置换完毕。

最终可得到如下的结果。 很明显，初始归并段数量更少。

使用置换-选择排序，可以让每个初始归并段的长度超越内存工作区大小的限制。

2. 最佳归并树

1. 归并树的性质

每个初始归并段看作一个叶子结点，归并段的长度作为结点权值，则上面这棵归并树的带权路径长度WPL=2*1+(5+1+6+2)*3=44=读磁盘的次数=写磁盘的次数。

重要结论：归并过程中的磁盘I/O次数=归并树的WPL*2。

要让磁盘I/O次数最少，就要使用归并树WPL最小（哈夫曼树）。

【数据结构】树和森林的相互转换及哈夫曼树

2. 多路归并的最佳归并树

注意：对于k叉归并，若初始归并段的数量无法构成严格的k叉归并树，则需要补充几个长度为0的“虚段”，在进行k叉哈夫曼树的构造。

3. 添加虚段的数量

k叉的最佳归并树一定是一棵严格的k叉树，即树中只包含度为k、度为0的结点。设度为k的结点有nk个，度为0的结点有n0个，归并树总结点数=n，则：

初始归并段数量+虚段数量=n0。

1. 若(初始归并段数量-1)%(k-1)=0，说明刚好可以构成严格k叉树，次数不需要添加虚段。
2. 若(初始归并段数量-1)%(k-1)=u≠0，则需要补充(k-1)-u个虚段。

例如：19个归并段进行3路归并，由于(19-1)%(3-1)=0，说明可以构成严格3叉树。而18个初始归并段进行3路归并。由于(18-1)%(3-1)=1≠0，说明需要添加虚段，添加虚段个数为(3-1)-1=1。

3. 小结

置换-选择排序：

设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。置换选择算法的步骤如下:

1. 从FI输入w个记录到工作区WA。
2. 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。
3. 将MINIMAX记录，输出到FO中去。
4. 若FI不空，则从FI输入下一个记录到WA中。
5. 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。
6. 重复3) ~5)，直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。
7. 重复2) ~6)，直至WA为空。由此得到全部初始归并段。