第10章排序(参考答案)
18. 对于后三种排序方法两趟排序后,序列的首部或尾部的两个元素应是有序的两个极值,而给定的序列并不满足。
20. 本题为步长为3的一趟希尔排序。 24.枢轴是73。
49. 小根堆中,关键字最大的记录只能在叶结点上,故不可能在小于等于n/2的结点上。
64. 因组与组之间已有序,故将n/k个组分别排序即可,基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。
部分答案解释如下:
5. 错误。例如冒泡排序是稳定排序,将4,3,2,1按冒泡排序排成升序序列,第一趟变成3,2,1,4,此时3就朝向最终位置的相反方向移动。 12. 错误。堆是n个元素的序列,可以看作是完全二叉树,但相对于根并无左小右大的要求,故其既不是二叉排序树,更不会是平衡二叉树。
22. 错误。待排序序列为正序时,简单插入排序比归并排序快。
三、填空题
1. 比较,移动
2.生成有序归并段(顺串),归并
3.希尔排序、简单选择排序、快速排序、堆排序等
4. 冒泡,快速
5. (1)简单选择排序 (2)直接插入排序(最小的元素在最后时)
6. 免去查找过程中每一步都要检测整个表是否查找完毕,提高了查找效率。
7. n(n-1)/2
8.题中p指向无序区第一个记录,q指向最小值结点,一趟排序结束,p和q所指结点值交换,同时向后移p指针。(1)!=null (2)p->next (3)r!=null (4)r->data
9. 题中为操作方便,先增加头结点(最后删除),p指向无序区的前一记录,r指向最小值结点的前驱,一趟排序结束,无序区第一个记录与r所指结点的后继交换指针。
(1)q->link!=NULL (2)r!=p (3)p->link (4)p->link=s (5)p=p->link
10.(1)i (6)r[max]<-->r[n-i+1] 11.(1)N (2)0 (3)N-1 (4)1 (5)R[P].KEY (7)(N+2)(N-1)/2 (8)N-1 (9)0 (10)O(1)(每个记录增加一个字段) (11)稳定(请注意I 的步长为-1) 12. 3,(10,7,-9,0,47,23,1,8,98,36) 13.快速 14.(4,1,3,2,6,5,7) 15.最好每次划分能得到两个长度相等的子文件。设文件长度n=2k-1,第一遍划分得到两个 长度?n/2?的子文件,第二遍划分得到4个长度?n/4?的子文件,以此类推,总共进行 k=log2(n+1)遍划分,各子文件长度均为1,排序结束。 16.O(n2) 17. O(nlog2n) 18.(1)2*i (2)r[j].key>r[j+1].key (3)true (4)r[j] (5)2*i 19.(1)2*i (2)j<=r (3)j←j+1 (4)x.key>heap[j].key (5)i←j (6)j←2*i (7)x 20.(1)j:=2*i (2)finished:=false (3)(r[j].key>r[j+1].key) (4)r[i]:=r[j] (5)i:=j (6) j:=2*i (7)r[i]:=t; (8)s if t(r,i,n) (9)r[1]:=r[i] (10)s if t(r,1,i-1) 21. ④是堆 (1)选择 (2)筛选法 (3)O(nlog2n) (4)O(1) 22. (1) 选择 (2)完全二叉树 (3)O(Nlog2N) (4)O(1) (5)满足堆的性质 23.(1)finish:=false (2)h[i]:=h[j]; i:=j; j:=2*j; (3)h[i]:=x (4)h,k,n (5)s if t(h,1,r-1) 24. {D,Q,F,X,A,P,B,N,M,Y,C,W} 25. (1)p[k]:=j (2)i:=i+1 (3)k=0 (4)m:=n (5)m 26. 程序(a)(1)true (2)a[i]:=t (3)2 TO n step 2 (4)true (5)NOT flag 程序(b)(1)1 (2)a[i]=t (3)(i=2;i<=n;i+=2) (4)1 (5)flag 27.(Q,A,C,S,Q,D,F,X,R,H,M,Y),(F,H,C,D,Q,A,M,Q,R,S,Y,X) 28. 初始归并 段(顺串) 29. 初始归并段,初始归并段,减少外存信息读写次数(即减少归并趟数),增加归并路数和 减少初始归并段个数。 30. ?n/m? 31.(1)m,j-1 (2) m:=j+1 (3)j+1,n (4) n:=j-1 最大栈空间用量为 O(logn)。 四、应用题 1. 假设含n个记录的序列为{ R1, R2, …,R n},其相应的关键字序列为{ K1, K2, …,K n}, 这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系Ks1≤Ks2≤…≤Ks n, 按此固有关系将n个记录序列重新排列为{ Rs1, Rs2, …,Rs n }。若整个排序过程都在内存 中完成,则称此类排序问题为内部排序。 2. 3. 这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化,而题中叙述和排序中稳定性的定义无关,所以此说法不对。对4,3,2,1起泡排序就可否定本题结论。 4. 可以做到。取a与b进行比较,c与d进行比较。设a>b,c>d(ad,则有序a>b>d;若b 5. 本题答案之一请参见第9章的“四、应用题”第70题,这里用分治法求解再给出另一参考答案。 对于两个数x和y,经一次比较可得到最大值和最小值;对于三个数x,y,z,最多经3次比较可得最大值和最小值;对于n(n>3)个数,将分成长为n-2和2的前后两部分A和B,分别找出最大者和最小者:Max A、Min A、Max B、Min B,最后Max={Max A,Max B}和Min={Min A,Min B}。对A 使用同样的方法求出最大值和最小值,直到元素个数不超过3。设C(n)是所需的最多比较次数,根据上述原则,当n>3时有如下关系式: C(n)= 通过逐步递推,可以得到:C(n)=?3n/2?-2。显然,当n>=3时,2n-3>3n/2-2。事实上,?3n/2?-2是解决这一问题的比较次数的下限。 6. 假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个,则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子,则说明尚有两种状态没有分辨出来。我们知道,若二叉树高度是h,则叶子结点个数最多为2h-1;反之,若有u个 叶子结点,则二叉树的高度至少为?log2u?+1。这就是说,描述n个记录排序的判定树必定存在一条长度为?log2(n!)?的路径。即任何一个籍助“比较”进行排序的算法,在最坏情况下所需进行的比较次数至少是?log2(n!)?。根据斯特林公式,有?log2(n!)? =O(nlog2n)。即籍助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog2n)。证毕。 7. 答:拓扑排序,是有向图的顶点依照弧的走向,找出一个全序集的过程,主要是根据与顶点连接的弧来确定顶点序列;冒泡排序是借助交换思想通过比较相邻结点关键字大小进行排序的算法。 8. 直接插入排序的基本思想是基于插入,开始假定第一个记录有序,然后从第二个记录开始,依次插入到前面有序的子文件中。即将记录R[i](2<=i<=n)插入到有序子序列R[1..i-1]中,使记录的有序序列从R[1..i-1]变为R[1..i] ,最终使整个文件有序。共进行n-1趟插入。最坏时间复杂度是0(n2),平均时间复杂度是0(n2),空间复杂度是O(1),是稳定排序。 简单选择排序的基本思想是基于选择,开始有序序列长度为零,第i(1<=i 二路并归排序的基本思想是基于归并,开始将具有n个待排序记录的序列看成是n个长度为1的有序序列,然后进行两两归并,得到?n/2?个长度为2的有序序列,再进行两两归并,得到?n/4?个长度为4的有序序列。如此重复,经过?log2n?趟归并,最终得到一个长度为n的有序序列。最坏时间复杂度和平均时间复杂度都是0(nlog2n),空间复杂度是O(n),是稳定排序。 9. 错误。快速排序,堆排序和希尔排序是时间性能较好的排序方法,但都是不稳定的排序方法。 10. 等概率(后插),插入位置0..n,则平均移动个数为n/2。 若不等概率,则平均移动个数为= 11. 从节省存储空间考虑:先选堆排序,再选快速排序,最后选择归并排序; 从排序结果的稳定性考虑:选择归并排序。堆排序和快速排序都是不稳定排序; 从平均情况下排序最快考虑:先选择快速排序。 12. (1)堆排序,快速排序,归并排序 (2)归并排序 (3)快速排序 (4)堆排序 13. 平均比较次数最少: 快速排序; 占用空间最多: 归并排序; 不稳定排序算法:快速排序、堆排序、希尔排序。 14. 求前k个最大元素选堆排序较好。因为在建含n个元素的堆时,总共进行的关键字的比较次数不超过4n ,调整建新堆时的比较次数不超过2log2n次。在n个元素中求前k个最大元素,在堆排序情况下比较次数最多不超过4n+2klog2n。 稳定分类是指,若排序序列中存在两个关键字值相同的记录Ri与Rj(Ki=Kj,i≠j)且Ri 领先于Rj,若排序后Ri与Rj的相对次序保持不变,则称这类分类是稳定分类(排序),否则为不稳定分类。 A,C和E是稳定分类(排序),B和D是不稳定分类(排序)。 15. 16. (1)此为直接插入排序算法,该算法稳定。 (2)r[O]的作用是监视哨,免去每次检测文件是否到尾,提高了排序效率。 采用x.key<=r[j].key描述算法后,算法变为不稳定排序,但能正常工作。 17. (1) 横线内容:①m ②1 ③0 ④1 (2)flag起标志作用。若未发生交换,表明待排序列已有序,无需进行下趟排序。 (3)最大比较次数n(n-1)/2,最大移动次数3n(n-1)/2 (4)稳定 18. (1) ①499 ②A[j]>A[j+1] ③b:=true (2)冒泡排序 (3)499次比较,0次交换 (4) n(n-1)/2次比较,n(n-1)/2次交换(相当3n(n-1)/2次移动),本题中n=500,故 有124750次比较和交换(相当373250次移动)。 19. 答:此排序为双向起泡排序:从前向后一趟排序下来得到一个最大值,若其中发生交换, 则再从后向前一趟排序,得到一个最小值。一趟: 12,23,35,16,25,36,19,21,16,47 二趟:12,16,23,35,16,25,36,19,21,47 三趟: 12,16,23,16,25,35,19,21,36,47 四趟:12,16,16,23,19,25,35,21,36,47 五趟:12,16,16,19,23,25,21,35,36,47 六趟:12,16,16,19,21,23,25,35,36,47 七趟: 12,16,16,19,21,23,25,35,36,47 20. 对冒泡算法而言,初始序列为反序时交换次数最多。若要求从大到小排序,则表现为初 始是上升序。 21. 证明:起泡排序思想是相邻两个记录的关键字比较,若反序则交换,一趟排序完成得到 一个极值。由题假设知R j在R i之前且K j>R i,即说明R j和R i是反序;设对于R i之前全部记录1—R i-1(其中包括K j)中关键字最大为Kmax,则Kmax≥Kj,故经过起泡排序前i-2次后,R i-1 的关键字一定为Kmax,又因Kmax≥K j>R i,故R i-1和R i为反序,由此可知R i-1和R i必定交换, 证毕。 22.采用直接插入排序算法,因为记录序列已基本有序,直接插入排序比较次数少,且由于 少量次序不对的记录与正确位置不远,使直接插入排序记录移动次数也相对较少,故选直接 插入排序算法。 23. 各带标号语句的频度:(1)n (2)n-1 (3)(n+2)(n-1)/2 (4)n(n-1)/2 (5)n-1 时间复杂度O(n2), 属于直接选择排序。 24. 6, 13, 28, 39, 41, 72, 85, 20 i=1↑ m=4↑ r=7↑ 20<39 i=1↑m=2↑r=3↑ 20>13 i=3 r=3 m=3 20<28 r=2 i=3 将r+1(即第3个)后的元素向后移动,并将20放入r+1处,结果为 6,13,20,28,39,41,72,85。 (1)使用二分法插入排序所要进行的比较次数,与待排序的记录的初始状态无关。不 论待排序序列是否有序,已形成的部分子序列是有序的。二分法插入首先查找插入位置,插 入位置是判定树查找失败的位置。失败位置只能在判定树的最下两层上。 (2)一些特殊情况下,二分法插入排序要比直接插入排序要执行更多的比较。例如, 在待排序序列已有序的情况下就是如此。 25. (1)直接插入排序 第一趟(3)[8,3],2,5,9,1,6 第二趟(2)[8,3,2],5,9,1,6 第三趟 (5)[8,5,3,2],9,1,6 第四趟(9)[9,8,5,3,2],1,6 第五趟(1)[9,8,5,3,2,1],6 第六趟 (6)[9,8,6,5,3,2,1] (2)直接选择排序(第六趟后仅剩一个元素,是最小的,直接选择排序结束) 第一趟(9)[9],3,2,5,8,1,6 第二趟(8)[9,8],2,5,3,1,6 第三趟 (6)[9,8,6],5,3,1,2 第四趟(5)[9,8,6,5],3,1,2 第五趟(3)[9,8,6,5,3],1,2 第六趟 (2)[9,8,6,5,3,2],1 (3)直接插入排序是稳定排序,直接选择排序是不稳定排序。 26.这种看法不对。本题的叙述与稳定性的定义无关,不能据此来判断排序中的稳定性。例如 5,4,1,2,3在第一趟冒泡排序后得到4,1,2,3,5。其中4 向前移动,与其最终位置相反。但冒泡排序是稳定排序。快速排序中无这种现象。 设D=7 D=3 1,11,2,5,15,8,14,34,20,22,66,100,44,76,125 D=1 1,2,5,8,11,14,15,20,22,34,44,66,76,100,125 28. 设待排序记录的个数为n,则快速排序的最小递归深度为?log2n?+1,最大递归深度n。 29. 平均性能最佳的排序方法是快速排序,该排序方法不稳定。 初始序列: 50,10,50,40,45,85,80 一趟排序: [45,10,50,40] 50 [85,80] 二趟排序: [40,10] 45 [50] 50 [80] 85 三趟排序: 10,40,45,50,50,80,85 30. 快速排序。 31. (1) 在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2k-1,那么第一遍划分得到两个长度均为?n/2?的子文件,第二遍划分得到4个长度均为?n/4?的子文件,以此类推,总共进行k=log2(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件(长度均为3,k=2)进行排序,各需2次,共10次即可。 (2) 在最好情况下快速排序的原始序列实例:4,1,3,2,6,5,7。 (3) 在最坏情况下,若每次用来划分的记录的关键字具有最大值(或最小值),那么只能得到左(或右)子文件,其长度比原长度少1。因此,若原文件中的记录按关键字递减次序排列,而要求排序后按递增次序排列时,快速排序的效率与冒泡排序相同,其时间复杂度为O(n2)。所以当n=7时,最坏情况下的比较次数为21次。 (4) 在最坏情况下快速排序的初始序列实例: 7,6,5,4,3,2,1,要求按递增排序。32.该排序方法为快速排序。 33. 不是。因为当序列已有序时,快速排序将退化成冒泡排序,时间复杂度为O(n2)。当待排序序列无序,使每次划分完成后,枢轴两侧子文件长度相当,此时快速排序性能最好。34. 初始序列:[28],07,39,10,65,14,61,17,50,21 21移动:21,07,39,10,65,14,61,17,50,[] 39移动:21,07,[],10,65,14,61,17,50,39 17移动:21,07,17,10,65,14,61,[],50,39 65移动:21,07,17,10,[],14,61,65,50,39 14移动:21,07,17,10,14,[28],61,65,50,39 类似本题的另外叙述题的解答: (1):快速排序思想:首先将待排序记录序列中的所有记录作为当前待排序区域,以第一个记录的关键字作为枢轴(或支点)(pivot),凡其关键字不大于枢轴的记录均移动至该记录之前,凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后,记录的无序序列R[s..t]将分割成两部分:R[s..i-1]和R[i+1..t],且R[j].key≤R[i].key≤R[k].key(s ≤j 35.(1)不可以,若m+1到n之间关键字都大于m的关键字时,<=k可将j定位到m上,若为 (2)不稳定,例如2,1,2′,(m=1,n=3)对2,1,2′排序,完成会变成1,2′,2。 (3)各次调用qsort1的结果如下: 一次调用m=1,n=10 11,3,16,4,18,22,58,60,40,30 j=6 二次调用m=7,n=10 11,3,16,4,18,22,40,30,58,60 j=9 (右部) 三次调用m=10,n=10 不变,返回 m=7,n=8 11,3,16,4,18,22,30,40,58,60 j=8 四次调用m=9,n=8 不变,返回m=7,n=7 返回m=1,n=5 4,3,11,16,18,22,30,40,58,60 j=3(左部) 五次调用m=1,n=2 3,4,11,16,18,22,30,40,58,60 j=2 六次调用m=1,n=1 不变,返回 m=3,n=2 返回m=4,n=5 3,4,11,16,18,22,30,40,58,60 j=4 七次调用m=4,n=3 不变,返回(注:一次划分后,左、右两部分调用算两次)(4)最大栈空间用量为O(logn)。 36. 在具有n个元素的集合中找第k(1≤k≤n)个最小元素,应使用快速排序方法。其基本思想如下:设n个元素的集合用一维数组表示,其第一个元素的下标为1,最后一个元素下标为n。以第一个元素为“枢轴”,经过快速排序的一次划分,找到“枢轴”的位置i,若i=k,则该位置的元素即为所求;若i>k,则在1至i-1间继续进行快速排序的划分;若i 37. 快速排序各次调用结果: 一次调用:18,36,77,42,23,65,84,10,59,37,61,98 二次调用:10,18,77,42,23,65,84,36,59,37,61,98 三次调用:10,18,61,42,23,65,37,36,59,77,84,98 归并排序各次调用结果: 一次调用36,98,42,77,23,65,10,84,37,59,18,61, (子文件长度为1,合并后子文件长度为2) 二次调用36,42,77,98,10,23,65,84,18,37,59,61 (子文件长度为2,合并后子文件长 度为4) 三次调用10,23,36,42,65,77,84,98,18,37,59,61 (第一子文件长度8,第二子文件长度为4) 38. 建立堆结构:97,87,26,61,70,12,3,45 (2)70,61,26,3,45,12,87,97 (4)45,12,26,3,61,70,87,97 (6)12,3,26,45,61,70,87,97 39. (1)是大堆; (2)是大堆;(4)是小堆; (3)不是堆,调成大堆 100,98,66,85,80,60,40,77,82,10,20 类似叙述(1):不是堆 调成大顶堆 92,86,56,70,33,33,48,65,12 (2)①是堆 ②不是堆 调成堆 100,90,80,25,85,75,60,20,10,70,65,50 (3)①是堆 ②不是堆 调成大堆21,9,18,8,4,17,5,6(图略) (4):略 40. 在内部排序方法中,一趟排序后只有简单选择排序和冒泡排序可以选出一个最大(或最小)元素,并加入到已有的有序子序列中,但要比较n-1次。选次大元素要再比较n-2次, 其时间复杂度是O(n 2 )。从10000个元素中选10个元素不能使用这种方法。而快速排序、插入排序、归并排序、基数排序等时间性能好的排序,都要等到最后才能确定各元素位置。只有堆排序,在未结束全部排序前,可以有部分排序结果。建立堆后,堆顶元素就是最大(或最小,视大堆或小堆而定)元素,然后,调堆又选出次大(小)元素。凡要求在n 个元素中选出k(k< (2) 求次小值 42. 用堆排序方法,详见第40题的分析。从序列{59,11,26,34,14,91,25}得到{11,17,25}共用14次比较。其中建堆输出11比较8次,调堆输出17和25各需要比较4次和2次。 类似本题的另外叙述题的解答: (1)堆排序,分析同前,共20+5+4+5=34 次比较。 43. 对具体例子的手工堆排序略。 堆与败者树的区别:堆是n 个元素的序列,在向量中存储,具有如下性质: (i=1,2,…,?n/2?) 由于堆的这个性质中下标i 和2i 、2i+1的关系,恰好和完全二叉树中第i 个结点和其子树结点的序号间的关系一致,所以堆可以看作是n 个结点的完全二叉树。而败者树是由参加比赛的n 个元素作叶子结点而得到的完全二叉树。每个非叶(双亲)结点中存放的是两个子结点中的败者数据,而让胜者去参加更高一级的比赛。另外,还需增加一个结点,即结点0,存放比赛的全局获胜者。 44.(1)堆的存储是顺序的 (2)最大值元素一定是叶子结点,在最下两层上。 (3)在建含有n 个元素、深度为h 的堆时,其比较次数不超过4n ,推导如下: 由于第i 层上的结点数至多是2i-1 ,以它为根的二叉树的深度为h-i+1,则调用?n/2?次筛选算法时总共进行的关键字比较次数不超过下式之值: (2)树形选择排序基本思想:首先对n 个待排序记录的关键字进行两两比较,从中选出?n/2?个较小者再两两比较,直到选出关键字最小的记录为止,此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军”,而“亚军”是从与“冠军”比较失败的记录中找出,具体做法为:输出“冠军”后,将其叶子结点关键字改为“最大值”,然后从该叶子结点开始,和其左(或右)兄弟比较,修改从叶子结点到根结点路径上各结点的关键字,则根结点的关键字即为次小关键字。如此下去,可依次选出从小到大的全部关键字。 (3) 树形选择排序与直接选择排序相比较,其优点是从求第2个元素开始,从n-i+1个元素中不必进行n-i 次比较,只比较?log 2n ?次,比较次数远小于直接选择排序;其缺点是辅助储存空间大。 (4) 堆排序基本思想是:堆是n 个元素的序列,先建堆,即先选得一个关键字最大或最小的记录,然后与序列中最后一个记录交换,之后将序列中前n-1记录重新调整为堆(调堆的过程称为“筛选”), 再将堆顶记录和当前堆序列的最后一个记录交换,如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时,堆排序只需要一个记录大小供 交换用的辅助空间,调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较, 46. K1到K n是堆,在K n+1加入后,将K1..K n+1调成堆。设c=n+1,f=?c/2?,若K f<=K c,则调整完 成。否则,K f与K c交换;之后,c=f,f=?c/2?,继续比较,直到K f<=K c,或f=0,即为根结点,调整结束。 47. (1)①child=child+1; ②child/2 (2)不能,调为大堆:92,86,56,70,33,33,48,65,12,24 48. (1)不需要。因为建堆后R[1]到R[n]是堆,将R[1]与R[n]交换后,R[2]到R[n-1]仍是堆,故对R[1]到R[n-1]只需从R[1]往下筛选即可。 (2) 堆是n个元素的序列,堆可以看作是n个结点的完全二叉树。而树型排序是n个元素作叶子结点的完全二叉树。因此堆占用的空间小。调堆时,利用堆本身就可以存放输出的有序数据,只需要一个记录大小供交换用的辅助空间。排序后,heap数组中的关键字序列与堆是大堆还是小堆有关,若利用大堆,则为升序;若利用小堆则为降序。 49. 最高位优先(MSD)法:先对最高位关键字K0进行排序,将序列分成若干子序列,每个子序列中的记录都具有相同的K0值,然后,分别就每个子序列对关键字K1进行排序,按K1值不同再分成若干更小的子序列,……,依次重复,直至最后对最低位关键字排序完成,将所有子序列依次连接在一起,成为一个有序子序列。 最低位优先(LSD)法:先对最低位关键字K d-1进行排序,然后对高一级关键字K d-2进行排序,依次重复,直至对最高位关键字K0排序后便成为一个有序序列。进行排序时,不必分成子序列,对每个关键字都是整个序列参加排序,但对K i (0<=i 50. (1)冒泡排序(H,C,Q,P,A,M,S,R,D,F,X,Y) (2)初始步长为4的希尔排序(P,A,C,S,Q,D,F,X,R,H,M,Y) (3)二路归并排序(H,Q,C,Y,A,P,M,S,D,R,F,X) (4)快速排序(F,H,C,D,P,A,M,Q,R,S,Y,X) 初始建堆:(A,D,C,R,F,Q,M,S,Y,P,H,X) 51. (1)一趟希尔排序: 12,2,10,20,6,18,4,16,30,8,28 ( D=5) (2)一趟快速排序:6,2,10,4,8,12,28,30,20,16,18 (3)链式基数排序LSD [0][1][2][3][4][5][6][7][8][9] ↓↓↓↓↓ 分配 30 12 4 16 8 ↓↓↓↓ 10 2 6 28 ↓↓ 20 18 收集:→30→10→20→12→2→4→16→6→8→28→18 52. (1)2路归并第一趟:18,29,25,47,12,58,10,51;第二趟:18,25,29,47,10,12,51,58; 第三趟:10,12,18,25,29,47,51,58 (2)快速排序第一趟:10,18,25,12,29,58,51,47; 第二趟:10,18,25,12,29,47,51,88;第三趟:10,12,18,25,29,47,51,88 (3)堆排序建大堆:58,47,51,29,18,12,25,10; ①51,47,25,29,18,12,10,58;②47,29,25,10,18,12,51,58; ③29,18,25,10,12,47,51,58;④25,18,12,10,29,47,51,58; ⑤18,10,12,25,29,47,51,58;⑥12,10,18,25,29,47,51,58;⑦10,12,18,25,29,47,51,58 类似叙述:(1) ①设按3路归并 I/O次数=2*wpl=202次 ③④⑤略。 53. (1)当至多进行n-1趟起泡排序,或一趟起泡排序中未发生交换(即已有序)时,结束排序。 (2)希尔排序是对直接插入排序算法的改进,它从“记录个数少”和“基本有序”出发,将待排序的记录划分成几组(缩小增量分组),从而减少参与直接插入排序的数据量,当经过几次分组排序后,记录的排列已经基本有序,这个时候再对所有的记录实施直接插入排序。 (3)13,24,33,65,70,56,48,92,80,112 (4)采用树型锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次。(两两比较8次选出8个优胜,再两两比较4次选出4个优胜,半决赛两场,决赛一场,共比较了15次。将冠军的叶子结点改为最大值,均与兄弟比较,共4次选出亚军。) 54. (1)按LSD法→321→156→57→46→28→7→331→33→34→63 分配 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 321 33 34 156 57 28 331 63 46 7 收集→321→331→33→63→34→156→46→57→7→28 类似叙述(1) 略。 55. ①快速排序②冒泡排序③直接插入排序④堆排序 56. A.p[k]←j B.i←i+1 C.k=0 D.m←n E.m 57. 一趟快速排序:22,19,13,6,24,38,43,32 初始大堆:43,38,32,22,24,6,13,19 二路并归:第一趟:19,24,32,43,6,38,13,22 第二趟:19,24,32,43,6,13,22,38 第三趟:6,13,19,22,24,32,38,43 堆排序辅助空间最少,最坏情况下快速排序时间复杂度最差。 58. (1)排序结束条件为没有交换为止 第一趟奇数:35,70,33,65,21,24,33 第二趟偶数:35,33,70,21,65,24,33 第三趟奇数:33,35,21,70,24,65,33 第四趟偶数:33,21,35,24,70,33,65 第五趟奇数:21,33,24,35,33,70,65 第六趟偶数:21,24,33,33,35,65,70 第七趟奇数:21,24,33,33,35,65,70(无交换) 第八趟偶数:21,24,33,33,35,65,70(无交换) 结束 59. 设归并路数为k,归并趟数为s,则s=?log k100?,因?log k100?=3 ,所以k=5,即最少5 路归并。 60. 证明:由置换选择排序思想,第一个归并段中第一个元素是缓冲区中最小的元素,以后每选一个元素都不应小于前一个选出的元素,故当产生第一个归并段时(即初始归并段),缓冲区中m个元素中除最小元素之外,其他m-1个元素均大于第一个选出的元素,即当以后读入元素均小于输出元素时,初始归并段中也至少能有原有的m个元素。证毕。 61. 因 类似叙述 (1)加 62. 加5-(31-1)%(5-1)-1=2个虚段。 63. 内部排序中的归并排序是在内存中进行的归并排序,辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件,将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数,即归并的趟数。因为归并的趟数s=?log k m?,其中,m是归并段个数,k是归并路数。增大k和减少m都可减少归并趟数。应用中通过败者树进行多(k)路平衡归并和置换-选择排序减少m,来提高外部排序的效率。 64. 初始败者树 初 始归并段: R 1:3,19,31,51,61,71,100,101 R 2:9,17,19,20,30,50,55 R 3:6 类似叙述题略。 65. (1)4台磁带机:平衡归并只能用2路平衡归并,需归并?log 2650?=10趟。多步归并进行3路归并,按3 阶广义斐波那契序列。F 11<650 +f 10=149+81=230 t 3=f 11=149 (2) 多步归并排序前五趟归并的情况如下: 1步 2步 3步 4步 5步 注:m p 表示p 个长为m 单位的归并段 1149 表示149个长为1个单位的归并段。 类似叙述题略 类似叙述题略。 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("%d,%f",R[i].num,R[i].score); if(i%10==0) printf("\n");} }//SelectSort 6. typedef struct { int key; datatype info}RecType void CountSort(RecType a[],b[],int n) //计数排序算法,将a中记录排序放入b 中 { for(i=0;i { for(j=0,cnt=0;j