交换用的辅助空间,调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比 较 46.K到K是堆,在K1加入后,将K..K1调成堆。设C=n+1,f=c/2,若K<=K,则调整完 成。否则,K与K交换:之后,c=f,f=c/2,继续比较,直到K<=,或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]与Rn]交换后,R[2]到R[n-1]仍是 堆,故对R[1]到R[n-1]只需从R[1]往下筛选即可 (2)堆是n个元素的序列,堆可以看作是n个结点的完全二叉树。而树型排序是n个元 素作叶子结点的完全二叉树。因此堆占用的空间小。调堆时,利用堆本身就可以存放输出的 有序数据,只需要一个记录大小供交换用的辅助空间。排序后,heap数组中的关键字序列 与堆是大堆还是小堆有关,若利用大堆,则为升序:若利用小堆则为降序。 49.最高位优先(MSD)法:先对最高位关键字K进行排序,将序列分成若干子序列,每个 子序列中的记录都具有相同的K°值,然后,分别就每个子序列对关键字K进行排序,按K 值不同再分成若干更小的子序列,…,依次重复,直至最后对最低位关键字排序完成,将 所有子序列依次连接在一起,成为一个有序子序列。 最低位优先(LSD)法:先对最低位关键字Kˉ进行排序,然后对高一级关键字K进行 排序,依次重复,直至对最高位关键字K排序后便成为一个有序序列。进行排序时,不必 分成子序列,对每个关键字都是整个序列参加排序,但对K(0<=i<d-1)排序时,只能用稳 定的排序方法。另一方面,按LSD进行排序时,可以不通过关键字比较实现排序,而是通过 若干次“分配”和“收集”来实现排序 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[o][1][2][3][4][5][6][7][8][9] 收集:→30→10→20→12→2→4→16→6→8→28→18 (1)2路归并第一趟:18,29,25,47,12,58,10,51;第二趟:18,25,29,47,10,12,51,58 第三趟:10,12,18,25,29, (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交换用的辅助空间，调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比 较， 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）法：先对最高位关键字 K 0 进行排序，将序列分成若干子序列，每个 子序列中的记录都具有相同的 K 0 值，然后，分别就每个子序列对关键字 K 1 进行排序，按 K 1 值不同再分成若干更小的子序列，……，依次重复，直至最后对最低位关键字排序完成，将 所有子序列依次连接在一起，成为一个有序子序列。 最低位优先（LSD）法：先对最低位关键字 K d-1 进行排序，然后对高一级关键字 K d-2 进行 排序，依次重复，直至对最高位关键字 K 0 排序后便成为一个有序序列。进行排序时，不必 分成子序列，对每个关键字都是整个序列参加排序，但对 K i (0<=i<d-1)排序时，只能用稳 定的排序方法。另一方面，按 LSD 进行排序时，可以不通过关键字比较实现排序，而是通过 若干次“分配”和“收集”来实现排序。 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；