{ //选择第i大的记录，并交换到位
k=i; //假定第i个元素的关键字最大
for(j=i+1;j<=n;j++) //找最大元素的下标 if(R[j].score>R[k].score) k=j;
if(i!=k) R[i] <-->R[k]; //与第i个记录交换 }//for
for(i=1; i<=n; i++) //输出成绩
{ printf(\if(i==0) printf(\
}//SelectSort 6. typedef struct
{ int key; datatype info}RecType
void CountSort(RecType a[],b[],int n) //计数排序算法，将a中记录排序放入b中
{ for(i=0;i { for(j=0,cnt=0;j if(a[j].key }//Count_Sort (3) 对于有n个记录的表，关键码比较n次。 (4) 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间；而这种方法比较次数是n，且需要另一数组空间。 [算法讨论]因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数2 是n次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为： for(i=0;i for(j=i+1;j if(a[i].key 7. [题目分析]保存划分的第一个元素。以平均值作为枢轴，进行普通的快速排序，最后枢轴的位置存入已保存的第一个元素，若此关键字小于平均值，则它属于左半部，否则属于右半部。 int partition (RecType r[],int l,h) { int i=l,j=h,avg=0; for(;i<=h;i++) avg+=R[i].key; i=l; avg=avg/(h-l+1); while (i { while (i while (i } if(R[i].key<=avg) return i; else return i-1; } 2 2 void quicksort (RecType R[],int S,T); {if (S {k=partition (R,S,T); quicksart (R,S,k); quicksart (R,k+1,T);} } 8. int Partition(RecType R[]，int l，int h) //一趟快速排序算法，枢轴记录到位，并返回其所在位置， { int i=l; j=h; R[0] = R[i]; x = R[i].key; while(i { while(i while(i 9. [题目分析]以Kn为枢轴的一趟快速排序。将上题算法改为以最后一个为枢轴先从前向后 再从后向前。 int Partition(RecType K[]，int l，int n) { //交换记录子序列K[l..n]中的记录，使枢轴记录到位，并返回其所在位置， //此时，在它之前（后）的记录均不大（小）于它 int i=l; j=n; K[0] = K[j]; x = K[j].key; while(i { while(i while(i K[i]=K[0]; return i; }//Partition 10. [题目分析]把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功返回其位置或失败返回0为止。 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;