数据结构课件第八章

行一次内部归并所需时间。，u*tmg是对u个记 录进行内部归并所需的时间。
13
• 若总记录个数为 n，磁盘上每个页块可容纳 b 个记录， 内存缓冲区可容纳 i 个页块，则每个初始归并段长度 为 len = i * b，可生成 m = n/len 个初始归并段。
• 在做 2 路归并排序时, 第一趟从 m 个初始归并段得到
S*(u-1)*logk = logkm* (u-1) * logk
= logm * (u-1) * logk / logk = logm * (u-1)
20
• 从得到的式子可以看出总的排序码比较次数与k 无关，也就是说总的归并时间不会随k的增大而 增大。因此，只要内存空间允许，增大归并路数 k，将有效地减少归并树深度，从而减少读写磁 盘次数d，提高外部排序的速度。
11
一般地，若总元素个数为n，磁盘上每个页块可
容纳b个元素，内存缓冲区可容纳i个页块，则
每个初始归并段长度为len = i * b，可生成m =
n / len 个等长的初始归并段。在做2路归并排
序时，第一趟从m个初始归并段得到 m/2 个
归并段，以后各趟将从p (p >1) 个归并段得到
p / 2 个归并段，总归并趟数等于归并树的高
最后，段结束标志MaxNum（如图中的∞）升
入Ls[0]，排序完成，输出一个段结束标志。
23
Ls[0] m3 胜者
m3
Ls[1] m1 m3 Ls[2] m0 m3 Ls[4] 6 m3
6 16 ∞
m1 m2 Ls[3] 败者树 20 m1 20 m2 40 90 ∞
24
m4 8 m4 8 12 m0
图8.3 选出当前最小的关键字8
25
void k_waymerge () { r = new Element[k]; //创建元素数组
*key = new int[k+1];
*Ls = new int[k];
//创建外结点数组
//创建败者树数组
for ( i = 0; i < k; i++ ) { //传送参选排序码 InputRecord ( r[i] ); key[i] = r[i].key;
3


当记录以文件的形式存于磁盘上时，通常是按 物理块来存放的，物理块也叫做页块。每个页 块可存放若干个记录。操作系统是按页块对磁 盘信息进行读写。 磁盘通常是指由若干片磁盘组成的磁盘组, 各个 盘片安装在同一主轴上高速旋转。各个盘面上 半径相同的磁道构成了柱面。各盘面设置一个 读写磁头，它们装在同一活动臂上，活动臂可 以直接从一个柱面移到另一个柱面上。
}
26
for ( i = 0; i < k; i++) Ls[i] = k;
key[k] = -MaxNum;
for ( i = k-1; i; i-- )
//初始化
//调整形成败者树
adjust ( key, Ls, k, i );
while ( key[Ls[0]] != MaxNum ) { q = Ls[0];
9
两路归并排序的归并树
初始 归并段 第一趟 归并结果 第二趟 归并结果
R1 750 R2 750 R3 750 R4 750 R5 750 R6 750
R12
1500
R34
1500
R56
1500
R1234
3000
第三趟 归并结果
R123456
4500
10
输入缓冲区 1
输出缓冲区 输入缓冲区 2

步扩大归并段和减少归并段个数, 直到最后归 并成一个归并段(有序文件)为止。
基于磁盘进行的排序多使用归并排序方法。
7
• 例：设有一个包含4500个记录的输入文件。 现用一台其内存至多可容纳750个记录的计算 机对该文件进行排序。输入文件放在磁盘上，
磁盘每个页块可容纳250个记录, 这样全部记
录可存储在 4500 / 250＝18 个页块中。输出文
R1 第一趟 第二趟 R2 R123 R123456
18
R3
R4
R5 R345
R6
• 从上例看到好像k越大越好，但是从下面的讨
论中又看到单纯增加k将导致增加内部归并的
时间。例如对n个元素的文件，做内部k路归并 时，在k个元素中选择最小者，需要顺序比较 k-1次。每趟归并产生含有u个元素Baidu Nhomakorabea归并段时， 需要做(u-1)*(k-1)次比较，S 趟归并总共需要
• 失败者树:所谓败者树是一棵正则的完全二叉树， 其中每个叶结点存放当前参加比较的元素；每个 非叶结点存放其子女结点中排序码大的结点（即 败者），让二者中的小排序码去参加更上一层的 比较，当到达根结点时，根中仍存放其左、右子 中较大排序码，得到的小排序码就是目前序列的 最小排序码。 21
• 设有5个初始归并段，m0=[6，16，∞]、m1=[8，12， ∞]、m2=[30，38，∞]、m3=[9，22，∞]、m4=[20， 40，，90，∞]，其中∞为段结束标志MaxNum，开始 进行5路归并，每个归并段有一个排序码参加归并，每 个非叶结点中的段号为其左、右子女中的排序码大的 元素所在的段号（败者），数组Ls存放比较过程的结 果，如图8.3中，Ls[2]=0（即段m0中的排序码为当前 的败者），每个非叶结点向上分支上的段号表示比较 过程的胜者，它将参加更高一层结点的比较。
22
• Ls[0]存放最后的胜者。以后每选出一个当前排
序码最小的元素，将它送入输出缓冲区，然后
从它所在的归并段输入缓冲区中取出下一个参 加归并的元素，替换已经取走的最小元素，如 图8.4最左侧叶结点（排序码为16），再从叶结 点到根结点，沿某一特定路径进行调整，将下
一个排序码最小元素的归并段号调整到Ls[0]中。
16

归并趟数 S＝ logkm 增大归并路数k, 可减少归并趟数S, 从而减 少总读写磁盘次数d。

17
8.1.2 多路平衡归并 (k-way Balanced merging) • 从8.1式可以看出增大归并路数k可以减少归 并趟数S。图8.2给出对有6个初始归并段的文 件做3路平衡归并时的归并树，可以看出只 需要归并两趟。
序的过程中主要考虑访问外存的次数。
6
• 当记录以文件的形式存于磁盘上时，其排序过程主 要分为两个阶段：
(1)、建立用于外排序的内存缓冲区。根据它们 的大小将输入文件划分为若干段, 用某种内排序 方法对各段进行排序。经过排序的段叫做初始 归并段。当它们生成后就被写到外存中去。
(2)、把 (1) 生成的初始归并段加以归并, 逐

若把内存区域等份地分为 3 个缓冲区。其中 的两个为输入缓冲区, 一个为输出缓冲区, 可 以在内存中利用简单 2 路归并函数 merge( ) 实现 2 路归并。 首先, 从参加归并排序的两个输入归并段 R1 和 R2 中分别读入一块, 放在输入缓冲区1 和 输入缓冲区2 中。然后在内存中进行 2 路归 并，归并结果顺序存放到输出缓冲区中。
temp = q; q = Ls[t]; Ls[t] = temp; } Ls[0] = q; } // adjust
29
• 8.1.3 置换选择排序
输入文件FI
内存工作区WA
输出文件Fo
内存工作区可容纳 w个记录
30
置换选择排序的操作过程：
1. 从输入文件FI中把 k 个元素读入内存工作区WA中，假设内存 中存放元素的数组r可容纳的元素个数为 k 。 2. 将无穷小存入Threshold作为阈值。 3. 从所有排序码比Threshold大的元素中选择一个排序码最小的元 素r[q]作为阈值，其排序码存入Threshold。 4. 将r[q]元素写到输出文件FO中。 5. 若FI未读完，则从FI读入下一个元素。
度 logm。
12
• 根据2路归并树, 估计2路归并排序时间tES的
上界为：
tES = m*tis + d*tio + s*u*tmg 其中：m是初始归并段的个数；tIS 是对一个初 始归并段进行内排序的时间的均值； d 是读/写 外存页块的总次数；tIO 是对每一个页块进行读 /写的时间；S是归并趟数；tmg是对一个记录进
4
5
为了访问某一页块, 先寻找柱面: 活动臂使读写 磁头移到指定柱面上: 寻查(seek)。再根据盘面 号选择相应读写磁头, 等待指定页块转到读写磁 头下: 等待(latency)。传输一个字符的时间为 trw， 则在磁盘组上读写一个页块的时间：

