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

(2)树形选择排序基本思想:首先对n个待排序记录的关键字进行两两比较,从中选出?n/2?个较小者再两两比较,直到选出关键字最小的记录为止,此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军”,而“亚军”是从与“冠军”比较失败的记录中找出,具体做法为:输出“冠军”后,将其叶子结点关键字改为“最大值”,然后从该叶子结点开始,和其左(或右)兄弟比较,修改从叶子结点到根结点路径上各结点的关键字,则根结点的关键字即为次小关键字。如此下去,可依次选出从小到大的全部关键字。

(3) 树形选择排序与直接选择排序相比较,其优点是从求第2个元素开始,从n-i+1个元素中不必进行n-i次比较,只比较?log2n?次,比较次数远小于直接选择排序;其缺点是辅助储存空间大。

(4) 堆排序基本思想是:堆是n个元素的序列,先建堆,即先选得一个关键字最大或最小的记录,然后与序列中最后一个记录交换,之后将序列中前n-1记录重新调整为堆(调堆的过程称为“筛选”),再将堆顶记录和当前堆序列的最后一个记录交换,如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时,堆排序只需要一个记录大小供交换用的辅助空间,调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较,

46. K1到Kn是堆,在Kn+1加入后,将K1..Kn+1调成堆。设c=n+1,f=?c/2?,若Kf<=Kc,则调整完成。否则,

Kf与Kc交换;之后,c=f,f=?c/2?,继续比较,直到Kf<=Kc,或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进行排序,将序列分成若干子序列,每个子序列中的记录都具有相同的K值,然后,分别就每个子序列对关键字K进行排序,按K值不同再分成若干更小的子序列,??,依次重复,直至最后对最低位关键字排序完成,将所有子序列依次连接在一起,成为一个有序子序列。

d-1d-2

最低位优先(LSD)法:先对最低位关键字K进行排序,然后对高一级关键字K进行排序,依次重复,直至对最高位关键字K0排序后便成为一个有序序列。进行排序时,不必分成子序列,对每个关键字都是整个序列参加排序,但对Ki (0<=i

(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

0

1

1

↓ ↓

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 9 类似叙述:(1) ①设按3路归并 I/O次数=2*wpl=202次 ② 10 5 4 7 18 52 ③④⑤ 略。

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

3 6 7 8 24 5 9 3 7 6 4 8 10 类似叙述(1) 略。

55. ①快速排序 ②冒泡排序 ③直接插入排序 ④堆排序

56. A.p[k]←j B.i←i+1 C.k=0 D.m←n E.m

二路并归:第一趟: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=?logk100?,因?logk100?=3 ,所以k=5,即最少5路归并。 60. 证明:由置换选择排序思想,第一个归并段中第一个元素是缓冲区中最小的元素,以后每选一个元素都不应小于前一个选出的元素,故当产生第一个归并段时(即初始归并段),缓冲区中m个元素中除最小元素之外,其他m-1个元素均大于第一个选出的元素,即当以后读入元素均小于输出元素时,初始归并段中也至少能有原有的m个元素。证毕。 2 3 61. 因(8-1)%(3-1)=1,故第一次归并 时加一个“虚段”。 5 4 5 7 9 10 WPL=5*3+(4+5+7+9+10)*2+18*1 =103

类似叙述:

(1)加4-(12-1)%(4-1)-1=1个虚段 3 6 8

9 17 18 20 30 44 60 62 14 26 58 18 64 196 68 85 WPL=(3+6+8)*3+(9+18+20+30+44+60+62)*2+(68+85)*1 =690 (2)(3)(4)略。 62. 加5-(31-1)%(5-1)-1=2个虚段。 12 2 2 2 2 2 2 2 2 413 3 3 3 3 3 3 3 3 5 5 12 6 12 10 12 12 15 19 20 20 5 5 5 5 5 52 20 78 25 总读写次数为2*wpl=800次。 类似叙述(1)(2)(3)略。 261 63. 内部排序中的归并排序是在内存中进行的归并排序,辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件,将每个子文件中记录读入内存后的排序方法可采用多种

内排序方法。外部排序的效率主要取决于读写外存的次数,即归并的趟数。因为归并的趟数s=?logkm?,其中,m是归并段个数,k是归并路数。增大k和减少m都可减少归并趟数。应用中通过败者树进行多(k)路平衡归并和置换-选择排序减少m,来提高外部排序的效率。

64. 初始败者树

1 3 4 初始归并段: R1:3,19,31,51,61,71,100,101

R2:9,17,19,20,30,50,55,90 R3:6

0

5 类似叙述题略。 71 3 2 1 1

65. (1)4台磁带机:平衡归并只能用2路平衡归并,需归并?log2650?=10趟。多步归并进行3路归并,按3阶广义斐波那契序列。F11<650

2步

t3=f11=149

3步

61 1 19 1 51 1 101 1 T1 1149+181+144 T2 1149+181 T3 1149T1 181+144 T2 181 T3 T1 144 T2 81T1 4步

T2 944 T3 537 T3 5 T4 T4 3149 T4 368 T4 324 5步

注:mp表示p个长为m单位的归并段 1149表示149个长为1个单位的归并段。

T1 1724 T2 920 T3 513 T4 3 4 6 T1 1711 T2 97 T3 T4 3113 7 8 9 类似叙述题略

C B A E D 66. (1) (2)