内蒙古大学《算法与数据结构》课件第8章外部排序
1计算机专业本科主干基础课计算机专业本科主干基础课2第第8章章 外部排序外部排序8.1 外部排序的方法外部排序的方法 8.1.1 外部排序的方法外部排序的方法 8.1.2 多路平衡归并多路平衡归并 8.1.3 置换置换-选择排序选择排序8.2 最佳归并树最佳归并树38.1.1 外部排序的基本过程外部排序的基本过程待排序的记录数量巨大，无法一次将待排序的待排序的记录数量巨大，无法一次将待排序的记录全部调入内存，一部分数据只能驻留在外记录全部调入内存，一部分数据只能驻留在外存上（磁带、磁盘、存上（磁带、磁盘、CD-ROM）上。上。不能使用不能使用内部排序的方法进行排序。否则将引起频繁访内部排序的方法进行排序。否则将引起频繁访问外存。问外存。 8.1 外部排序的方法外部排序的方法456trw，tiotseektlatencytrw外排序主要的时间开销用在外排序主要的时间开销用在信息的内、外存交换信息的内、外存交换上，内存排序所需时间可以忽略不计，因此在外排上，内存排序所需时间可以忽略不计，因此在外排序的过程中主要考虑访问外存的次数。序的过程中主要考虑访问外存的次数。78910R1 750 R2 750 R3 750 R4 750 R5 750 R6 750初始归并段R12 1500 R34 1500 R56 1500R1234 3000R123456 4500第一趟归并结果 第二趟归并结果 第三趟归并结果 111213 tES = m*tis + d*tio + s*u*tmg其中：其中：tIS d tIO tmg14151617188.1.2 多路平衡归并多路平衡归并 (k-way Balanced merging)192021222324m1m0m230m49 20688123038 92220409090m0m1m3m4m3Ls0Ls1Ls2Ls3Ls4m3m3m1败者树败者树m3胜者胜者图图8.3 选出当前最小的关键字选出当前最小的关键字6m225m1m0m2 30m3 920168 16 8 12 30 38 9 22 20409090m0m1m2m3m4m3Ls0Ls1Ls2Ls3Ls4m4m4m1败者败者树树m3胜者胜者图图8.3 选出当前最小的关键字选出当前最小的关键字826void k_waymerge () r = new Elementk;/创建元素数组创建元素数组 *key = new intk+1; /创建外结点数组创建外结点数组 *Ls = new intk; /创建败者树数组创建败者树数组 for ( i = 0; i k; i+ ) /传送参选排序码传送参选排序码 InputRecord ( ri ); keyi = ri.key; 27for ( i = 0; i 0; t /= 2 ) / t/ t是是q q的双亲的双亲 if ( keyLst keyq) /败者记入败者记入Lst, Lst, 胜者记入胜者记入q q temp = q; q = Lst; Lst = temp; Ls0 = q; / adjust/ adjust 30输入文件输入文件FI内存工作区内存工作区WA输出文件输出文件Fo内存工作区可容纳内存工作区可容纳 w个记录个记录311. 从输入文件从输入文件FI中把中把 k 个元素读入内存工作区个元素读入内存工作区WA中，假设内存中，假设内存中存放元素的数组中存放元素的数组r可容纳的元素个数为可容纳的元素个数为 k 。2. 将无穷小存入将无穷小存入Threshold作为阈值。作为阈值。3. 从所有排序码比从所有排序码比Threshold大的元素中选择一个排序码最小的元大的元素中选择一个排序码最小的元素素rq作为阈值，其排序码存入作为阈值，其排序码存入Threshold。4. 将将rq元素写到输出文件元素写到输出文件FO中。中。5. 若若FI未读完，则从未读完，则从FI读入下一个元素。读入下一个元素。6. 重复重复(3)-(5)，直到在，直到在WA中选不出排序码比中选不出排序码比Threshold大的元素为大的元素为止。此时，在输出文件止。此时，在输出文件FO中得到一个初始归并段，在它最后加中得到一个初始归并段，在它最后加一个归并段结束标志。一个归并段结束标志。7. 重复重复(2)-(6)，重新开始选择和置换，产生新的初始归并段，直，重新开始选择和置换，产生新的初始归并段，直到输入文件到输入文件FI中所有元素选完为止。中所有元素选完为止。置换选择排序的操作过程：置换选择排序的操作过程：32若按每个初始归并段的长度与内存工作区的长度一致的若按每个初始归并段的长度与内存工作区的长度一致的方法，采用前面的内部排序的方式，在长度为方法，采用前面的内部排序的方式，在长度为3 3的工作的工作区中进行排序，则区中进行排序，则9 9个元素的序列个元素的序列27, 31, 15, 54, 20, 22,66, 27, 31, 15, 54, 20, 22,66, 42, 3942, 39，可分成，可分成3 3个初始归并段：个初始归并段： Run0 15, 27, 31 Run1 20, 22, 54 Run2 39, 42, 66 但采用上述置换但采用上述置换- -选择的方法，如图选择的方法，如图8.58.5可生成可生成2 2个长度不个长度不等的初始归并段：等的初始归并段： Run0 15, 27, 31, 54, 66 Run1 20, 22, 39, 42 33输入文件FI工作区WA输出文件FO段号与阈值66, 42,39, 22, 20, 54, 15, 31, 2739, 42, 66, 22, 20, 5415, 31, 2739, 42, 66, 22, 2054, 31, 27151 段 1539, 42, 66, 2254, 31, 2027, 151 段 2739, 42, 6654, 22, 2031，27，151 段 3139, 4266, 22, 2054,31,27,151 段543942, 22, 2066,54,31,27,151 段66343942, 22, 20,66,54,31,27,15加归并段结束标记3942, 22, 202段开始42, 22, 39202段2042, 3922，202段 224239，22，202段3942，39，22，202段 42，42，22，20加归并段结束标记35 在在WAWA中选择的过程可利用中选择的过程可利用“败者树败者树”来实现。来实现。 在利用败者树选取最小元素时，把败者树的叶在利用败者树选取最小元素时，把败者树的叶结点和非叶结点分开定义。假设败者树有结点和非叶结点分开定义。假设败者树有k k个个叶结点，用叶结点，用keykey存放，存放，key0key0到到keyk-1keyk-1存放各归存放各归并段当前参加归并的元素的排序码，并段当前参加归并的元素的排序码，keykkeyk是辅是辅助工作单元，在初始建立败者树时使用，存放助工作单元，在初始建立败者树时使用，存放一个最小的在各归并段中不可能出现的排序码：一个最小的在各归并段中不可能出现的排序码：- -MaxNumMaxNum。36 首先比较两个元素所在归并段的段号，段号小首先比较两个元素所在归并段的段号，段号小者为胜者，段号大者为败者；在归并段的段号者为胜者，段号大者为败者；在归并段的段号相同时，排序码小者为胜者，排序码大者为败相同时，排序码小者为胜者，排序码大者为败者。比较后把败者元素在元素数组者。比较后把败者元素在元素数组 r r 中的序号中的序号记入它的双亲结点中，把胜者元素在元素数组记入它的双亲结点中，把胜者元素在元素数组 r r 中的序号记入工作单元中的序号记入工作单元 s s 中，向更上一层进中，向更上一层进行比较，最后的胜者记入行比较，最后的胜者记入 Ls0Ls0中。中。 37383940412422222(11)阈值为阈值为39，选出，选出42 (12) 阈值为阈值为42，结束，结束43利用败者树生成初始归并段的算法：利用败者树生成初始归并段的算法：void generateRuns () r = new Elementk; int *key = new intk; /参选元素排序码数组参选元素排序码数组 int *rn = new intk; /参选元素段号数组参选元素段号数组 int *Ls = new intk; /败者树败者树 for (i = 0; i 0; i- ) /输入首批元素输入首批元素 if ( end of input ) rni = 2; /中途结束中途结束 else InputRecord ( ri ); /从缓冲区输入从缓冲区输入 keyi = ri.key; rni = 1; SelectMin ( key, rn, Ls, k, i, rq ); /调整调整 45利用败者树生成初始归并段的算法利用败者树生成初始归并段的算法q = Ls0; / q是最小元素在是最小元素在 r 中的序号中的序号int rq = 1; / rq的归并段段号的归并段段号int rc = 1; /当前归并段段号当前归并段段号int rmax = 1; /下次将要产生的归并段段号下次将要产生的归并段段号int Threshold = MaxNum; /阈值阈值while (1) /生成一个初始归并段生成一个初始归并段if ( rq != rc ) /当前最小元素归并段大当前最小元素归并段大Output end of run marker; /加段结束符加段结束符if ( rq rmax ) return; /处理结束处理结束 else rc = rq; /否则置当前段号等于否则置当前段号等于rq46利用败者树生成初始归并段的算法利用败者树生成初始归并段的算法OutputRecord ( rq ); / / rc rc=rqrq，输出，输出 Threshold = Keyq; /置新的阈值置新的阈值 if ( end of input ) rnq = rmax + 1; /虚设元素虚设元素 else /输入文件未读完输入文件未读完 InputRecord ( rq ); /读入到刚才位置读入到刚才位置 keyi = ri.key; if ( keyq 0; t /= 2 ) if ( rnLst rq | rnLst = rq & keyLst keyq ) /先比较段号再比较排序码先比较段号再比较排序码, , 小者为胜者小者为胜者 49在败者树中选择最小元素的算法：在败者树中选择最小元素的算法：int temp = q; q = Lst; Lst = temp; /败者记入败者记入Lst, Lst, 胜者记入胜者记入q q rq = rnq; Ls0 = q; /最后的胜者最后的胜者 / / SelectMinSelectMin508.2 最佳归并树最佳归并树 归并树是描述归并过程的归并树是描述归并过程的 m m 叉树。因为每一次叉树。因为每一次做做 m m 路归并都需要有路归并都需要有m m个归并段参加，因此，个归并段参加，因此，归并树是只有度为归并树是只有度为0 0和度为和度为 m m 的结点，称为正的结点，称为正则则 m m 叉树。叉树。例如：例如：设有设有1111个长度不等的初始归并段，其长个长度不等的初始归并段，其长度（元素个数）分别为度（元素个数）分别为 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 222, 4, 6, 8, 10, 12, 14, 16, 18, 20, 2251 对它们进行对它们进行 3 3 路归并时的归并树如图路归并时的归并树如图8.78.7所示。所示。在归并树中，各叶结点代表参加归并的各初始在归并树中，各叶结点代表参加归并的各初始归并段，叶结点上的权值即为该初始归并段中归并段，叶结点上的权值即为该初始归并段中的元素个数，根结点代表最终生成的归并段，的元素个数，根结点代表最终生
