发布时间 : 星期六 文章数据结构——C语言描述习题及答案 耿国华更新完毕开始阅读22574af95627a5e9856a561252d380eb629423b0
手工执行算法k-merge，追踪败者树的变化过程。假设初始归并段如下：
（10，15，16，20，31，39，+∞）； （9，18，20，25，36，48，+∞）； （20，22，40，50，67，79，+∞）； （6，15，25，34，42，46，+∞）； （12，37，48，55，+∞）； （84，95，+∞）；
已知某文件经过置换选择排序之后，得到长度分别为47，9，39，18，4，12，23和7的八
个初始归并段。试用3路平衡归并设计一个读写外存次数最少的归并方案，并求出读写外存的次数。
第十章 外部排序
void Insert_Sort1(SqList &L) {ey>[i+1].key) {
[k+1].key=[i].key; ey>[i].key;++j)
[j-1].key=[j].key; ey=[k+1].key; ey>=x) ey;j--) d[j+1]=d[j]; d[j+1]=[i].key; final++; }
else ey;j++) d[j-1]=d[j];
d[(j-2)%MAXSIZE+1]=[i].key; first=(first-2)%MAXSIZE+1; ey=d[i]; }ey=0;[0].next=1; [1].next=0; ey;
while[[p].next].key q=[p].next; [p].next=i; [i].next=q; }ext; for(i=1;i<;i++) ext; q=[p].next; if(p!=i) { [p]<->[i]; [i].next=p; } p=q; }ey; while(low while(low while(low else ey>[low+1].key) [low]<->[low+1]; if[low+1].key>[high].key) [low+1]<->[high]; if[low].key>[low+1].key) [low]<->[low+1]; } }中,j表示当前元素;i以前的元素全部为红色;k以后的元素全部为蓝色.这样,就可以根据j的颜色,把其交换到序列的前部或者后部. void LinkedList_Select_Sort(LinkedList &L) {ey>[k].key) [j]<->[k]; j=k; } }ey<[j+1].key) j++; if(j }初始堆时,i的上限从3开始(为什么?) 2.调整堆的时候,要从结点的三个孩子结点中选择最大的那一个,最左边的孩子的序号的计算公式为j=3*s-1(为什么?) void Merge_Sort(int a[ ],int n) {如说,\把第一个序列划分为两个子序列,使其中的第一个子序列含有s1个记录,0<=s1 void Hash_Sort(int a[ ]) {t++; else if(a[j] min_dif=abs(b[0].gt-b[0].lt); for(i=0;i min=0; for(j=0;j if(c[j] typedef enum {0,1,2,3,4,5,6,7,8,9} digit; 因为如此,它才能够被用来实现基数排序. typedef struct { int key; int pos; } Shadow; ey=b[i].key; d[i].pos=i; } for(i=n-1,change=1;i>1&&change;i--) ey>d[j+1].key) { d[j]<->d[j+1]; change=1; } }os]; }//Shadow_Sort < 全文完 >