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 个虚段才能构成完全二叉树
