8.【外部排序】基本概念和方法 + 优化：【败者树】{减少关键字对比次数}、【置换-选择 排序】{减少初始归并段数量}、【最佳归并树】{谁先合并更快}

外部排序的基本概念和方法

外部排序：对大文件进行排序时，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。
因此需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。

1. 外部排序的步骤

① 根据内存缓冲区大小，将外存上的文件分成 r 个子文件，依次读入内存并利用内部排序方法