tio＝tseek＋tlatency＋trw
外排序主要的时间开销用在信息的内、外存交换 上，内存排序所需时间可以忽略不计，因此在外排
//选归并段 //最小元素的段号
27
OutputRecord ( r[q] );
InputRecord ( r[q] ); key[q] = r[q].key; adjust ( key, Ls, k, q ); } Output end of run marker; } // k_waymerge
30
30 38 ∞
9
9
22 ∞
∞ 图8.3 选出当前最小的关键字6
胜者 Ls[0] m3 m3 Ls[1] m 1 m1 m4 Ls[2] m2 Ls[3] m0 m4 Ls[4] m 3 16 m3 16 ∞ 30 9 9 m1 22 ∞ 20 20 m2 40 90 ∞
败者 树
30 8 m 38 0 ∞ 8 m4 12 ∞
件也放在磁盘上, 用以存放归并结果。
8
• 由于内存中可用于排序的存储区域能容纳
750 个记录, 因此内存中恰好能存3个页块的
记录.
• 在外排序一开始, 把18块记录, 每3块一组, 读
入内存。利用某种内排序方法进行内排序,
形成初始归并段, 再写回外存。总共可得到6
个初始归并段。然后一趟一趟进行归并排序。
• 第一趟：36 tIO＋4500 tmg
•第二趟：归并两个具有 1500 个记录的归并段 R12和 R34
时间为：24 tIO＋3000 tmg •第三趟：将 R1234 和 R56 归并成一个归并段 • ＝ 36 tIO＋4500 tmg 合计 tES＝6 tIS＋132 tIO＋12000 tmg
的比较次数为：
• S*(u-1)*(k-1) = logkm * (u-1) * (k-1)= logm
* (u-1) * (k-1) / logk
19
• 在初始归并段个数m与元素个数u一定时， logm*(u1)是一个常数，而(k-1) / logk在k增大时趋于无穷大。 因此，增大归并路数k，会使得内部归并的时间增大。 当k增加到一定程度时，可能就抵消了由于减少读写磁 盘次数而赢得的时间。 • 当然我们还可以使用下面将要讲到的“败者树”的方 法从k个归并段中选最小者，当k较大时（k 6），用 败者树选出排序码最小的元素只需比较logk次（小于 k-1次）。此时，S趟归并总共需要的比较次数为：
m/2 个归并段，以后各趟将从 l (l >1) 个归并段得到
l /2 个归并段。总归并趟数为 log2m
14
• 对 4500 个记录进行排序的例子, 各种操作的
计算时间如下：
• 产生初始归并段：
• 读 18 个输入块, 内部排序6次, 写18个输出块 ＝6 tIS＋36 tIO
15
• 归并初始归并段 R1～R6：
//输出
//从该段补入元素
//调整
//输出段结束标志
28
自某叶结点key[q]到败者树根结点的调整算法
void adjust () { //q指示败者树的某叶结点key[q], 从该结点起到根结点进行 比较, 将最小key元素所在归并段的段号记入Ls[0]。k是叶 结点key[0..k-1]的个数。 for ( t = (k+q) / 2; t > 0; t /= 2 ) // t是q的双亲 if ( key[Ls[t]] < key[q]) {//败者记入Ls[t], 胜者记入q
计算机专业本科主干基础课
数据结构与算法
DATA STRUCTURE AND ARITHMETIC
1
第8章
外部排序
8.1 外部排序的方法
8.1.1 外部排序的方法 8.1.2 多路平衡归并 8.1.3 置换-选择排序
8.2 最佳归并树
2
8.1 外部排序的方法
8.1.1 外部排序的基本过程
待排序的记录数量巨大，无法一次将待排序的 记录全部调入内存，一部分数据只能驻留在外 存上（磁带、磁盘、CD-ROM）上。不能使用 内部排序的方法进行排序。否则将引起频繁访 问外存。