第十章习题
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;i 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;i 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;i a[i]<->a[i+1]; change=1; } for(i=0;i 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; }