数据结构：外部排序+胜/败者树_败者树是哈夫曼树吗?

排序之外部排序

有时，待排序的文件很大，计算机内存不能容纳整个文件，这时候对文件就不能使用内部排序了（这里做一下说明，其实所有的排序都是在内存中做的，这里说的内部排序是指待排序的内容在内存中就可以完成，而外部排序是指待排序的内容不能在内存中一下子完成，它需要做内外存的内容交换），外部排序常采用的排序方法也是归并排序，这种归并方法由两个不同的阶段组成：

1、采用适当的内部排序方法对输入文件的每个片段进行排序，将排好序的片段（成为归并段）写到外部存储器中（通常由一个可用的磁盘作为临时缓冲区），这样临时缓冲区中的每个归并段的内容是有序的。

2、利用归并算法，归并第一阶段生成的归并段，直到只剩下一个归并段为止。

例如要对外存中4500个记录进行归并，而内存大小只能容纳750个记录，在第一阶段，我们可以每次读取750个记录进行排序，这样可以分六次读取，进行排序，可以得到六个有序的归并段，如下图：

每个归并段的大小是750个记录，记住，这些归并段已经全部写到临时缓冲区（由一个可用的磁盘充当）内了，这是第一步的排序结果。

完成第二步该怎么做呢？这时候归并算法就有用处了，算法描述如下：

1、将内存空间划分为三份，每份大小250个记录，其中两个用作输入缓冲区，另外一个用作输出缓冲区。首先对Segment_1和Segment_2进行归并，先从每个归并段中读取250个记录到输入缓冲区，对其归并，归并结果放到输出缓冲区，当输出缓冲区满后，将其写道临时缓冲区内（外部存储器中），如果某个输入缓冲区空了，则从相应的归并段中再读取250个记录进行继续归并，反复以上步骤，直至Segment_1和Segment_2全都排好序，形成一个大小为1500的记录，然后对Segment_3和Segment_4、Segment_5和Segment_6进行同样的操作。

2、对归并好的大小为1500的记录进行如同步骤1一样的操作，进行继续排序，直至最后形成大小为4500的归并段，至此，排序结束。

可以用一个图示表示上述算法的归并效果：

多路归并算法：

以上对外部排序如何使用归并算法进行排序进行了简要总结，提高外部排序需要考虑以下问题：

1、如何减少排序所需的归并趟数。

2、如果高效利用程序缓冲区，使得输入、输出和CPU运行尽可能地重叠。

3、如何生成初始归并段（Segment）和如何对归并段进行归并。

三、外部排序：
外部排序分为两个独立的阶段。首先，将含有n个记录的文件分为若干长度为l的子文件（归并段），依次读入内存并用内部排序方法进行排序，将排序后的子文件重新写入外存。然后对这些归并段进行逐趟归并。

提高外排的效率应主要着眼于外存信息的读写次数，而这与归并的趟数成正比。对m个初始归并段进行k路平衡归并时**，m越小或k越大**，便能减少趟数。

当k越大，归并时，需要的比较次数就越多，可以利用败者树减少比较次数。

为了减小m，可以用置换选择排序。由置换选择生成所得的初始归并段，各段长度不等。可以构造一棵哈夫曼树作为归并树，使外部归并时所需的读写次数最少。

败者树
胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。
　　不同的是，胜者树的中间结点记录的是胜者的标号；
　　而败者树的中间结点记录的败者的标号。
　　胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。在k路归并排序中经常用到。
　　胜者树重构：
　　当叶子结点b3的值变为11时，重构的胜者树如Fig. 2所示。

1.     b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；
   1

2.     b3 PK b0，b0胜b3负，内部结点ls[2]的值为0；
   1

3.     b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；
   1

4.     b0 PK b1，b1胜b0负，内部结点ls[1]的值为1。.
   1

　　败者树重构：将新进入选择树的结点与其父结点进行比赛：将败者存放在父结点中；而胜者再与上一级的父结点比较。


置换选择排序：

从内存工作区中找>29的最小值。
>38的最小值
.。。