loading?ki?k2i??ki?k2i?1或?ki?k2i??ki?k2i?1 （i=1,2,?,?n/2?）
由于堆的这个性质中下标i和2i、2i+1的关系，恰好和完全二叉树中第i个结点和其子树结点的序号间的关系一致，所以堆可以看作是n个结点的完全二叉树。而败者树是由参加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个子结点中的败者数据，而让胜者去参加更高一级的比赛。另外，还需增加一个结点，即结点0，存放比赛的全局获胜者。 44.（1）堆的存储是顺序的
（2）最大值元素一定是叶子结点，在最下两层上。
（3）在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：
i-1
由于第i层上的结点数至多是2,以它为根的二叉树的深度为h-i+1，则调用?n/2?次筛选算法时总共进行的关键字比较次数不超过下式之值：
i?h?1?2.2(h?i)?i?11i?h?1j2.(h?i)?2.j?(2n)j/2?4n???ih?jj?1j?11h?1h?1
45.(1) 05 16
05 23 16 23 16 16 23 05 71 23 71
72 68 72 73 71 23 94 16 05 73 71 23 94 16 ∞
23 68 23
94 68 23 71
72 68 73 71 23 94 ∞ ∞
(2)树形选择排序基本思想：首先对n个待排序记录的关键字进行两两比较，从中选出?n/2?个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出，具体做法为：输出“冠军”后，将其叶子结点关键字改为“最大值”，然后从该叶子结点开始，和其左（或右）兄弟比较，修改从叶子结点到根结点路径上各结点的关键字，则根结点的关键字即为次小关键字。如此下去，可依次选出从小到大的全部关键字。
(3) 树形选择排序与直接选择排序相比较，其优点是从求第2个元素开始，从n-i+1个元素中不必进行n-i次比较，只比较?log2n?次，比较次数远小于直接选择排序；其缺点是辅助储存空间大。
(4) 堆排序基本思想是：堆是n个元素的序列，先建堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n-1记录重新调整为堆（调堆的过程称为“筛选”），再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供
68 68 交换用的辅助空间，调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较， 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数组中的关键字序列与堆是大堆还是小堆有关，若利用大堆，则为升序；若利用小堆则为降序。
0
49. 最高位优先（MSD）法：先对最高位关键字K进行排序，将序列分成若干子序列，每个
011
子序列中的记录都具有相同的K值，然后，分别就每个子序列对关键字K进行排序，按K值不同再分成若干更小的子序列，??，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。
d-1d-2
最低位优先（LSD）法：先对最低位关键字K进行排序，然后对高一级关键字K进行
0
排序，依次重复，直至对最高位关键字K排序后便成为一个有序序列。进行排序时，不必
i
分成子序列，对每个关键字都是整个序列参加排序，但对K (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 ↓ ↓ 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；⑦ 9 10,12,18,25,29,47,51,58 类似叙述：(1) ①设按3路归并 I/O次数=2*wpl=202次 ② 4 4 3 8 3 7 7 5 6 7 8 9 6 10 18 24 5 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 类似叙述(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=?logk100?，因?logk100?=3 ，所以k=5,即最少5 10 路归并。 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 14 26 类似叙述： (1)加4-(12-1)%(4-1)-1=1个虚段 58 3 6 8 17 9 18 20 30 44 60 62 64 196 WPL=(3+6+8)*3+(9+18+20+30+44+60+62)*2+(68+85)*1 413 =690 (2)(3)(4)略。 62. 加5-(31-1)%(5-1)-1=2个虚段。 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 5 5 12 12 6 10 15 19 12 12 20 12 18 68 85 5 5 5 5 5 20 52 78 25 20 总读写次数为2*wpl=800次。 261 类似叙述(1)(2)(3)略。 63. 内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。因为归并的趟数s=?logkm?,其中，m是归并段个数，k是归并路数。增大k和减少m都可减少归并趟数。应用中通过败者树进行多（k）路平衡归并和置换-选择排序减少m，来提高外部排序的效率。 64. 初始败者树 1 初始归并段： 3 R1:3,19,31,51,61,71,100,101 R2:9,17,19,20,30,50,554 0 2 5 71 1 101 3 1 61 19 51