第十章排序参考答案 下载本文

类似叙述题略。

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->dataprior->data) //交换两结点指针,涉及6条链

{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=avg) j--;

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=x) j--; if (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=x) j--; if (i

K[i]=K[0]; return i; }//Partition

10. [题目分析]把待查记录看作枢轴,先由后向前依次比较,若小于枢轴,则从前向后,直到查找成功返回其位置或失败返回0为止。