数据结构——C语言描述习题及答案 耿国华

手工执行算法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=pivotkey) high--; [low]=[high];

while(low[high].key) [low]<->[high];

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

< 全文完 >