外部排序：归并排序
- 根据内存缓冲区大小，将外存上含有n个记录（n超超超大）的文件分成若干长度为h的子文件。
- 依次读入内存并利用内部排序算法对它们进行排序。（r个归并段，t为 internal sort时间）
- 将排序后得到的有序子文件重新写回外存，这些有序自文件称为归并段（顺串）。
- 对这些归并段进行逐趟归并（趟数S，每趟比较n-1次），使归并段逐渐由小到大直至得到整个有序文件。（归并路数m, 初始归并段数，IO次数 = logm r）
时间复杂度
- S趟归并总共需要比较的次数
败者树：树形选择排序的变体
失败树
例
- 运用败者树，S趟m路归并的比较次数为
与路数m无关了！！！但并不是能无限增大m，每个缓冲区变小了
置换-选择排序
算法思想
划分不等长的归并段，归并段内部有序
归并树
归并树
最佳归并树: 结点数值为归并段长度
例
哈夫曼树
补0结点
补充0结点个数计算
例
2019真题
