20<39 i=1↑m=2↑r=3↑
20>13 i=3 r=3 m=3
20<28 r=2 i=3
将r+1(即第3个)后的元素向后移动，并将20放入r+1处，结果为6,13,20,28,39,41,72,85。
（1）使用二分法插入排序所要进行的比较次数，与待排序的记录的初始状态无关。不论待排序序列是否有序，已形成的部分子序列是有序的。二分法插入首先查找插入位置，插入位置是判定树查找失败的位置。失败位置只能在判定树的最下两层上。
（2）一些特殊情况下，二分法插入排序要比直接插入排序要执行更多的比较。例如，在待排序序列已有序的情况下就是如此。 25. (1)直接插入排序 第一趟
第四趟
(3)[8,3],2,5,9,1,6 第二趟 (2)[8,3,2],5,9,1,6 (5)[8,5,3,2],9,1,6
(9)[9,8,5,3,2],1,6 第五趟 (1)[9,8,5,3,2,1],6
第第
三六
趟趟
(6)[9,8,6,5,3,2,1]
(2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束）
(9)[9],3,2,5,8,1,6 第二趟 (8)[9,8],2,5,3,1,6 (6)[9,8,6],5,3,1,2
(5)[9,8,6,5],3,1,2 第五趟 (3)[9,8,6,5,3],1,2
第第
三六
趟趟
第一趟
第四趟
(2)[9,8,6,5,3,2],1
(3)直接插入排序是稳定排序，直接选择排序是不稳定排序。
26.这种看法不对。本题的叙述与稳定性的定义无关，不能据此来判断排序中的稳定性。例如 5,4,1,2,3在第一趟冒泡排序后得到4,1,2,3,5。其中4 向前移动，与其最终位置相反。但冒泡排序是稳定排序。快速排序中无这种现象。
27. 125，11，22，34，15，44，76，66，100，8，14，20，2，5，1 设D=7
1，11，8，14，15，2，5，66，100，22，34，20，44，76，125 D=3
1，11，2，5，15，8，14，34，20，22，66，100，44，76，125 D=1 1，2，5，8，11，14，15，20，22，34，44，66，76，100，125
28. 设待排序记录的个数为n，则快速排序的最小递归深度为?log2n?+1，最大递归深度n。 29. 平均性能最佳的排序方法是快速排序，该排序方法不稳定。
初始序列: 50，10，50，40，45，85，80
一趟排序: [45，10，50，40] 50 [85，80] 二趟排序: [40，10] 45 [50] 50 [80] 85
三趟排序: 10，40，45，50，50，80，85 30. 快速排序。
31. (1) 在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k-1，那么第一遍划分得到两个长度均为?n/2?的子文件，第二遍划分得到4个长度均为?n/4?的子文件，以此类推，总共进行k=log2(n+1)遍划分，各子文件的长度均为1，排序完毕。当
n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件（长度均为3，k=2）进行排序，各需2次，共10次即可。
(2) 在最好情况下快速排序的原始序列实例：4,1,3,2,6,5,7。 (3) 在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右)子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为O(n2)。所以当n=7时，最坏情况下的比较次数为21次。
(4) 在最坏情况下快速排序的初始序列实例： 7,6,5,4,3,2,1，要求按递增排序。 32.该排序方法为快速排序。
33. 不是。因为当序列已有序时，快速排序将退化成冒泡排序，时间复杂度为O(n2)。当待排序序列无序，使每次划分完成后，枢轴两侧子文件长度相当，此时快速排序性能最好。 34. 初始序列：[28],07,39,10,65,14,61,17,50,21 2121,07,39,10,65,14,61,17,50,[]
39移动：21,07,[],10,65,14,61,17,50,39 1721,07,17,10,65,14,61,[],50,39
65移动：21,07,17,10,[],14,61,65,50,39 14
移动：移动：移动：
21,07,17,10,14,[28],61,65,50,39 类似本题的另外叙述题的解答： （1）：快速排序思想：首先将待排序记录序列中的所有记录作为当前待排序区域，以第一个记录的关键字作为枢轴（或支点）（pivot），凡其关键字不大于枢轴的记录均移动至该记录之前，凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t],且R[j].key≤R[i].key≤R[k].key(s≤j 35．（1）不可以，若m+1到n之间关键字都大于m的关键字时,<=k可将j定位到m上，若为 （2）不稳定，例如2，1，2′，（m=1,n=3）对2，1，2′排序，完成会变成1，2′，2。 （3）各次调用qsort1的结果如下： 一次调用m=1,n=10 11,3,16,4,18,22,58,60,40,30 j=6 二次调用m=7,n=10 11,3,16,4,18,22,40,30,58,60 j=9 (右部) 三次调用m=10,n=10 不变，返回 m=7,n=8 11,3,16,4,18,22,30,40,58,60 j=8 四次调用m=9,n=8 不变，返回 m=7,n=7 返回 m=1,n=5 4,3,11,16,18,22,30,40,58,60 j=3（左部） 五次调用m=1,n=2 3,4,11,16,18,22,30,40,58,60 j=2 六次调用m=1,n=1 不变，返回 m=3,n=2 返回 m=4,n=5 3,4,11,16,18,22,30,40,58,60 j=4 七次调用m=4,n=3 不变，返回 （注：一次划分后，左、右两部分调用算两次） （4）最大栈空间用量为O(logn)。 36. 在具有n个元素的集合中找第k（1≤k≤n）个最小元素，应使用快速排序方法。其基本思想如下：设n个元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i，若i=k，则该位置的元素即为所求；若i>k，则在1至i-1间继续进行快速排序的划分；若i 素就是第k（1≤k≤n）个最小元素。 37. 快速排序各次调用结果： 一次调用：18,36,77,42,23,65,84,10,59,37,61,98 二次调用：10,18,77,42,23,65,84,36,59,37,61,98 三次调用：10,18,61,42,23,65,37,36,59,77,84,98 归并排序各次调用结果： 一次调用36,98,42,77,23,65,10,84,37,59,18,61, (子文件长度为1，合并后子文件长度为2) 二次调用36,42,77,98,10,23,65,84,18,37,59,61 (子文件长度为2，合并后子文件长度为4) 三次调用10,23,36,42,65,77,84,98,18,37,59,61 (第一子文件长度8，第二子文件长度为4) 38. 建立堆结构:97,87,26,61,70,12,3,45 (2)70,61,26,3,45,12,87,97 (4)45,12,26,3,61,70,87,97 (6)12,3,26,45,61,70,87,97 39. (1)是大堆； (2)是大堆；（4）是小堆； (3)不是堆，调成大堆 100，98，66，85，80，60，40，77，82，10，20 类似叙述(1):不是堆 调成大顶堆 92，86，56，70，33，33，48，65，12 (2)①是堆 ②不是堆 调成堆 100，90，80，25，85，75，60，20，10，70，65，50 (3)①是堆 ②不是堆 调成大堆21，9，18，8，4，17，5，6（图略） (4):略 40. 在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大（或最小）元素，并加入到已有的有序子序列中，但要比较n-1次。选次大元素要再比较n-2次,其时间复杂度是O(n)。从10000个元素中选10个元素不能使用这种方法。而快速排序、插入排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。只有堆排序，在未结束全部排序前，可以有部分排序结果。建立堆后，堆顶元素就是最大（或最小，视大堆或小堆而定）元素，然后，调堆又选出次大（小）元素。凡要求在n个元素中选出k(k< 61 87 908 462 170 2 503 512 897 275 503 653 87 61 170 462 908 512 897 275 653 (2) 求次小值 275 503 653 908 87 462 61 170 5122 897 503 908 653 61 275 87 170 462 512 897 42. 用堆排序方法，详见第40题的分析。从序列{59，11，26，34，14，91，25}得到{11，17，25}共用14次比较。其中建堆输出11比较8次，调堆输出17和25各需要比较4次和2次。 类似本题的另外叙述题的解答： （1）堆排序，分析同前，共20+5+4+5=34 次比较。 43. 对具体例子的手工堆排序略。 堆与败者树的区别：堆是n个元素的序列，在向量中存储，具有如下性质： ?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层上的结点数至多是2i-1,以它为根的二叉树的深度为h-i+1，则调用?n/2?次筛选算法时总共进行的关键字比较次数不超过下式之值： 11h?1h?1h?j? i?h?1 45.(1) 72 72 2i?1.2(h?i)??i?h?12.(h?i)?i?2j?1.j?(2n)?j/2?4nj?1j 05 23 71 73 71 23 23 94 23 23 71 73 71 23 23 94 94 ∞ ∞ 68 68 68 16 16 05 05 05 68 72 71 73 71 23 23 16 16 16 16 ∞ 68 68 23 94 (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值不同再分成若干更小的子序列，??，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。 最低位优先（LSD）法：先对最低位关键字Kd-1进行排序，然后对高一级关键字Kd-2进行排序，依次重复，直至对最高位关键字K0排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对Ki (0<=i 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 排序 0 1 1 ↓ ↓ 20 18 收集：→30→10→20→12→2→4→16→6→8→28→18