类似叙述题略。
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]a[i-1];change=1;} low++; //修改下界 }//while }//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