1 物料管理 EXST 1 Algorithms and Data Structures:EXSORT 1 、外存信息的存取 1 、外部排序： 内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。 外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘。特点为内存运行时 间短，内、外存进行交换需要时间长。减少 I/O 时间成为主要矛盾。 记录（ Record ）：数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记 录。原因起源于是在历史上研究管理应用和计算机科学的两部分人 员的习惯。 域（场）：记录中的每个数据项，称之为域（ Field ） 。 文件：记录的集合。 关键字：唯一标识记录的域，称之为关键字。 有序文件：文件根据关键字的大小。排成递增或递减的序列。 2 、基本术语： 3 、常用外存： 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度幔。

2 物料管理 EXST 2 Algorithms and Data Structures:EXSORT 1 、外存信息的存取 3 、常用外存： 带文件的组织的改进： 块 1 块 3块 3 块 2 IBG （ Inter Block Gap ）块间间隙 B.F （块因子） ＝ 一个物理记录包含逻辑记录的个数 带的利用率上升，如上例： 盘文件的位置：盘组号、柱面号、磁道号、块（扇区号） 盘文件的读写时间： T i/o = t seck + t la + n×t wm t seck ：找道时间 t la ：等待时间 t wm ：传输时间 / 字符， n 字符数。

3 物料管理 EXST 3 Algorithms and Data Structures:EXSORT 2 、外部排序的方法 1 、步骤： 生成合并段（ run ）：读入文件的部分记录到内存 － > 在内存中进行内部排序 － > 将排好序的这些记录写入外存，形成合并段 － > 再读入该文件 的下面的记录，往复进行，直至文件中的记录全部形成合并段 为止。 外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文 件。 平衡合并分类法：被合并的初始合并段均匀分布在 K 条磁带上，即分布在 T 1 、 T 2 、 …… T k 上。对这 K 条带进行合并，将生成的中间归并段分布在 T K+1 、 T K+2 、 …… T 2K 上。然后，循环往复，直至最后形成一个 单一的合并段为止。 7 、 15 、 19 8 、 11 、 、 23 、 31 5 、 12 归并趟数 : log k m where k 是路数； m 是初始合并段数。 如： m=6 ，那么 log 2 6 = 3 而 log 3 6 = 2 此外，还有一次生成所有合并段的时间。对 文件中的所有的记录全部读写一次。 每一趟归并时，对文件中的所有的记录都要全部读写一次。 K 大，趟数减 少，读写记录的总数将减少。但 K 大，需要的内存将越多。

4 物料管理 EXST 4 Algorithms and Data Structures:EXSORT 3 、多路平衡归并的实现 1 、带、盘的平衡多路归并的性质： log k m 趟 e.g: K > 2 时, 趟数将会减少。 m 个归并串。总共 n 个记录。 合并段 1 合并段 k 合并段 m-1 合并段 m 中间合并段 有序文件 层数： log k m +1 归并趟数： log k m 设从 k 个元素中挑选一个最小的元素需 ( k-1) 次比较。 每次比较耗费的时间代价为 : t mg ，那么在进行 k 路平衡归并时，总的比较时间耗费不会超过： log k m × ( k - 1 ) × ( n - 1 ) × t mg = log 2 m / log 2 k × ( k - 1 ) × ( n - 1 ) × t mg k log 2 m / log 2 k × ( k - 1 ) 大大

5 物料管理 EXST 5 Algorithms and Data Structures:EXSORT 3 、多路平衡归并的实现 1 、带、盘的平衡多路归并的性质： 改进：采用胜者树或者败者树，从 K 个元素中挑选一个最小的元素仅需 log 2 k 次比 较，这时总的时间耗费将下降： log k m × log 2 k × ( n - 1 ) × t mg ＝ log 2 m × ( n - 1 ) × t mg 输入缓冲区输入缓冲区 输出缓冲区输出缓冲区 注意：挑出冠军 需要进行 k-1 次 比较，此处需要 比较 3 次。

6 物料管理 EXST 6 Algorithms and Data Structures:EXSORT 3 、多路平衡归并的实现 2 、胜者树及其使用 胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的 结果，使得更快地挑出亚军、第三名 …… 。 决出第一名需比较： k - 1 次 决出第二名需比较： log 2 k 次 决出第三名需比较： log 2 k 次 结果：采用胜者树后，从 K 个元素中挑选一个最小的元素仅需 log 2 k 次比 较，这时总的时间耗费下降为： log k m × log 2 k × ( n - 1 ) × t mg ＝ log 2 m × ( n - 1 ) × t mg 有意思的是该结果和 k 无关，这是通过多用空间换来的。 改进：采用胜者树， K 个元素中最小的元素输出之后，从根结点到它的相应的叶子结 点路径上的结点都需要进行修改，为了加快程序运行的速度产生了败者树。

7 物料管理 EXST 7 Algorithms and Data Structures:EXSORT 、多路平衡归并的实现 3 、败者树及其使用 输入缓冲区输入缓冲区 输出缓冲区输出缓冲区 注意：挑出冠军 需要进行 k-1 次 比较，此处需要 比较 3 次。

