发布时间 : 星期日 文章第十章排序参考答案更新完毕开始阅读f1d379da50e2524de5187ecb
(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)