第9章习题答案

1、习题91.在各种排序方法中，哪些是稳定的？哪些是不稳定的？对不稳定的排序方法举出一个不稳定的例子。解：排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序折半插入排序二路插入排序表插入排序起泡排序直接选择排序希尔排序快速排序堆排序2-路归并排序基数排序稳定稳定稳定稳定稳定不稳定不稳定不稳定不稳定稳定稳定2,2,13,2,2,1(d=2，d=1)2,2,12,1,1(大顶堆)2.若不考虑基数排序，则排序的两种基本操作是什么？解：关键字的比较和记录的移动。3.外排序的基本操作是什么？解：生成有序归并段，归并。4.分别采用堆排序、快速排序、起泡排序和归并排序，对初始状态为有序的表，则最省

2、时间的是哪种排序方法？最费时间的是哪种排序方法？解：起泡排序，快速排序。5.不受待排序初始序列的影响的排序算法是哪种？其时间复杂度是多少？解：简单选择排序，时间复杂度是。6.直接插入排序设置监视哨的作用是什么？解：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。7.从平均时间性能而言，哪种排序方法最佳？解：快速排序。8.设待排序的记录有10个，其关键字分别为75，23，98，44，57，12，29，64，38，82。手工执行以下排序算法(按字典序比较关键字的大小)，写出每一堂排序结束时的关键字的状态：(1)直接插入排序(2)折半插入排序(3)起泡排序(4)简单选择排序(5)快速

3、排序(6)希尔排序(7)2-路归并排序(8)基数排序解：略9.已知记录序列R1.n中的关键字各不相同，可按如下所述实现计数排序：另设数组C1.n，对每个记录Ri，统计序列中关键字比它小的记录个数存于Ci，则Ci=0的记录必为关键字最小的记录，然后依Ci值的大小对R中记录进行重新排列，试编写实现上述排序的算法。解：void Count_Sort(int R,int n)/计数排序算法 int CMAX; for(i=0;i<n;i+)/对每一个元素 for(j=i,count=0;j<n;j+) /统计关键字比它小的元素个数 if(Rj<Ri)count+; Ci=count;

4、 for(i=0;i<n;i+)/依次求出关键字最小,第二小,.,最大的记录 min=i; for(j=i+1;j<n;j+) if(Cj<Cmin) min=j; /求出最小记录的下标min temp=Ri;Ri=Rmin; Rmin=temp; /与第i个记录交换 Cmin=Ci; /Count_Sort10.已知奇偶交换算法如下描述：第一趟对所有奇数的i，将Ri和Ri+1进行比较，第二趟对所有偶数的i，将Ri和Ri+1进行比较，每次比较时若Ri>Ri+1，则将两者交换，以后重复上述二趟过程，直到整个数组有序。(1)试问排序结束的条件是什么？(2)编写一个实现上述排

5、序过程的算法。解：void OE_Sort(int R ,int n)/奇偶交换排序的算法 change=1; while(change) change=0; for(i=1;i<n-1;i+=2) /对所有奇数进行一趟比较 if(Ri>Ri+1) temp=Ri; Ri=Ri+1; Ri+1=temp; change=1; for(i=0;i<n-1;i+=2) /对所有偶数进行一趟比较 if(Ri>Ri+1) temp=Ri; Ri=Ri+1; Ri+1=temp; change=1; /while/OE_Sort 本算法的结束条件是连续两趟比较无交换发生。11.编

6、写算法，对n个关键字取整数值的记录进行整理，使得所有关键字为负值的记录排在关键字为非负值的记录之前，要求：(1)采用顺序存储结构，至多使用一个记录的辅助存储空间。(2)算法的时间复杂度为。(3)讨论算法中记录的最大移动次数。解：void Divide(int R,int n)/把数组R中所有值为负的记录调到非负的记录之前 low=0;high=n-1;while(low<high) while(low<high&&Rhigh>=0) high-; /以0作为虚拟的枢轴记录 temp=Rlow; Rlow=Rhigh; Rhigh=temp; while(low

7、<high&&Rlow<0) low+; temp=Rlow; Rlow=Rhigh; Rhigh=temp; /Divide12.序列的“中值记录”指的是：如果将此序列排序后，它是第n/2个记录。试编写一个求中值记录的算法。解：typedef struct int gt; /大于该记录的个数 int lt; /小于该记录的个数pl; /整个序列中比某个关键字大或小的记录个数KeyType MidElement(SqList &L)if(!L.length)return 0;pl bMAX;RcdType temp;int i,j,min,t;for(i=1

8、; i<=L.length; i+)/对每一个元素统计比它大和比它小的元素个数gt和lt for(bi.gt=0, bi.lt=0,j=1;j<=L.length; j+)if(L.rj.key>L.ri.key)bi.gt+;else if(L.rj.key<L.ri.key)bi.lt+;for(i=1; i<=L.length; i+)min=i;for(j=i+1;j<=L.length;j+)if(bj.lt<bmin.lt)min=j;/求出最小记录的下标mintemp=L.ri;L.ri=L.rmin;L.rmin=temp;/与第i个记

9、录交换t=bi.gt+;bi.gt=bmin.gt+;bi.gt+;bmin.gt=t;bmin.gt+;t=bi.lt+;bi.lt=bmin.lt+;bi.lt+;bmin.lt=t;bmin.lt+;int mid=(L.length+1)/2;return L.rmid.key;13.有序数组是堆吗？解：有序数组是堆。因为有序数组中的关键字序列满足堆的性质。若数组为降序，则此堆为大顶堆，反之为小顶堆。14.在高度为h的堆中，最多有多少个记录？最少有多少个记录？在大顶堆中，关键字最小的记录可能存放在堆的哪些位置？解：高度为h的堆实际上为一棵高度为h的完全二叉树，因此根据二叉树的性质可以算出，它最少应有2h-1个元素；最多可有2h-1个元素(注意一个有括号，一个没有)。在大顶堆中，关键字最小的元素可能存放在堆的任一叶子结点上。15.若关键字是非负整数，快速排序、归并