第十章习题

第十章习题

10.1 磁盘平衡归并和磁带平衡归并在时间上有否差别？如果有，差别在何处？如果没有，

请说明理由？

10.2 败者树中的败者指的是什么？若利用败者树求k个数中的最大值，在某次比较中得到

a>b，那么谁是败者？败者树与堆有何区别？

10.3 试问输入文件在哪种状态下，经由置换选择排序法得到的初始归并段长度最长？其最长的长度是多少？

10.4假如对一个经由置换选择排序法得到的输出文件再次进行置换选择排序，试问该文件将

产生什么变化？

10.5 设内存有大小为6个记录的区域可供内部排序之用，文件的关键字序列为：（51，49，

39，46，38，29，14，61，15，30，1，48，52，3，63，27，4，13，89，24，46，58，33，76）。试列出：

（1） 用内部排序方法求出的初始归并段； （2）用置换选择排序法得到的初始归并段。

10.6 假设某文件经内部排序得到100个初始归并段，试问：

（1）若要使多路归并三趟完成排序，则应取归并的路数至少为多少？

（2）假如操作系统要求一个程序同时可用的输入、输出文件的总数不超过13，则按多路

归并至少需几趟可完成排序？如果限定这个趟数，则可取的最低路数是多少？

10.7 假设一次I/O的物理块大小为150，每次可对750个记录进行内部排序，那么对含有

150000个记录的磁盘文件进行4路平衡归并排序时，需进行多少次I/O？ 10.8 手工执行算法k-merge，追踪败者树的变化过程。假设初始归并段如下：

（10，15，16，20，31，39，+∞）； （9，18，20，25，36，48，+∞）； （20，22，40，50，67，79，+∞）； （6，15，25，34，42，46，+∞）； （12，37，48，55，+∞）； （84，95，+∞）；

10.9 已知某文件经过置换选择排序之后，得到长度分别为47，9，39，18，4，12，23和7的八个初始归并段。试用3路平衡归并设计一个读写外存次数最少的归并方案，并求出读写外存的次数。

第十章 内部排序

10.23

void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法 {

k=L.length;

for(i=k-1;i;--i) //从后向前逐个插入排序

if(L.r[i].key>L.r[i+1].key) {

L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 }

}//Insert_Sort1 10.24

void BiInsert_Sort(SqList &L)//二路插入排序的算法 {

int d[MAXSIZE]; //辅助存储 x=L.r.key;d=x; first=1;final=1;

for(i=2;i<=L.length;i++) {

if(L.r[i].key>=x) //插入前部 {

for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j]; d[j+1]=L.r[i].key; final++; }

else //插入后部 {

for(j=first;d[j]

d[(j-2)%MAXSIZE+1]=L.r[i].key;

first=(first-2)%MAXSIZE+1; //这种形式的表达式是为了兼顾first=1的情况 } }//for

for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去 L.r[j].key=d[i]; }//BiInsert_Sort 10.25

void SLInsert_Sort(SLList &L)//静态链表的插入排序算法 {

L.r[0].key=0;L.r[0].next=1;

L.r[1].next=0; //建初始循环链表 for(i=2;i<=L.length;i++) //逐个插入 {

p=0;x=L.r[i].key;

while(L.r[L.r[p].next].key

q=L.r[p].next; L.r[p].next=i; L.r[i].next=q; }//for

p=L.r[0].next;

for(i=1;i

while(p

L.r[p]<->L.r[i]; L.r[i].next=p; } p=q; }//for

}//SLInsert_Sort 10.26

void Bubble_Sort1(int a[ ],int n)//对包含n个元素的数组a进行改进的冒泡排序 {

change=n-1; //change指示上一趟冒泡中最后发生交换的元素 while(change) {

for(c=0,i=0;ia[i+1]) {

a[i]<->a[i+1];

c=i+1; //c指示这一趟冒泡中发生交换的元素 }

change=c; }//while

}//Bubble_Sort1 10.27

void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法 {

low=0;high=n-1; //冒泡的上下界 change=1;

while(low

change=0;

for(i=low;ia[i+1]) {

a[i]<->a[i+1]; change=1;

}

high--; //修改上界

for(i=high;i>low;i--) //从下向上起泡 if(a[i]

a[i]<->a[i-1]; change=1; }

low++; //修改下界 }//while

}//Bubble_Sort2 10.28

