第十章排序参考答案

int index (RecType R[],int l,h,datatype key) { int i=l,j=h; while (i

{ while (i<=j && R[j].key>key) j--; if (R[j].key==key) return j; while (i<=j && R[i].key

printf(“Not find”) ; return 0; }//index

11. (1) [题目分析]从第n个记录开始依次与其双亲(n/2)比较,若大于双亲则交换,继而与其双亲的双亲比较,以此类推直到根为止。

void sift(RecType R[],int n)

{ //假设 R[1..n-1]是大堆,本算法把R[1..n]调成大堆 j=n; R[0]=R[j]; for (i=n/2;i>=1;i=i/2)

if (R[0].key>R[i].key){ R[j]=R[i];j=i;} else break; R[j]=R[0];

}//sift

(2)void HeapBuilder(RecType R[],int n) { for (i=2;i<=n;i++) sift (R,i); } 12. void sort (RecType K[],int n) { for (i=1;i<=n;i++) T[i]=i; for (i=1;i

for (j=1;j<=n-i;j++)

if (K[T[j]]>K[T[j+1]]) {t=T[j];T[j]=T[j+1];T[j+1]=t;}

}//sort

[算法讨论] 上述算法得到辅助地址表,T[i]的值是排序后K的第i个记录,要使序列K有序,则要按T再物理地重排K的各记录。算法如下:

void Rearrange(RecType K[],int T[],n)

//对有n个记录的序列K,按其辅助地址表T进行物理非递减排序 {for(i=1;i<=n;i++) if (T[i]!=i)

{j=i; rc=K[i]; //暂存记录K[i]

while (T[j]!=i) //调整K[T[j]]到T[j]=i为止 {m=T[j]; K[j]=K[m]; T[j]=j; j=m;} K[j]=rc; T[j]=j; //记录R[i]到位 }//if

}//Rearrange

13. (1) 堆排序是对树型选择排序的改进,克服了树型选择排序的缺点,其定义在前面已多次谈到,请参见上面“四、应用题”的43题和45题(4)。“筛选”是堆排序的基础算法。由于堆可以看作具有n个结点的完全二叉树,建堆过程是从待排序序列第一个非终端结点?n/2?开始,直到根结点,进

行“筛选”的过程。堆建成后,即可选得一个关键字最大或最小的记录。然后堆顶元素与序列中最后一个元素交换,再将序列中前n-1记录重新调整为堆,可选得一个关键字次大或次小的记录。依次类推,则可得到元素的有序序列。

(2) void Sift(RecType R[],int i,int m)

{ //假设R[i+1..m]中各元素满足堆的定义,本算法调整R[i]使序列R[i..m]中各元素满足堆的性质

R[0]=R[i];

for(j=2*i; j<=m; j*=2)

{ if(j

if(R[0].key

}//for

R[i]=R[0]; }//Sift

void HeapSort(RecType R[],int n) { //对记录序列R[1..n]进行堆排序。 for(i=n/2;i>0;i--) Sift(R,i,n);

for(i=n;i>1;i--){ R[1]<-->R[i]; Sift(R,1,i-1);}//for }//HeapSort

(3)堆排序的时间主要由建堆和筛选两部分时间开销构成。对深度为h的堆,“筛选”所需进行的关键字比较的次数至多为2(h-1);对n个关键字,建成深度为h(=?log2n?+1)的堆,所需进行的关键字比较的次数至多C (n),它满足下式:

11i?1C(n)??2i?h?1h?1?2(h?1)??2i?h?1h?3i?(h?1)

?2?2h?2?2?22?3???2?(h?1) ???(h?1)/2h-1?2(1/2?2/2hh?3/2(log23)

?2?2?2?2n)?1?4n

调整“堆顶”n-1次,总共进行的关键字比较的次数不超过:2(?log2(n-1)?+ ?log2(n-2)?+ ?+log22)<2n(?log2n?)因此,堆排序的时间复杂度为O(nlog2n)。 14. PROC LinkedListSelectSort( head: pointer);

//本算法一趟找出一个关键字最小的结点,其数据和当前结点进行交换;若要交换指针,则须记下 //当前结点和最小结点的前驱指针

p:=head↑.next; WHILE p<>NIL DO

[q:=p↑.next; r:=p; //设r是指向关键字最小的结点的指针 WHILE NIL DO

[IF q↑.data

q:=q↑.next; ]

IF r<>p THEN r↑.data<-->p↑.data p:=p↑.next; ]

ENDP;

15. void QuickSort(rectype r[n+1]; int n) // 对r[1..n]进行快速排序的非递归算法

{typedef struct

{ int low,high; }node

node s[n+1];//栈,容量足够大

int quickpass(rectype r[],int,int); // 函数声明 int top=1; s[top].low=1; s[top].high=n; while (top>0)

{ss=s[top].low; tt=s[top].high; top--; if (ss

{k=quickpass(r,ss,tt);

if (k-ss>1) {s[++top].low=ss; s[top].high=k-1;}

if (tt-k>1) {s[++top].low=k+1; s[top].high=tt;} }

} // 算法结束

int quickpass(rectype r[];int s,t) {i=s; j=t; rp=r[i]; x=r[i].key; while (i

{while (i

while (i=r[j].key) i++; if (i

r[i]=rp;

return (i);

} // 一次划分算法结束

[算法讨论]可对以上算法进行两点改进:一是在一次划分后,先处理较短部分,较长的子序列进栈;二是用“三者取中法”改善快速排序在最坏情况下的性能。下面是部分语句片段:

int top=1; s[top].low=1; s[top].high=n;

ss=s[top].low; tt=s[top].high; top--; flag=true; while (flag || top>0)

{k=quickpass(r,ss,tt);

if (k-ss>tt-k) // 一趟排序后分割成左右两部分

{if (k-ss>1) // 左部子序列长度大于右部,左部进栈 {s[++top].low=ss; s[top].high=k-1; } if (tt-k>1) ss=k+1; // 右部短的直接处理

else flag=false; // 右部处理完,需退栈

}

else if (tt-k>1) //右部子序列长度大于左部,右部进栈 {s[++top].low=k+1; s[top].high=tt; }

if (k-ss>1) tt=k-1 // 左部短的直接处理

else flag=false // 左部处理完,需退栈

}

if (!flag && top>0)

{ss=s[top].low; tt=s[top].high; top--; flag=true;}

} // end of while (flag || top>0) } // 算法结束

int quickpass(rectype r[];int s,t) // 用“三者取中法”进行快速排序的一次划分 { int i=s, j=t, mid=(s+t)/2; rectype tmp;

if (r[i].key>r[mid].key) {tmp=r[i];r[i]=r[mid];r[mid]=tmp } if (r[mid].key>r[j].key)

{tmp=r[j];r[j]=r[mid];

if (tmp>r[i]) r[mid]=tmp; else {r[mid]=r[i];r[i]=tmp } }

{tmp=r[i];r[i]=r[mid];r[mid]=tmp }

// 三者取中:最佳2次比较3次赋值;最差3次比较10次赋值 rp=r[i]; x=r[i].key;

while (i

{while (i

while (i=r[j].key) i++; if (i

r[i]=rp; return (i);

} // 一次划分算法结束

5 7 16. (1) (2)

40 80 70 70 77777777加入5后 加入80后

30 30 9 9 7 15 10 15

45 50 30 20 12 10 45 50 30 20 12 40

(3)[题目分析]从插入位置进行调整,调整过程由下到上。首先根据元素个数求出插入元素所在层次数,以确定其插入层是最大层还是最小层。若插入元素在最大层,则先比较插入元素是否比双亲小,如是,则先交换,之后,将小堆与祖先调堆,直到满足小堆定义或到达根结点;若插入元素不小于双亲,则调大堆,直到满足大堆定义。若插入结点在最小层,则先比较插入元素是否比双亲大,如是,则先交换,之后,将大堆与祖先调堆;若插入结点在最小层且小于双亲,则将小堆与祖先调堆,

联系客服:779662525#qq.com(#替换为@)