外部排序：归并排序

1. 根据内存缓冲区大小，将外存上含有n个记录（n超超超大）的文件分成若干长度为h的子文件。
2. 依次读入内存并利用内部排序算法对它们进行排序。（r个归并段，t为 internal sort时间）
3. 将排序后得到的有序子文件重新写回外存，这些有序自文件称为归并段（顺串）。
4. 对这些归并段进行逐趟归并（趟数S，每趟比较n-1次），使归并段逐渐由小到大直至得到整个有序文件。（归并路数m, 初始归并段数，IO次数 = logm r）
   时间复杂度

• S趟归并总共需要比较的次数
  

败者树：树形选择排序的变体

失败树
例

• 运用败者树，S趟m路归并的比较次数为
  

  与路数m无关了！！！但并不是能无限增大m，每个缓冲区变小了

置换-选择排序

算法思想
划分不等长的归并段，归并段内部有序

归并树

归并树

最佳归并树: 结点数值为归并段长度

例

哈夫曼树
补0结点
补充0结点个数计算
例
2019真题