数据结构-_外部排序.pptVIP

1、外存信息的存取 1、外存信息的存取 2、外部排序的方法 3、多路平衡归并的实现 3、多路平衡归并的实现 3、多路平衡归并的实现 3、多路平衡归并的实现 3、多路平衡归并的实现 3、多路平衡归并的实现 4、置换-选择排序 4、置换-选择排序 4、置换-选择排序 5、最佳归并树 5、最佳归并树 * * 物料管理 EXST * * * Algorithms and DataStructures:EXSORT 1、外部排序： 内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。 外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘。特点为内存运行时 间短，内、外存进行交换需要时间长。减少 I/O 时间成为主要矛盾。 记录（Record）：数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记 录。原因起源于是在历史上研究管理应用和计算机科学的两部分人 员的习惯。 域（场）：记录中的每个数据项，称之为域（Field） 。 文件：记录的集合。 关键字：唯一标识记录的域，称之为关键字。 有序文件：文件根据关键字的大小。排成递增或递减的序列。 2、基本术语： 3、常用外存： 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度幔。 3、常用外存： 带文件的组织的改进： 块 1 块 3 块 2 IBG（Inter Block Gap）块间间隙 B.F（块因子） ＝ 一个物理记录包含逻辑记录的个数 带的利用率上升，如上例： 盘文件的位置：盘组号、柱面号、磁道号、块（扇区号） 盘文件的读写时间：T i/o = tseck + tla + n×twm tseck ：找道时间 tla ：等待时间 twm ：传输时间/ 字符，n 字符数。 1、步骤： 生成合并段（run）：读入文件的部分记录到内存 － 在内存中进行内部排序 － 将排好序的这些记录写入外存，形成合并段 － 再读入该文件 的下面的记录，往复进行，直至文件中的记录全部形成合并段 为止。 外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文 件。 平衡合并分类法：被合并的初始合并段均匀分布在 K 条磁带上，即分布在 T1、T2、 …… Tk 上。对这 K 条带进行合并，将生成的中间归并段分布在 TK+1、 TK+2 、…… T2K 上。然后，循环往复，直至最后形成一个 单一的合并段为止。 7、15、19 8、11、13 16、23、31 5、12 归并趟数: logkm where k 是路数；m 是初始合并段数。 如：m=6，那么 log26 = 3 而 log36 = 2 此外，还有一次生成所有合并段的时间。对 文件中的所有的记录全部读写一次。 每一趟归并时，对文件中的所有的记录都要全部读写一次。K 大，趟数减 少，读写记录的总数将减少。但 K 大，需要的内存将越多。 1、带、盘的平衡多路归并的性质： logkm 趟 e.g: K 2 时, 趟数将会减少。m 个归并串。总共 n 个记录。 合并段 1 合并段 k 合并段 m-1 合并段 m 中间合并段 中间合并段 有序文件 层数： logkm +1 归并趟数： logkm 设从 k 个元素中挑选一个最小的元素需 ( k-1) 次比较。 每次比较耗费的时间代价为: tmg，那么在进行 k 路平衡归并时，总的比较时间耗费不会超过： logkm × ( k - 1 ) × ( n - 1 ) × tmg = log2m / log2k × ( k - 1 ) × ( n - 1 ) × tmg k log2m / log2k × ( k - 1 ) 大