void Bubble_Sort3(int a[ ],int n)//对上一题的算法进行化简,循环体中只包含一次冒泡 {

int b[ 3 ]; //b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用

d=1;b[0]=0;b[ 2 ]=n-1; //d为冒泡方向的标识,1为向上,-1为向下 change=1;

while(b[0]

change=0;

for(i=b[1-d];i!=b[1+d];i+=d) //统一的冒泡算法 if((a[i]-a[i+d])*d>0) //注意这个交换条件 {

a[i]<->a[i+d]; change=1; }

b[1+d]-=d; //修改边界 d*=-1; //换个方向 }//while

}//Bubble_Sort3 10.29

void OE_Sort(int a[ ],int n)//奇偶交换排序的算法 {

change=1;

while(change) {

change=0;

for(i=1;ia[i+1]) {

a[i]<->a[i+1]; change=1; }

for(i=0;ia[i+1]) {

a[i]<->a[i+1]; change=1; } }//while }//OE_Sort

分析:本算法的结束条件是连续两趟比较无交换发生 10.30

typedef struct {

int low; int high;

} boundary; //子序列的上下界类型

void QSort_NotRecurve(int SQList &L)//快速排序的非递归算法 {

low=1;high=L.length;

InitStack(S); //S的元素为boundary类型

while(low

if(high-low>2) //如果当前子序列长度大于3且尚未排好序 {

pivot=Partition(L,low,high); //进行一趟划分 if(high-pivot>pivot-low) {

Push(S,{pivot+1,high}); //把长的子序列边界入栈 high=pivot-1; //短的子序列留待下次排序 } else {

Push(S,{low,pivot-1}); low=pivot+1; } }//if

else if(low

Easy_Sort(L,low,high); //直接进行比较排序 low=high; //当前子序列标志为已排好序 }

else //如果当前子序列已排好序但栈中还有未排序的子序列 {

Pop(S,a); //从栈中取出一个子序列 low=a.low; high=a.high; }

}//while

}//QSort_NotRecurve

int Partition(SQList &L,int low,int high)//一趟划分的算法,与书上相同 {

L.r[0]=L.r[low];

pivotkey=L.r[low].key; while(low

while(low=pivotkey) high--;

L.r[low]=L.r[high];

while(low

L.r[high]=L.r[low]; }//while

L.r[low]=L.r[0]; return low; }//Partition

void Easy_Sort(SQList &L,int low,int high)//对长度小于3的子序列进行比较排序 {

if(high-low==1) //子序列只含两个元素

if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high]; else //子序列含有三个元素 {

if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1]; if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high]; if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1]; }

}//Easy_Sort 10.31

void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前 {

low=0;high=n-1; while(low

while(low=0) high--; //以0作为虚拟的枢轴记录 a[low]<->a[high];

while(lowa[high]; }

}//Divide 10.32

typedef enum {RED,WHITE,BLUE} color; //三种颜色

void Flag_Arrange(color a[ ],int n)//把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列 {

i=0;j=0;k=n-1; while(j<=k) switch(a[j]) {

case RED: a[i]<->a[j]; i++; j++; break;

case WHITE: j++; break; case BLUE: a[j]<->a[k];

k--; //这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况 }

}//Flag_Arrange

分析:这个算法中设立了三个指针.其中,j表示当前元素;i以前的元素全部为红色;k以后的元素全部为蓝色.这样,就可以根据j的颜色,把其交换到序列的前部或者后部. 10.33

void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法 {

for(p=L;p->next->next;p=p->next) {

q=p->next;x=q->data;

for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点 if(r->next->data

x=r->next->data; s=r; }

if(s!=q) //找到了值比q->data更小的最小结点s->next {

p->next=s->next;s->next=q;

t=q->next;q->next=p->next->next; p->next->next=t;

} //交换q和s->next两个结点 }//for

}//LinkedList_Select_Sort 10.34

void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法 {

for(i=2;i

{ //此时从H.r[1]到H.r[i-1]已经是大顶堆 j=i;

while(j!=1) //把H.r[i]插入 {

k=j/2;

if(H.r[j].key>H.r[k].key) H.r[j]<->H.r[k]; j=k; } }//for

}//Build_Heap 10.35

void TriHeap_Sort(Heap &H)//利用三叉树形式的堆进行排序的算法 {

for(i=H.length/3;i>0;i--) Heap_Adjust(H,i,H.length); for(i=H.length;i>1;i--) {

H.r[1]<->H.r[i];

Heap_Adjust(H,1,i-1); }

}//TriHeap_Sort