8 物料管理 EXST 8 Algorithms and Data Structures:EXSORT 3 、多路平衡归并的实现 3 、败者树的程序实现 typedef int LoserTree[ k ]; typedef struct { KeyType key; } Exnode, External[ k+1 ]; Void K_Merge ( LoserTree &ls ， External & b) { for ( i = 0; i < k ; ++i ) input(b[i].key); CreateLoserTree(ls); while ( b[ls[0]].key != MAXKEY ) { q = ls[0]; // q 为当前最小关键字所在的 b[] 的下标地址，即相 // 应的归并段的输入缓冲区的序号 output(q); // 在相应归并段的输入缓冲区中，将包含该关键字的 // 记录写入输出缓冲区 input(b[q].key); // 从序号为 q 的输入归并段中读入下一个记录 // 的关键字 Adjust( ls, q ); } output( ls[0]); // 将含最大关键字 MAXKEY 的记录写至输出归并段 } } // K_Merge

9 物料管理 EXST 9 Algorithms and Data Structures:EXSORT 3 、多路平衡归并的实现 3 、败者树的程序实现 Void Adjust ( LoserTree & ls ， int s) { t = (s + k )/2; while ( t >0 ) { if (b[s].key > b[ls[t]].key) s ls[t]; t = t / 2; } // s 指示新的胜者的地址。 b[s].key<=b[ls[t]].key, 则 b[s] 仍是胜者。 ls[0] = s; } // Adjust Void CreateLoserTree ( LoserTree &ls ) { b[k].key = MINKEY; for ( i=0; i < k; ++i ) ls[i]=k; for ( i=k-1; k >= 0; - - i ) Adjust(ls,i); } // CreateLoserTree

10 物料管理 EXST 10 Algorithms and Data Structures:EXSORT 4 、置换 - 选择排序 1 、作用：产生尽可能长的初始归并段。在内存长度一定时，按照通常的排序方法，产生的 初始归并段的长度只能和内存长度相同，但采用本方法之后可以产生却可以生成 两倍内存长度的初始归并段（平均情况下）。 2 、实例： F1 ： 31 、 21 、 19 、 12 、 26 、 41 、 11 、 37 、 15 、 23 、 29 在带 1 上 F2 ： 输出磁带 2 假定使用的内存只有 3 个记录长，利用置换 - 选择分类法产生初始合并段。

11 物料管理 EXST 11 Algorithms and Data Structures:EXSORT 4 、置换 - 选择排序 实例的实现过程： F1 ： 31 、 21 、 19 、 12 、 26 、 41 、 11 、 37 、 15 、 23 、 29 在带 1 上 步数内存缓冲区内容（由 F1 输入）输出结果（至带 F2 ） 131 、 21 、 、 21 、 (12) 、 26 、 (12) 、 41 、 (12)31 5(11) 、 41 、 (12)41 6(11) 、 (37) 、 (12) ## 711 、 37 、 、 37 、 、 37 、 、 37 、 、 ## 第二个初始合并段 第一个初始合并段

12 物料管理 EXST 12 Algorithms and Data Structures:EXSORT 4 、置换 - 选择排序 3 、长度分析： 设内存可以存放 m 个记录，则首先从文件读入 m 记录到内存。这 m 个记录 肯定可以归入本初始合并段内。这样，必须从文件中读入 m 个记录。这 m 个 记录中平均有一半可以归入本合并段，一半归入下一合并段。 因此，合并段的平均长度为： m + m/2 + m/4 + ………… = 2m 所以，在平均情况下，合并段的平均长度为 2m 。 4 、程序实现： 可以用败者树的办法 加以实现。

13 物料管理 EXST 13 Algorithms and Data Structures:EXSORT 5 、最佳归并树 1 、最佳归并树 从外存读 5 个记录 写入外存 5 个记录 从外存读 67 个记录 写入外存 91 个记录 C. 写入外存 67 个记录 从外存读 91 个记录 总共读写外存 326 个记录 按照 HUFFMAN 树的思想，记录少的段最先合并。不够时增加虚段。如下例所示。 8 个初始归并段，记录数分别为 9 、 12 、 18 、 3 、 17 、 2 、 6 、 24 。

14 物料管理 EXST 14 Algorithms and Data Structures:EXSORT 5 、最佳归并树 1 、最佳归并树 按照 HUFFMAN 树的思想，记录少的段最先合并。不够时增加虚段。 虚段的段数的计算 : 解：在 K 路平衡归并时，它的归并树的模型是一棵度为 K 的树。在这棵树上的结点要么 是叶子，要么是具有 K 个儿子的内部结点。设具有 K 个儿子的内部结点共有 n k 个 。初始归并段的个数为 m 个。 设 n = n k + m ，故： 从结点出发的枝条，共计有： K × n k 根 若从进入结点结点的角度进行考虑，则共有： n k + m － 1 注意：没有枝条进入根结点。 所以， K × n k ＝ n k + m － 1 于是： n k ＝ ( m － 1 ) / ( K - 1) 这就意味着，若 ( m － 1 ) MOD ( K - 1) ＝ 0 ，无需增加虚段。否则，要增加虚段，其 数目为： ( K － 1 ) － ( m － 1 ) MOD ( K - 1) 。