第11章 外排序
本章主要介绍下列内容（教材第三章）
1. 排列问题（归入第10章中的回溯法一并介绍，此处略）
2. 组合问题（同上处理）
3. 外排序及广义斐波那契（FIBONACCI）数
4. 传递闭包及Warshall算法(学生参考《数据结构》部分的Floyd算法自学)
课时分配：第3节讲授三个学时、上机三个学时
重点、难点：多遍归并外排序初始有序段的分配、虚段的添加算法
第三节 外排序及广义斐波那契（FIBONACCI）数
本节主要按教材内容介绍，但在适当位置要补充以下内容：
1．归并两个有序文件的细节讨论（见补充材料）
2．为形成尽可能长的初始归并段：
（1）用具有一定技巧的内部排序方法（见补充材料）
（2）置换选择排序（见《数据结构》外部排序一章）
3．在多遍归并（中途不分配）外排序中确定初始分布补充方法：
K阶斐波那契序列定义为：
??
??
?
≥+++
?=
?<≤
=
?+?? Kjfff
Kj
Kj
f
K
j
K
Kj
K
Kj
K
j
)(
1
)(
1
)(
)( 11
100
L
K阶广义斐波那契序列定义为：
??
???
≥+++
?≤≤=
?+?? KjFFF
KjF
K
j
K
kj
K
Kj
K
j )(
1
)(
1
)(
)( 101
L
已知有序段总数x，确定K条带分布的步骤为：
第一步：找出使 xF Kj ≥)( 的最小j值；
第二步：计算各带有序段数（等号右边为另法）：
)()(
1
)(
1
)(
2
)(
1
)(
2
)()()(
2
)(
1
)(
1
K
Kj
KK
Kj
K
j
K
j
K
K
j
K
Kj
K
j
K
j
K
ftffft
fffft
?+???
???
?+++=
+++=
L
L 或
)(
1
)(
)(
2
)(
1
)(
1
K
j
K
K
K
j
K
j
K
K
ft
fft
?
???
=
+=
M
)(
2
)(
1
)(
)(
3
)(
2
)(
1
)(
)2(
)(
3
)(
4
)(
)1(
)(
2
)(
3
K
j
K
K
K
K
K
j
K
K
K
K
K
Kj
KK
K
Kj
KK
ftt
ftt
ftt
ftt
??
???
??
??
?=
?=
?=
?=
M
例：给定有序段总数 253 及六根磁带进行五路多遍归并，试为五根输入带确定有序段
分配数目。
① 确定j
)5(
jF ：
9774972531296533179511111
11109876543210
62312061 31 16 8 4 2 1 1 0 0 0 0:f )5(j
j-1项
② 计算分布：
164731478551631
5545981631
59261481631
612481631
)5(
1
)5(
5
)5(
2
)5(
1
)5(
4
)5(
3
)5(
2
)5(
1
)5(
3
)5(
4
)5(
3
)5(
2
)5(
1
)5(
2
)5(
5
)5(
4
)5(
3
)5(
2
)5(
1
)5(
1
?====?=+=+=
=?=++=++=
=?=+++=+++=
=++++=++++=
???
???
????
?????
jjj
jjj
jjjj
jjjjj
ftfft
ffft
fffft
ffffft
4．P82 有序段初始分配演示（算法过程）
举50个有序段的分配为例（但事先并不知道是50个有序段）
j项≥253
A B C D E F
1 2 3 4 5 6
若实际为40个段，D的最后状态如何？
共25个，这时各带上的实际段数为：
P83 归并算法执行过程演示
初始段为40个时，按教材P82分配算法得：
1 2 3 4 5 6
实=A-D： 11 10 9 6 刚好 40个实 5=l
虚=D： 5 5 5 6 8个段！ 25个虚
1 1 1 1 1 0 实 A：
1 1 1 1 1 0 虚 D：
2 2 2 2 1 0 L:=2;B=1： A 后算
1 1 1 1 0 0 D 先算
0 0 0 0 0 0 D的变化过程
0 0 0 0 0 0 J:=1; l =1：
A
D
4 4 4 3 2 0 L:=3;B=2： A 共17
2 2 2 1 1 0 D
8 8 7 6 4 0 L:=4;B=4： A 共33
0 0 0 0 0 0 D的变化过程
两遍对应 A 值差即
为相应D值初值。
例如：
111100
111110:)
222210:1
l
l
?
+
对同一个j值
4 4 3 3 2 0 D
0 0 0 0 0 0 D变化过程
16 15 14 12 8 0 L:=5;B=8： A 共65
8 7 7 6 4 0 D共65-33=32
7
6
5
4
3
7
6
5
4
3
7
6
5
4
3
6
6
5
4
3
4
4
4
4
3
0
0
0
0
0
D变化，最后使D中剩下15作为虚段（记
录）。这时，各带上的实际段数为
13 12 11 9 5，共50个。
5 5 5 6 4 0 D
11 10 9 6 4 0 A
实际为50
余量为15
4
4
Tape 1 2 3 4 5 6
L=5时：且每个带上都有记录，故：
归：D： 4 4 4 5 3 1 原A-D：未变
3 3 3 4 2 2
2 2 2 3 1 3
1 1 1 2 0 4 11 10 9 6 4 0
因A[5]即A[T-1]还不为0，故仍repeat：
0 0 0 1 * 4 11 10 9 6 3 1
* * * 0 * 4 10 9 8 6 2 2
* * * * * 4 9 8 7 5 1 3
* * * * * 4 8 7 6 4 0 4
L=4时，先调整：
1 2 3 4 5 6
A 4 8 7 6 4 0
D 4 0 0 0 0 0
Tape原： 6 1 2 3 4 5
归： D 4 0 0 0 0 0 A 4 8 7 6 4 0
3 * * * * * 4 7 6 5 3 1
2 * * * * * 4 6 5 4 2 2
1 * * * * * 4 5 4 3 1 3
0 * * * * * 4 4 3 2 0 4
L=3时，先调整
逻辑Tape 1 2 3 4 5 6
物理Tape 5 6 1 2 3 4
归：D 0 0 0 0 0 0 A 4 4 4 3 2 0
* * * * * * 3 3 3 2 1 1
* * * * * * 2 2 2 1 0 2
L=2时，先调整
逻辑Tape 1 2 3 4 5 6
物理Tape 4 5 6 1 2 3
归：D 0 0 0 0 0 0 A 2 2 2 2 1 0
* * * * * * 1 1 1 1 0 1
L=1时，先调整，逻：1 2 3 4 5 6 物：3 4 5 6 1 2
归：D 0 0 0 0 0 0 A 1 1 1 1 1 0
* * * * * * 0 0 0 0 0 1
共8个段
虚实均空
两者同时为空
Repeat条件满足，停止循环，进入下遍。
退出repeat循环
退出repeat循环
L=0时，先调整：
逻Tape 1 2 3 4 5 6
物Tape 2 3 4 5 6 1
归：D全0 A 1 0 0 0 0 0
此时，因L=0，while循环结束，全部记录都在2号物理磁带上，只有一个有序段，可
作排序结果输出。
第四节 传递闭包及Warshall算法
一、先对上节内容再作小结以引入第三节课的讨论。
对教材上所给出的多遍归并外排序算法，形成初始归并段有两种方法：
1．一个原始记录作为一个有序段；
2．根据内存大小（假设可容纳n个记录），将原始记录n个为一组读入内存排序以形
成初始有序段（最后一个有序段可能不足n个记录）， 然 后 再 按新 构 成 的有序段总数进行分
配，必要时添加虚记录（一个为一段）以使有序段总数等于最接近的FeiboNacci数。
二、如何利用《数据结构》已有知识求关系的传递闭色（见教材P84-P88）。
三、课堂讨论及内部排序竞赛评奖。（参考程序见第8章内部排序的补充）
/*一个简单的外排程序*/
#include<stdio.h>
#include<stdlib.h>
#include<alloc.h>
#define N 1000
int huge *a;
main()
{ long int n,i,j,k;int min;FILE *f;char s[20];
printf("source file name=");scanf("%s",s);
n=0;f=fopen(s,"r");
a=farmalloc(sizeof(int)*(N+1));
while (!feof(f)) {n++;fscanf(f,"%d",&min);a[n]=min;}
for (i=1;i<=n;i++) printf("%8d",a[i]);
printf("\n");
for (i=1;i<=n-1;i++)
{k=i;
for (j=i+1;j<=n;j++) if (a[j]<a[k]) k=j;
if (k!=i) {min=a[k];a[k]=a[i];a[i]=min;}
}
for (i=1;i<=n;i++) printf("%8d",a[i]);
printf("\n");
fclose(f);
printf("target file name=");scanf("%s",s);
f=fopen(s,"w");
for (i=1;i<=n;i++) fprintf(f,"%8d",a[i]);
fclose(f);
farfree(a);}
/*一个简单的外部归并程序*/
#include<stdio.h>
#include<stdlib.h>
#include<alloc.h>
#define MAX 32767
int huge *a;
main()
{
int ar,br,cr;FILE *a,*b,*c;char s[20];
printf("source file name 1 :");scanf("%s",s);a=fopen(s,"r");
printf("source file name 2 :");scanf("%s",s);b=fopen(s,"r");
printf("target file name :");scanf("%s",s);c=fopen(s,"w");
if (feof(a)) ar=MAX;else fscanf(a,"%d",&ar);
if (feof(b)) br=MAX;else fscanf(b,"%d",&br);
while (!feof(a) || !feof(b))
{ if (ar<=br)
{ fprintf(c,"%8d",ar);if (feof(a)) ar=MAX;else fscanf(a,"%d",&ar);}
else { fprintf(c,"%8d",br);if (feof(b)) br=MAX;else fscanf(b,"%d",&br);}
}
if (ar==MAX && br<MAX) fprintf(c,"%8d",br);
if (br==MAX && ar<MAX) fprintf(c,"%8d",ar);
if (ar<=br && br<MAX) fprintf(c,"%8d%8d",ar,br);
if (ar>br && ar<MAX) fprintf(c,"%8d%8d",br,ar);
fclose(a);fclose(b);fclose(c);
}
| 课件名称： | 西华师范大学：算法与程序设计（推荐下载） |
| 课件分类： | 计算机 |
| 课件类型： | 教学课件 |
| 文件大小： | 19.44MB |
| 下载次数： | 9 |
| 评论次数： | 7 |
| 用户评分： | 8 |
- 48. 西华师范大学：算法与程序设计（推荐下载）：3
- 49. 西华师范大学：算法与程序设计（推荐下载）：4
- 50. 西华师范大学：算法与程序设计（推荐下载）：5
- 51. 西华师范大学：算法与程序设计（推荐下载）：6
- 52. 西华师范大学：算法与程序设计（推荐下载）：7
- 53. 西华师范大学：算法与程序设计（推荐下载）：8
- 54. 西华师范大学：算法与程序设计（推荐下载）：9
- 55. 西华师范大学：算法与程序设计（推荐下载）：ch1
- 56. 西华师范大学：算法与程序设计（推荐下载）：ch10
- 57. 西华师范大学：算法与程序设计（推荐下载）：ch11
- 58. 西华师范大学：算法与程序设计（推荐下载）：ch12
- 59. 西华师范大学：算法与程序设计（推荐下载）：ch2
- 60. 西华师范大学：算法与程序设计（推荐下载）：ch3
- 61. 西华师范大学：算法与程序设计（推荐下载）：ch4
- 62. 西华师范大学：算法与程序设计（推荐下载）：ch5
- 63. 西华师范大学：算法与程序设计（推荐下载）：ch6
- 64. 西华师范大学：算法与程序设计（推荐下载）：ch7
- 65. 西华师范大学：算法与程序设计（推荐下载）：ch8
- 66. 西华师范大学：算法与程序设计（推荐下载）：ch9(1)
