内蒙古大学《算法与数据结构》课件第8章外部排序
57页1、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 R
2、2 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;/创建元素
3、数组创建元素数组 *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. 从所有排序
4、码比从所有排序码比Threshold大的元素中选择一个排序码最小的元大的元素中选择一个排序码最小的元素素rq作为阈值,其排序码存入作为阈值,其排序码存入Threshold。4. 将将rq元素写到输出文件元素写到输出文件FO中。中。5. 若若FI未读完,则从未读完,则从FI读入下一个元素。读入下一个元素。6. 重复重复(3)-(5),直到在,直到在WA中选不出排序码比中选不出排序码比Threshold大的元素为大的元素为止。此时,在输出文件止。此时,在输出文件FO中得到一个初始归并段,在它最后加中得到一个初始归并段,在它最后加一个归并段结束标志。一个归并段结束标志。7. 重复重复(2)-(6),重新开始选择和置换,产生新的初始归并段,直,重新开始选择和置换,产生新的初始归并段,直到输入文件到输入文件FI中所有元素选完为止。中所有元素选完为止。置换选择排序的操作过程:置换选择排序的操作过程:32若按每个初始归并段的长度与内存工作区的长度一致的若按每个初始归并段的长度与内存工作区的长度一致的方法,采用前面的内部排序的方式,在长度为方法,采用前面的内部排序的方式,在长度为3 3的工作的工作区中
5、进行排序,则区中进行排序,则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,
《内蒙古大学《算法与数据结构》课件第8章外部排序》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》课件第8章外部排序》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页