目录

1.外部排序的基本概念

2.外部排序

2.1.外部排序的思想

2.2.外部排序的开销

2.3.优化——多路归并

3.败者树

4.置换选择排序

4.1.算法思想

4.2.手算过程

5.最佳归并树

---

1.外部排序的基本概念

外存中的数据读入内存→在内存中排序→数据写入外存

2.外部排序

2.1.外部排序的思想

采用归并排序的思想和方法

1.数据初始状态

2.将（36、8、26）（42、9、48）分别存入输入缓冲区1、输入缓冲区2

3.将输入缓冲区1和输入缓冲区2的数据进行递增排序

4.将输入缓冲区1和输入缓冲区2的数据通过输出缓冲区逐一写入外存，形成一个有序归并段

5.将（1、37、25）（45、27、28）分别存入输入缓冲区1、输入缓冲区2

6.将输入缓冲区1和输入缓冲区2的数据进行递增排序

7.将输入缓冲区1和输入缓冲区2的数据通过输出缓冲区逐一写入外存，形成一个有序归并段

8.对剩余12块内存依次进行上述操作，总共需要进行16次读操作和16次写操作，得到初始归并段

9.第一次归并：读入归并段1和归并段2中的第一块磁盘（相对最小），进行排序

10.依次找出这两个输入缓冲区中最元素，并将其移动到输出缓冲区中，当输出缓冲区满，则写入外存（1、8、9）

11.继续找出这剩余元素中的最小元素，直到某一个缓冲区中空，则读入其所属归并段的后一个内存块的数据，并继续进行上述操作。直到两个缓冲区都空，且归并段1和归并段2中的元素全部读入内存，此时归并段1和归并段2就得到了一个有序的递增序列

输入缓冲区1空

输入归并段1的第二块内存 

 

排序完成，归并段1和归并段2递增有序 

12.对剩余的六个归并段进行上述操作，八个归并段→四个归并段

13.第二次归并：继续采用此方法依次取出归并段1和归并段2（归并段1为八个归并段时的归并段1和归并段2，归并段2为八个归并段时的归并段3和归并段4）的各个块进行排序操作（步骤9、10、11）→四个归并段→两个归并段

原归并段1、2排序形成归并段1

原归并段3、4排序形成归并段2

14.第三次归并：继续排序归并段1、2，形成最后的有序递增序列

 

2.2.外部排序的开销

上述外部排序中：形成初始归并段→第一次归并（8 ~ 4）→第二次归并（4 ~ 2）→第三次归并(2 ~ 1)（每个过程都需要读和写16次，共32 + 32 * 3 = 128次）

总时间开销 = 内部排序所需时间 + 内部归并所需时间 + 外部读写所需时间

2.3.优化——多路归并

改用四路归并：初始化归并段→第一次归并（8 ~ 2）→第二次归并（2 ~ 1）

需要读写次数：32 + 32 * 2 = 96

但是，与此同时，缓冲区的数量也要变成四个（k路归并需k个缓冲区）

结论：1.对于 r 个初始归并段进行 k 路归并，需要归并趟数 = （向上取整，归并树高度）
2.提升外部排序的速度、减少读写磁盘的速度的方法：提高 k 值，降低 r 值。

提高 r 值：增加归并段长度

但是，提高 k 有负面影响：

A.需要的缓存空间升高（k路归并需k个缓冲区）

B.内部归并的所需时间提高（选出最小关键字需要进行k - 1次比较）

3.败者树

视为一棵完全二叉树

1.将每个归并段的第一个元素作为叶子结点加入败者树中

2.从左至右、从上往下的更新分支节点的信息：判断其左右子树的大小，除了根节点（最上面那个结点）记录冠军来自哪个归并段外，其余各分支节点记录的是失败者来自哪个归并段

3.取出最小的元素1后，从其所属的归并段中取出下一个元素6，依次与从叶子结点到根节点的各个结点所记录的败者信息进行对比

 引进败者树后，选出最小的关键字，仅需log2k次比较（向上取整）

4.置换选择排序

4.1.算法思想

使用选择置换排序，可以让每个初始段的长度不再受限于内存工作区大小

设内存工作区最多容纳w个数据

