第11章外排序 本章主要介绍下列内容(教材第三章) 1.排列问题(归入第10章中的回溯法一并介绍,此处略) 2.组合问题(同上处理) 3.外排序及广义斐波那契( FIBONACCI)数 4.传递闭包及 Warshall算法(学生参考《数据结构》部分的 Floyd算法自学) 课时分配:第3节讲授三个学时、上机三个学时 重点、难点:多遍归并外排序初始有序段的分配、虚段的添加算法 第三节外排序及广义斐波那契(F| BONACC|)数 本节主要按教材内容介绍,但在适当位置要补充以下内容 1.归并两个有序文件的细节讨论(见补充材料) 2.为形成尽可能长的初始归并段 (1)用具有一定技巧的内部排序方法(见补充材料) (2)置换选择排序(见《数据结构》外部排序一章) 3.在多遍归并(中途不分配)外排序中确定初始分布补充方法: K阶斐波那契序列定义为 0≤j<K-1 j=K K+1 j≥k K阶广义斐波那契序列定义为 0≤j≤K-1 K) j≥K 已知有序段总数x,确定K条带分布的步骤为: 第一步:找出使F≥x的最小j值 第二步:计算各带有序段数(等号右边为另法
第 11 章 外排序 本章主要介绍下列内容（教材第三章） 1. 排列问题（归入第 10 章中的回溯法一并介绍，此处略） 2. 组合问题（同上处理） 3. 外排序及广义斐波那契（FIBONACCI）数 4. 传递闭包及 Warshall 算法(学生参考《数据结构》部分的 Floyd 算法自学) 课时分配：第 3 节讲授三个学时、上机三个学时 重点、难点：多遍归并外排序初始有序段的分配、虚段的添加算法 第三节 外排序及广义斐波那契（FIBONACCI）数 本节主要按教材内容介绍，但在适当位置要补充以下内容： 1．归并两个有序文件的细节讨论（见补充材料） 2．为形成尽可能长的初始归并段： （1）用具有一定技巧的内部排序方法（见补充材料） （2）置换选择排序（见《数据结构》外部排序一章） 3．在多遍归并（中途不分配）外排序中确定初始分布补充方法： K 阶斐波那契序列定义为： ï î ï í ì + + + ³ = - £ < - = f - f - + f - j K j K j K f K j K j K K j K K j ( ) 1 ( ) 1 ( ) ( ) 1 1 0 0 1 L K 阶广义斐波那契序列定义为： ïî ï í ì + + + ³ £ £ - = F - F - + F - j K j K F K j K j k K j K K j ( ) 1 ( ) 1 ( ) ( ) 1 0 1 L 已知有序段总数 x，确定 K 条带分布的步骤为： 第一步：找出使 F x K j ³ ( ) 的最小 j 值； 第二步：计算各带有序段数（等号右边为另法）： ( ) ( ) 1 ( ) 1 ( ) 2 ( ) 1 ( ) 2 ( ) ( ) ( ) 2 ( ) 1 ( ) 1 K j K K K j K K j K j K K j K j K K j K j K t f f f t f t f f f f - - - + - - - - = + + + - = + + + L L 或
例:给定有序段总数253及六根磁带进行五路多遍归并,试为五根输入带确定有序段 分配数目 ①确定j 项≥253 2345678910 l111159173365129253497977 f5):000011248163161120236 1项 ②计算分布: f+f+(3+f4+3=31+16+8+4+2=61 12)=+fP3+f3+f=31+16+8+4=61-2=59 13=(+f2+f=31+16+8=59-4=55 f+f2=31+16=55-8=4713=(=31=47-16 4.P82有序段初始分配演示(算法过程) 举50个有序段的分配为例(但事先并不知道是50个有序段)
( ) 1 ( ) ( ) 2 ( ) 1 ( ) 1 K j K K K j K j K K t f t f f - - - - = = + 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 j K K K K j K K K t t f t t f t t f t t f - - - - - - - - - = - = - = - = - M 例：给定有序段总数 253 及六根磁带进行五路多遍归并，试为五根输入带确定有序段 分配数目。 ① 确定 j (5) Fj ： 1 1 1 1 1 5 9 17 33 65 129 253 497 977 0 1 2 3 4 5 6 7 8 9 10 11 f : 0 0 0 0 1 1 2 4 8 16 31 61 120 236 (5) j j-1 项 ② 计算分布： 31 16 55 8 47 31 47 16 31 16 8 59 4 55 31 16 8 4 61 2 59 31 16 8 4 2 61 (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 = + = + = - = = = = - = + + = + + = - = = + + + = + + + = - = = + + + + = + + + + = - - - - - - - - - - - - - - - j j j j j j j j j j j j j j j t f f t f t f f f t f f f f t f f f f f 4．P82 有序段初始分配演示（算法过程） 举 50 个有序段的分配为例（但事先并不知道是 50 个有序段） j 项≥253
A BC DE F 123456 两遍对应A值差即 实 为相应D值初值。 例如: 1+1:222210 J=1;l=1:000000D l:111110 对同一个j值 l11100 L:=2,B=1: 22210A后算 111100D先算 000000D的变化过程 L:=3B=2:4 0A共17 2|2|210D 000000D的变化过程 L=4B=4:887640A共33 43|3 00000 D变化过程 L=5B=8:1615141280A共65 实际为50 877640D共653=32余量为15 777640 D变化,最后使D中剩下15作为虚段(记 666640录)。这时,各带上的实际段数为 555540 1195,共50个 若实际为40个段,D的最后状态如何? 共25个,这时各带上的实际段数为 109640A P83归并算法执行过程演示 初始段为40个时,按教材P82分配算法得: 123456 实=A-D: 111096 刚好 40个实1=5 虚=D 5556 8个段! 25个虚
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 个实 l = 5 虚=D： 5 5 5 6 8 个段！ 25 个虚 实 A： 1 1 1 1 1 0 虚 D： 1 1 1 1 1 0 L:=2;B=1： 2 2 2 2 1 0 A 后算 1 1 1 1 0 0 D 先算 0 0 0 0 0 0 D的变化过程 J:=1; l =1： 0 0 0 0 0 0 A D L:=3;B=2： 4 4 4 3 2 0 A 共 17 2 2 2 1 1 0 D L:=4;B=4： 8 8 7 6 4 0 A 共 33 0 0 0 0 0 0 D的变化过程 两遍对应 A 值差即 为相应 D 值初值。 例如： 111100 ) :111110 1: 222210 l l - + 对同一个 j 值 4 4 3 3 2 0 D 0 0 0 0 0 0 D 变化过程 L:=5;B=8： 16 15 14 12 8 0 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
L=5时:且每个带上都有记录,故 归:D:444531 原A-D:未变 33 321 204 因A[5]即A[T-1]还不为0,故仍 repeat 0001 11109631 **0* 4444 1098622 987513 * 876404 共8 虚实均空 L=4时,先调整 A 446 370 0 460 540 600 pe原 12345 D400000 A487640 水*** 3210 ** 4444 654 3210 水*** 两者同时为空 L=3时,先调整 逻辑Tape123456 物理Tape561234 归:D0000 水* 0* 432 44320 332 1 L=2时,先调整 Repeat条件满足,停止循环,进入下遍 逻辑Tape123456 物理Tape456 归:D000000 A222210 水*水** 退出 repeat循环 L=1时,先调整,逻: 物 退出 repeat循环
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时,先调整 逻Tape123456 物Tape234561 归:D全0 此时,因L=0, while循环结束,全部记录都在2号物理磁带上,只有一个有序段 作排序结果输出。 第四节传递闭包及 Warshaw算法 先对上节内容再作小结以引入第三节课的讨论 对教材上所给出的多遍归并外排序算法,形成初始归并段有两种方法: 1.一个原始记录作为一个有序段 2.根据内存大小(假设可容纳n个记录),将原始记录n个为一组读入内存排序以形 成初始有序段(最后一个有序段可能不足n个记录),然后再按新构成的有序段总数进行分 配,必要时添加虚记录(一个为一段)以使有序段总数等于最接近的 Fibonacci 如何利用《数据结构》已有知识求关系的传递闭色(见教材P84-P88)。 三、课堂讨论及内部排序竞赛评奖。(参考程序见第8章内部排序的补充) /*一个简单的外排程序* #include #include #definen 1000 main i long int n, i,j, k, int min; FILE *f, char s[201 printf("source file name="): scanf("%s"s); I0; fopen(s, "I"); a=farmalloc(sizeof(int)(N+D) while(feof(f)(n++ fscanf(f, "%d", miniMin for(Fl; <=n, i++) printf("%8d" aiD) for(i=l;i<=n-1;++) for(=i+l<=n:j++)if(aljkalkkj; if (kl=i)(min=a[k]; a[k]=ai]; ai=min for(Fl; K<=n; 1++) printf("%8d" aiD) "n"); fclose(f) printf("target file name="); scanf("%s"S fopen(s, w") for(Fl; K<=n, i++) fprintf(f, %8d", aiD) fclose(f) carfree(a)
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 #include #include #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 #include #include #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)arMAX; else fscanf(a, %d", &ar) if (feof(b))brMAX; else fscanf(b, "%d", &br) while( feof(a)ll I feof(b) i 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); 3 if(ar==MAX & brbr & ar<MAX) fprintf(c, %8d%8d", br, ar); fclose(a), fclose(b), fclose(c)
/*一个简单的外部归并程序*/ #include #include #include #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 (arbr && ar<MAX) fprintf(c,"%8d%8d",br,ar); fclose(a);fclose(b);fclose(c); }
