外部排序思维脑图思维导图

生杀予夺

2023-12-17

浏览量: 13

外部排序

排序原理

排序优化

步骤，过程等相关内容讲解

树图思维导图提供《外部排序思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《外部排序思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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越长，数量越少，归并趟数越少

1107文家市玉萍思维导图

U245265618

0.96

树图思维导图提供《1107文家市玉萍思维导图》在线思维导图免费制作，点击“编辑”按钮，可对《1107文家市玉萍思维导图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：ed943ef641f6dc874860eb6095857ed6

种子思维脑图思维导图

U282195478

2.62

树图思维导图提供《种子思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《种子思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：86f8307a40ea24607c6c79354e09377f

思维导图模板

IT互联网

产品结构

正文

相似思维导图模版

思维导图模版推荐

首页

我的文件

我的团队

个人中心

﻿外部排序思维脑图思维导图

思维导图大纲

相关思维导图模版

﻿原理

﻿败者树

﻿置换-选择排序

﻿最佳归并树

﻿步骤

﻿k路归并过程

﻿优化