①将待排序文件FI输入w个数据到内存工作区WA中

②选择WA中关键字最小的数据，输出到FO中，并且用MIN记录该最小关键字

③若FI不空，则从FI中继续输入文件到WA

④ 从WA中选出比MIN更大的关键字的数据，输出并更新此最小关键字作为新MIN

⑤重复②~④直到WA中的每个关键字都＞MIN为止，由此得到一个新的归并段

⑥重复②~⑤，直到WA空，得到全部初始归并段

4.2.手算过程

1.初始状态

归并段1： 

2.4、6、9依次加入内存工作区中，（4、6、9）选择最小的元素4，输出4并更改MIN = 4

3.加入7，（7、6、9）选择最小元素6 > MIN = 4，输出6并更改MIN = 6

4.加入13，（7、13、9）选择最小元素7 > MIN = 6，输出7并更改MIN = 7

5.加入11，（11、13、9）选择最小元素9 > MIN = 7，输出9并更改MIN = 9

6.加入16，（11、13、16）选择最小元素11 > MIN = 9，输出11并更改MIN = 11

8.加入14，（14、13、16）选择最小元素13 > MIN = 11，输出13并更改MIN = 13

9.加入10，（14、10、16）选择最小元素10 < MIN = 13，标记13为不可输出，选择第二小的元素14 > MIN = 13，输出14并更改MIN = 14

10.加入22，（22、10、16）选择最小元素16  > MIN = 14，输出16并更改MIN = 16

11.加入30，（22、10、30）选择最小元素22 > MIN = 16，输出并更改MIN = 22

12.加入2，（2、10、30）选择最小元素2 < MIN = 22，标记2为不可输出，选择第三小的元素30 > MIN = 22，输出30并更改MIN = 30

13.加入3，（2、10、3）选择最小元素3 < MIN = 30，标记2为不可输出，此时，输出缓冲区中的三个元素都是不可输出元素，则第一个归并区到上一个输出元素为止（4、6、7、9、11、13、14、16、22、30）

归并段2： 

14.（2、10、3）选择最小元素2，输出2并更改MIN = 2

15.加入19，（19、10、3）选择最小元素3 > MIN = 2，输出3并更改MIN = 3

16.加入20，（19、10、20）选择最小元素10 > MIN = 3，输出10并更改MIN = 10

17.加入17，（19、17、20）选择最小元素17 > MIN = 10，输出17并更改MIN = 17

18.加入1，（19、1、20）选择最小元素1 < MIN = 17，标记1为不可输出，选择第二小的元素19 > MIN = 17，输出19并更改MIN = 19

19.加入23，（23、1、20）选择最小元素20 > MIN = 19，输出20并更改MIN = 20

20.加入5，（23、1、5）选择最小元素5 < MIN = 20，标记5为不可输出，选择第三小的元素23 > MIN = 23，输出23并更改MIN = 23

21.加入36，（36、1、5）选择最小元素36 > MIN = 36，输出36并更改MIN = 36

22.加入22，（12、1、5）选择最小元素12 < MIN = 36，标记12为不可输出时，输出缓冲区中的三个元素都是不可输出元素，则第二个归并区到上一个输出元素为止（2、3、10、17、19、20、23、36）

第三个归并段：

23.（12、1、5）选择最小元素1，输出1并更改MIN = 1

24.加入18，（12、18、5）选择最小元素5 > MIN = 1，输出5并更改MIN = 5

25.加入21，（12、18、21）选择最小元素12 > MIN = 5，输出12并更改MIN = 12

26.加入39，此时，待排序文件空，将内存工作区中的剩余数据按序输出，即18、21、39，则第三个归并段为（1、5、12、18、21、39）

5.最佳归并树

1.性质和构造完全相同于哈弗曼树

2.与哈弗曼树的区别：

k叉树，其中k > 2时：需要判断是否能满足构造完全k叉树，若不满足，则需要添加长度为0的“虚段”

①若（初始归并段数量 - 1） % （k - 1） = 0，则能构成完全k叉树

②若（初始归并段数量 - 1） % （k - 1）= u ≠ 0，则说明需要添加（k - 1）- u 个虚段才能构成完全二叉树