void Heap_Adjust(Heap &H,int s,int m)//顺序表H中,H.r[s+1]到H.r[m]已经是堆,把H.r[s]插入并调整成堆 {

rc=H.r[s];

for(j=3*s-1;j<=m;j=3*j-1) {

if(j

H.r[s]=rc; }//Heap_Adjust

分析:本算法与课本上的堆排序算法相比,只有两处改动:1.建初始堆时,i的上限从H.length/3开始(为什么?) 2.调整堆的时候,要从结点的三个孩子结点中选择最大的那一个,最左边的孩子的序号的计算公式为j=3*s-1(为什么?) 10.36

void Merge_Sort(int a[ ],int n)//归并排序的非递归算法 {

for(l=1;l

for(i=0;(2*i-1)*l

start1=2*l*i; //求出待归并的两段的上下界 end1=start1+l-1; start2=end1+1;

end2=(start2+l-1)>(n-1)?(n-1):(start2+l-1);//注意end2可能超出边界 Merge(a,start1,end1,start2,end2); //归并 }

}//Merge_Sort

void Merge(int a[ ],int s1,int e1,int s2,int e2)//将有序子序列a[s1]到a[e1]和a[s2]到a[e2]归并为有序序列a[s1]到a[e2] {

int b[MAXSIZE]; //设立辅助存储数组b for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++) {

if(a[i]

while(i<=e1) b[k++]=a[i++];

while(j<=e2) b[k++]=a[j++]; //归并到b中 for(i=s1;i<=e2;i++) //复制回去 a[i]=b[i]; }//Merge 10.37

void LinkedList_Merge_Sort1(LinkedList &L)//链表结构上的归并排序非递归算法 {

for(l=1;lnext,e2=p;p->next;p=e2) {

for(i=1,q=p;i<=l&&q->next;i++,q=q->next); e1=q;

for(i=1;i<=l&&q->next;i++,q=q->next); e2=q; //求出两个待归并子序列的尾指针

if(e1!=e2) LinkedList_Merge(L,p,e1,e2); //归并 }

}//LinkedList_Merge_Sort1

void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2 {

q=p->next;r=e1->next; //q和r为两个子序列的起始位置 while(q!=e1->next&&r!=e2->next) {

if(q->datadata) //选择关键字较小的那个结点接在p的后面

{

p->next=q;p=q; q=q->next; } else {

p->next=r;p=r; r=r->next; }

}//while

while(q!=e1->next) //接上剩余部分 {

p->next=q;p=q; q=q->next; }

while(r!=e2->next) {

p->next=r;p=r; r=r->next; }

}//LinkedList_Merge 10.38

void LinkedList_Merge_Sort2(LinkedList &L)//初始归并段为最大有序子序列的归并排序,采用链表存储结构 {

LNode *end[MAXSIZE]; //设立一个数组来存储各有序子序列的尾指针 for(p=L->next->next,i=0;p;p=p->next) //求各有序子序列的尾指针 if(!p->next||p->data>p->next->data) end[i++]=p;

while(end[0]->next) //当不止一个子序列时进行两两归并 {

j=0;k=0; //j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置 for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列 {

e1=end[j];e2=end[j+1]; //确定两个子序列

if(e1->next) LinkedList_Merge(L,p,e1,e2); //归并

end[k++]=e2; //用新序列的尾指针取代原来的尾指针 j+=2; //转到后面两个子序列 }

}//while

}//LinkedList_Merge_Sort2

void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2 {

q=p->next;r=e1->next;

while(q!=e1->next&&r!=e2->next)

{

if(q->datadata) {

p->next=q;p=q; q=q->next; } else {

p->next=r;p=r; r=r->next; }

}//while

while(q!=e1->next) {

p->next=q;p=q; q=q->next; }

while(r!=e2->next) {

p->next=r;p=r; r=r->next; }

}//LinkedList_Merge,与上一题完全相同 10.39

