外部排序的基本概念
Q: 什么是外部排序？
A: 外部排序是指待排序的记录存储在外存中，无法一次性装入内存，需要在内存和外存之间进行多次数据交换，以达到排序整个文件的目的。
记忆辅助: 比如有一个 10GB 的大文件需要排序，但内存只有 1GB，这时就需要使用外部排序算法。
Q: 外部排序与内部排序的主要区别是什么？
A: 外部排序涉及内存和外存的数据交换，而内部排序不涉及。
记忆辅助: 内部排序就像在书桌上整理几本书，而外部排序就像整理整个图书馆的书籍，需要把书搬来搬去。
外部排序的方法
Q: 外部排序通常采用什么算法？
A: 外部排序通常采用归并排序算法。
记忆辅助: 归并排序非常适合处理外部排序，因为它可以将大文件分解成多个小文件进行排序，然后再合并成有序的大文件。
Q: 外部排序的两个主要阶段是什么？
A: 生成初始归并段和归并阶段。
记忆辅助: 可以把外部排序想象成两步走：第一步，把大文件分成小文件，并在内存中排序；第二步，把排好序的小文件合并成一个有序的大文件。
Q: 如何生成初始归并段？
A: 根据内存缓冲区大小，将外存上的文件分成若干长度为
记忆辅助: 就像把图书馆的书分成几堆，每堆的大小取决于书架的大小，然后把每堆书排好序。
Q: 如何进行归并阶段？
A: 对初始归并段进行逐趟归并，使归并段逐渐由小到大，直至得到整个有序文件。
记忆辅助: 就像把排好序的几堆书合并成一堆，每次合并都是有序的，最终得到一堆有序的书。
外部排序的总时间计算
Q: 外部排序的总时间由哪几部分组成？
A: 内部排序的时间 + 外存信息读/写的时间 + 内部归并的时间。
记忆辅助: 外部排序的时间主要花在磁盘读写上，因为磁盘读写速度比内存操作慢很多。
Q: 外部排序的主要时间消耗在哪里？
A: 外存信息读/写的时间。
记忆辅助: 可以把外部排序想象成搬运工在搬运货物，搬运货物的时间比整理货物的时间长得多。
Q: 如何减少外部排序的时间？
A: 应着力减少 I/O 次数，即减少磁盘读/写次数。
记忆辅助: 减少 I/O 次数就像减少搬运工搬运货物的次数，这样可以大大减少搬运时间。
多路平衡归并
Q: 增大归并路数有什么作用？
A: 增大归并路数可以减少归并趟数，进而减少总的磁盘 I/O 次数。
记忆辅助: 归并路数就像搬运工一次可以搬运的货物数量，数量越多，搬运次数越少。
Q:
A: 归并趟数
记忆辅助: 比如有 16 个初始归并段，采用 2 路归并，需要 4 趟归并；采用 4 路归并，只需要 2 趟归并。
Q: 归并树的高度与归并趟数有什么关系？
A: 归并树的高度 - 1 = 归并趟数
记忆辅助: 归并树的高度可以直观地反映归并的趟数，高度越高，趟数越多。
败者树的构造与应用
Q: 什么是败者树？
A: 败者树是树形选择排序的一种变体，可视为一棵完全二叉树，用于快速选择
记忆辅助: 败者树就像一场淘汰赛，每次比赛都淘汰失败者，最终决出冠军。
Q: 败者树的叶节点存放什么？
A:
记忆辅助: 败者树的叶节点就像比赛的选手，它们的值就是比赛的成绩。
Q: 败者树的内部节点存放什么？
A: 内部结点用来记忆左右子树中的 “失败者”，即关键字较大的元素。
记忆辅助: 败者树的内部节点记录了比赛的淘汰过程，每个节点都指向它的两个子节点中较大的那个。
Q: 败者树的深度为多少？
A:
记忆辅助: 败者树的深度与比赛的轮数有关，
Q: 使用败者树选择最小关键字需要比较多少次？
A:
记忆辅助: 使用败者树选择最小关键字就像查询比赛的冠军，只需要沿着树根到冠军节点的路径比较
Q: 败者树如何维护？
A: 败者树从下往上维护，每次调整只需与失败结点比较一次，维护时间复杂度为
记忆辅助: 败者树的维护就像更新比赛结果，每次只需要更新被击败的选手和它的祖先节点。
置换-选择排序
Q: 置换-选择排序的目的是什么？
A: 生成更长的初始归并段，减少归并趟数，从而减少 I/O 次数，提高外部排序的速度。
记忆辅助: 置换-选择排序就像一个聪明的搬运工，它会尽量把更多相同类型的货物放在一起搬运，这样可以减少搬运次数。
Q: 置换-选择排序生成的初始归并段长度有什么特点？
A: 初始归并段的长度平均是传统等长初始归并段的 2 倍，从而减少初始归并段的个数。
记忆辅助: 置换-选择排序生成的初始归并段长度不一定相等，但平均长度比传统方法更长，因此可以减少初始归并段的数量。
最佳归并树的构建
Q: 什么是最佳归并树？
A: 使 I/O 次数最少的归并树。
记忆辅助: 最佳归并树就像一个最优的搬运方案，它可以使搬运次数最少。
Q: 如何构建最佳归并树？
A: 采用哈夫曼树的思想，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并。
记忆辅助: 构建最佳归并树就像安排搬运货物的顺序，应该先搬运轻的货物，最后搬运重的货物，这样可以使总的搬运量最小。
Q: 最佳归并树的带权路径长度 WPL 等于什么？
A: WPL = 归并过程中的总读记录数。
记忆辅助: 带权路径长度可以理解为所有初始归并段的长度与其在归并树中深度的乘积之和。
Q: 最佳归并树的 I/O 次数如何计算？
A: I/O 次数 = 2 × WPL。
记忆辅助: 每次归并都需要读取所有参与归并的初始归并段，并将归并后的结果写回外存，因此 I/O 次数是 WPL 的两倍。
Q: 什么时候需要在最佳归并树中添加虚段？
A: 当初始归并段不足以构成一棵严格
记忆辅助: 添加虚段就像在搬运货物时添加一些空的箱子，这样可以使所有货物都能按照最佳方案进行搬运。