merge( r, S, 1); EnQueue( 0, 1); end end; 9-18若设待排序关键码序列有n个关键码,n是一个完全平方数。将它们划分为块,每 块有个关键码。这些块分属于两个有序表。下面给出一种O(1)空间的非递归归并算法 stepl:在两个待归并的有序表中从右向左总共选出个具有最大值的关键码 step2:若设在 stepl选出的第2个有序表中的关键码有s个,则从第1个有序表选出的 关键码有-s个。将第2个有序表选出的s个关键码与第1个有序表选出的关键码左边的 同样数目的关键码对调 step3:交换具有最大√个关键码的块与最左块(除非最左块就是具有最大√个关键码 的块)。对最右块进行排序 step4:除去具有最大n个关键码的块以外,对其它的块根据其最后的关键码按非递减 顺序排序 step5:设置3个指针,分别位于第1块、第2块和第3块的起始位置,执行多次 substep, 直到3个指针都走到第块为止。此时前-1块已经排好序。 subStep所做的工作是比较第2个指针与第3个指针所指关键码,将值小的与第 1个指针所指关键码对调,相应指针前进1个关键码位置 step6:对最后第G块中最大的√个关键码进行排序 (1)设有16个关键码,分别存放于两个有序表{10,12,14,16,18,20,2,25}和11,13,15 17,19,21,23,24}中,试根据上面的描述,写出排序的全过程,并说明它具有时间复杂度On) 和空间复杂度O(1) (2)编写相应的算法。要求两个待排序有序表的长度可以不同,但每一个表的长度都是 √n的倍数。 (3)假设两个有序表分别为(x,…;xm)和(xm+1,…;x),编写一个算法归并这两个有序 表,得到(x1,…,xn)。设S=n 9-19试编写一个算法,将对象序列(x,x2…,x)循环右移p个位置,0≤p≤no要求该算法 的时间复杂度为On)而空间复杂度为O(1)。 【解答】 9-20在什么条件下,MSD基数排序比LSD基数排序效率更高? 【解答】 9-21在已排好序的序列中,一个对象所处的位置取决于具有更小关键码的对象的个数。基 于这个思想,可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域 count, 用于存放在已排好序的序列中该对象前面的对象数目,最后依com域的值,将序列重新排 列,就可完成排序。试编写一个算法,实现计数排序。并说明对于一个有n个对象的序列, 为确定所有对象的 count值,最多需要做mn-1)/2次关键码比较。 【解答】 3661428← 待排序的表 始状态 第1趟排序结果 第2趟排序结果 第3趟排序结果merge( r, s, t ); EnQueue( Q, t ); end end; 9-18 若设待排序关键码序列有 n 个关键码，n 是一个完全平方数。将它们划分为 n 块，每 块有 n 个关键码。这些块分属于两个有序表。下面给出一种 O(1)空间的非递归归并算法： step1: 在两个待归并的有序表中从右向左总共选出 n 个具有最大值的关键码； step2: 若设在 step1 选出的第 2 个有序表中的关键码有 s 个，则从第 1 个有序表选出的 关键码有 n - s 个。将第 2 个有序表选出的 s 个关键码与第 1 个有序表选出的关键码左边的 同样数目的关键码对调； step3: 交换具有最大 n 个关键码的块与最左块(除非最左块就是具有最大 n 个关键码 的块)。对最右块进行排序； step4: 除去具有最大 n 个关键码的块以外，对其它的块根据其最后的关键码按非递减 顺序排序； step5: 设置 3 个指针，分别位于第 1 块、第 2 块和第 3 块的起始位置，执行多次 substep， 直到 3 个指针都走到第 n 块为止。此时前 n −1 块已经排好序。  subStep 所做的工作是比较第 2 个指针与第 3 个指针所指关键码，将值小的与第 1 个指针所指关键码对调，相应指针前进 1 个关键码位置。 step6: 对最后第 n 块中最大的 n 个关键码进行排序。 (1) 设有 16 个关键码，分别存放于两个有序表{10, 12, 14, 16, 18, 20, 22, 25}和{11, 13, 15, 17, 19, 21, 23, 24}中，试根据上面的描述，写出排序的全过程，并说明它具有时间复杂度 O(n) 和空间复杂度 O(1)。 (2) 编写相应的算法。要求两个待排序有序表的长度可以不同，但每一个表的长度都是 n 的倍数。 (3) 假设两个有序表分别为(x1, …, xm)和(xm+1, …, xn)，编写一个算法归并这两个有序 表，得到(x1, …, xn)。设 s = n 。 9-19 试编写一个算法，将对象序列(x1, x2, …, xn)循环右移 p 个位置，0  p  n。要求该算法 的时间复杂度为 O(n)而空间复杂度为 O(1)。 【解答】 9-20 在什么条件下，MSD 基数排序比 LSD 基数排序效率更高？ 【解答】 9-21 在已排好序的序列中，一个对象所处的位置取决于具有更小关键码的对象的个数。基 于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域 count， 用于存放在已排好序的序列中该对象前面的对象数目，最后依 count 域的值，将序列重新排 列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有 n 个对象的序列， 为确定所有对象的 count 值，最多需要做 n(n-1)/2 次关键码比较。 【解答】 0 0 0 0 初始状态 2 1 0 0 第 1 趟排序结果 3 0 0 第 2 趟排序结果 0 1 第 3 趟排序结果 35 66 14 28 14 28 35 66 待排序的表