发布时间 : 星期三 文章第十章排序参考答案更新完毕开始阅读f1d379da50e2524de5187ecb
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 [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[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[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）[题目分析]从插入位置进行调整，调整过程由下到上。首先根据元素个数求出插入元素所在层次数，以确定其插入层是最大层还是最小层。若插入元素在最大层，则先比较插入元素是否比双亲小，如是，则先交换，之后，将小堆与祖先调堆，直到满足小堆定义或到达根结点；若插入元素不小于双亲，则调大堆，直到满足大堆定义。若插入结点在最小层，则先比较插入元素是否比双亲大，如是，则先交换，之后，将大堆与祖先调堆；若插入结点在最小层且小于双亲，则将小堆与祖先调堆，