外部排序思维脑图思维导图
步骤，过程等相关内容讲解
树图思维导图提供 外部排序思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 外部排序思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：c67f727d5384557bdb75a735553ae307
思维导图大纲
外部排序思维导图模板大纲
原理
内存放不下，磁盘与内存以块为单位交换、排序、归并
败者树
作用：优化内部归并次数
例子
败者树，一图胜千言，注意，叶子其实是虚拟的
优化之处
k路归并，第一次构造败者树需要对比关键字k-1次
有了败者树，选出最小元素，至多需要对比关键字⌈logk⌉次（即层数）
置换-选择排序
作用：生成长度（可能）不等的归并段，减少初始归并段r的数量
过程及注意点
必须是选内存工作区WA中比MINNMAX大的记录中的最小值，放到归并段中
一旦选不出来，就可以新开一个归并段了
实际上，上述过程中在WA中选出MINIMAX记录的过程利用败者树实现
最佳归并树
作用：置换-选择排序得到的归并段大小不同，利用最佳归并树来组织这些归并段使I/O最少
理论
每个初始归并段对应一个叶子结点，归并段块数 = 叶子权值
归并过程中磁盘I/O次数 =归并树WPL * 2，利用了哈夫曼树
k叉归并的最佳归并树一定是严格k叉树，树中只有度为k、0的结点
构造
构造方法和哈夫曼树一毛一样，但是要先补充虚段
利用原理：树的边数 = 顶点数 - 1
（初始归并段数量 - 1）% (k - 1) = u
补充（k - 1） - u个权值为0的虚段
如果能整除就不要补充
例如
妈的终于要结束了？
步骤
生成r个初始归并段，如果有N个记录，内存工作区只能容纳L个记录，传统方法是对L个记录内部排序，共生成r = ⌈N/L⌉个初始归并段
如图利用两个缓冲区生成初始归并段
进行S趟k路归并
S = ⌈log r⌉ (以k为底)
k路归并过程
k个归并段的块读入k个输入缓冲区，若要并行处理：2k个输入，2个输出；k个缓冲区就要k路归并
如图，两个归并段分别放一块进去，归并后放到外存中新的位置
输出缓冲区满，写出外存；一旦输入缓冲区空，先放一块进来！
如图，这玩意知道就好，我看不能考
优化
时间开销 = 读写外存时间 + 内部排序时间 （生成初始归并段）+ 内部归并时间
读写磁盘次数 = 文件总块数 * 2（生成初始归并段） + 文件总块数 * 2 * 归并趟数
如果有r个段，每段有n个记录，利用传统的简单选择排序选出最小值，要比较(r - 1) * (nr - 1)次，因为r个段中选出1个最小值要r-1次，而一共有nr个段，只需要选nr-1次就能选出各值的排序
王道上的习题是这样，实际当然是错的了，当选了非常多，只剩最后r个记录时，选出最小值要r-1次，剩r-1个记录，此时要r-2次了，以此类推
优化主要减少归并趟数
增加归并路数k，进行多路平衡归并
多路平衡归并
代价：增加输入缓冲区、k个归并段要k-1次对比（k路归并要k-1次对比）
减少初始归并段数量r
r越长，数量越少，归并趟数越少
相关思维导图模板
树图思维导图提供 三国演义人物关系思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 三国演义人物关系思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：2c9d5602617c646a5afc7704c8dcb653
树图思维导图提供 蛋鸡通风思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 蛋鸡通风思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：e40a7e6bda85503c6e34cc3e3a910f4d
沪公网安备 31011502019485号
上海工商