void SL_Merge(int a[ ],int l1,int l2)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列 {

start1=0;start2=l1; //分别表示序列1和序列2的剩余未归并部分的起始位置 for(i=0;i

for(j=start2;j RSh(a,start1,j-1,k);//将a[start1]到a[j-1]之间的子序列循环右移k位 start1+=k+1;

start2=j; //修改两序列尚未归并部分的起始位置 }

}//SL_Merge

void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18 {

len=end-start+1; for(i=1;i<=k;i++)

if(len%i==0&&k%i==0) p=i; //求len和k的最大公约数p for(i=0;i

j=start+i;l=start+(i+k)%len;temp=a[j]; while(l!=start+i) {

a[j]=temp; temp=a[l]; a[l]=a[j];

j=l;l=start+(j-start+k)%len; //依次向右移 }

a[start+i]=temp; }//for }//RSh 10.40

书后给出的解题思路在表述上存在问题,无法理解.比如说,\把第一个序列划分为两个子序列,使其中的第一个子序列含有s1个记录,0<=s1

void Hash_Sort(int a[ ])//对1000个关键字为四位整数的记录进行排序 {

int b[10000];

for(i=0;i<1000;i++) //直接按关键字散列 {

for(j=a[i];b[j];j=(j+1)000); b[j]=a[i]; }

for(i=0,j=0;i<1000;j++) //将散列收回a中 if(b[j]) {

for(x=b[j],k=j;b[k];k=(k+1)000) if(b[k]==x) {

a[i++]=x; b[k]=0; } }//if

}//Hash_Sort 10.42

typedef struct {

int gt; //大于该记录的个数 int lt; //小于该记录的个数

} place; //整个序列中比某个关键字大或小的记录个数 int Get_Mid(int a[ ],int n)//求一个序列的中值记录的位置 {

place b[MAXSIZE];

for(i=0;i

if(a[j]>a[i]) b[i].gt++; else if(a[j]

min_dif=abs(b[0].gt-b[0].lt);

for(i=0;i

void Count_Sort(int a[ ],int n)//计数排序算法 {

int c[MAXSIZE];

for(i=0;i

for(j=0,count=0;j for(i=0;i

min=0;

for(j=0;j

if(c[j]a[min]; //与第i个记录交换

c[min]=INFINITY; //修改该记录的c值为无穷大以便下一次选取 }

}//Count_Sort 10.44

void Enum_Sort(int a[ ],int n)//对关键字只能取v到w之间任意整数的序列进行排序 {

int number[w+1],pos[w+1];

for(i=0;i

pos[i]=pos[i-1]+num[i]; //pos数组可以把关键字的值映射为元素在排好的序列中的位置

for(i=0;i

a[i]=c[i]; }//Enum_Sort

分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpot数组起的是相类似的作用. 10.45

typedef enum {0,1,2,3,4,5,6,7,8,9} digit; //个位数类型

typedef digit[3] num; //3位自然数类型,假设低位存储在低下标,高位存储在高下标 void Enum_Radix_Sort(num a[ ],int n)//利用计数实现基数排序,其中关键字为3位自然数,共有n个自然数 {

int number ,pos ; num c[MAXSIZE];

for(j=0;j<3;j++) //依次对个位,十位和百位排序 {

for(i=0;i

pos[i]=pos[i-1]+num[i]; //把关键字的值映射为元素在排好的序列中的位置 for(i=0;i

}//Enum_Radix_Sort

分析:计数排序是一种稳定的排序方法.正因为如此,它才能够被用来实现基数排序. 10.46

typedef struct {

int key; int pos;

} Shadow; //影子序列的记录类型

void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)//对元素很大的记录序列b进行排序,结果放入a中,不移动元素 {

Shadow d[MAXSIZE];

for(i=0;i

d[i].key=b[i].key; d[i].pos=i; }

for(i=n-1,change=1;i>1&&change;i--) //对影子序列执行冒泡排序 {

change=0;

for(j=0;j

if(d[j].key>d[j+1].key) {

d[j]<->d[j+1]; change=1; } }//for

for(i=0;i

本文来源：https://www.bwwdw.com/article/mf1o.html