5)二路外排序 6)选择树(贏者树和败者树 4重点和难点 重点和难点主要包括: 1)置换排序和多路归并排序的特点; 2)多路平衡归并等外排序方法及败者树构造方法; 3)最佳归并树的建立方法。 5授课提示 理解文件结构及其管理方法,把握外排序的基本过程及优化技巧,在实践中 进行应用。 在讲授重点和难点内容的过程中,需要重点关注的有 1)置换排序 置换选择排序的核心思想是利用最小值堆(或最大值堆)对数据进行处理。 每输出一个最小值(或最大值),就从缓冲区中读入下一个数。 置换选择算法的效果:如果堆的大小是M,一个顺串的最小长度就是M个 记录,至少原来在堆中的那些记录将成为顺串的一部分。最好的情况下,例如输 入已经被排序,有可能一次就把整个文件生成为一个顺串 讲解过程除了讲解清楚基本排序过程外,还要帮助分析置换排序的性能。 2)多路归并排序 基本原理:把多个顺串加以合并成为一个顺串,即形成一个已排序的文件。 在K路归并中,最直接的方法就是作K-1次比较来找出所要的记录,但这样 做花的代价较大,采用选择树的方法来实现K路归并。选择树是完全二叉树, 有两种类型:贏者树和败者树 (1)赢者树 在利用选择树进行归并时,将两个子女结点中的赢者(关键码值较小者)上 升到父结点,称这种选择树为赢者树。因此,根结点是树中的最终赢者的索引, 即为下一个要输出的记录结点5) 二路外排序 6) 选择树（赢者树和败者树） 4 重点和难点 重点和难点主要包括： 1) 置换排序和多路归并排序的特点； 2) 多路平衡归并等外排序方法及败者树构造方法； 3) 最佳归并树的建立方法。 5 授课提示 理解文件结构及其管理方法，把握外排序的基本过程及优化技巧，在实践中 进行应用。 在讲授重点和难点内容的过程中，需要重点关注的有： 1) 置换排序 置换选择排序的核心思想是利用最小值堆（或最大值堆）对数据进行处理。 每输出一个最小值（或最大值），就从缓冲区中读入下一个数。 置换选择算法的效果：如果堆的大小是 M，一个顺串的最小长度就是 M 个 记录，至少原来在堆中的那些记录将成为顺串的一部分。最好的情况下，例如输 入已经被排序，有可能一次就把整个文件生成为一个顺串。 讲解过程除了讲解清楚基本排序过程外，还要帮助分析置换排序的性能。 2) 多路归并排序 基本原理：把多个顺串加以合并成为一个顺串，即形成一个已排序的文件。 在 K 路归并中，最直接的方法就是作 K-1 次比较来找出所要的记录，但这样 做花的代价较大，采用选择树的方法来实现 K 路归并。选择树是完全二叉树， 有两种类型：赢者树和败者树。 （1）赢者树 在利用选择树进行归并时，将两个子女结点中的赢者（关键码值较小者）上 升到父结点，称这种选择树为赢者树。因此，根结点是树中的最终赢者的索引， 即为下一个要输出的记录结点