类似叙述题略。
67.外排序用k-路归并(k>2)是因为k越小，归并趟数越多，读写外存次数越多，时间效率越低，故，一般应大于最少的2路归并。 若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。 68. R1:19,48,65,74,101 R2:3,17,20,21,21,33,53,99
五.算法设计题
1. void BubbleSort2(int a[],int n) //相邻两趟向相反方向起泡的冒泡排序算法 { change=1;low=0;high=n-1; //冒泡的上下界
while(low { change=0; //设不发生交换 for(i=low;i if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;} //有交换，修改标志change high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i] }//BubbleSort2 [算法讨论]题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。 2. typedef struct node { ElemType data; struct node *prior,*next; }node，*DLinkedList; void TwoWayBubbleSort(DLinkedList la) //对存储在带头结点的双向链表la中的元素进行双向起泡排序。 {int exchange=1; // 设标记 DLinkedList p,temp,tail; head=la //双向链表头，算法过程中是向下起泡的开始结点 tail=null; //双向链表尾，算法过程中是向上起泡的开始结点 while (exchange) {p=head->next; //p是工作指针，指向当前结点 exchange=0; //假定本趟无交换 while (p->next!=tail) // 向下（右）起泡，一趟有一最大元素沉底 if (p->data>p->next->data) //交换两结点指针，涉及6条链 {temp=p->next; exchange=1;//有交换 p->next=temp->next;temp->next->prior=p //先将结点从链表上摘下 temp->next=p; p->prior->next=temp; //将temp插到p结点前 temp->prior=p->prior; p->prior=temp; } else p=p->next; //无交换，指针后移 tail=p; //准备向上起泡 p=tail->prior; while (exchange && p->prior!=head) //向上（左）起泡，一趟有一最小元素冒出 if (p->data {temp=p->prior; exchange=1; //有交换 p->prior=temp->prior;temp->prior->next=p； //先将temp结点从链表上摘 下 temp->prior=p; p->next->prior=temp; //将temp插到p结点后（右） temp->next=p->next; p->next=temp; } else p=p->prior; //无交换，指针前移 head=p; //准备向下起泡 }// while (exchange) } //算法结束 3. PROCEDURE StraightInsertSort(VAR R:listtype;n:integer); VAR i,j:integer; BEGIN FOR i:=2 TO n DO {假定第一个记录有序} BEGIN R[0]:=R[i]; j:=i-1; {将待排序记录放进监视哨} WHILE R[0].key R[j+1]:=R[0] {将待排序记录放到合适位置} END {FOR} END； 4. TYPE pointer=↑node; node=RECORD key:integer; link:pointer; END； PROCEDURE LINSORT(L:pointer); VAR t,p,q,s:pointer; BEGIN p:=L↑.link↑.link; {链表至少一个结点，p初始指向链表中第二结点（若存在）} L↑.link↑.link=NIL; {初始假定第一个记录有序} WHILE p<>NIL DO BEGIN q:=p↑.link; {q指向p的后继结点} s=L; WHILE (s↑.link<>NIL AND s↑.link↑.key s:=s↑.link; {向后找插入位置} p↑.link:=s↑.link; s↑.link=p;{插入结点} p=q; {恢复p指向当前结点} END {WHILE} END; {LINSORT} 5. typedef struct { int num; float score; }RecType; void SelectSort(RecType R[51]，int n) { for(i=1; i { //选择第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 if(a[j].key b[cnt]=a[i]; } }//Count_Sort (3) 对于有n个记录的表，关键码比较n2次。 (4) 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的 2 空间；而这种方法比较次数是n，且需要另一数组空间。 [算法讨论]因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是n2次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为： 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 if (i while (i if(R[i].key<=avg) return i; else return i-1; } 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 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 if (i while(i K[i]=K[0]; return i; }//Partition 10. [题目分析]把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功返回其位置或失败返回0为止。