后向前一趟排序，得到一个最小值。 一趟：12,23,35,16,25,36,19,21,16,47
二趟：12,16,23,35,16,25,36,19,21,47 三趟：12,16,23,16,25,35,19,21,36,47 四趟：12,16,16,23,19,25,35,21,36,47 五趟：12,16,16,19,23,25,21,35,36,47 六趟：12,16,16,19,21,23,25,35,36,47 七趟：12,16,16,19,21,23,25,35,36,47 20. 对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初始是上升序。
21. 证明：起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到一个极值。由题假设知Rj在Ri之前且Kj>Ri，即说明Rj和Ri是反序；设对于Ri之前全部记录1—Ri-1(其中包括Kj)中关键字最大为Kmax，则Kmax≥Kj，故经过起泡排序前i-2次后，Ri-1的关键字一定为Kmax，又因Kmax≥Kj>Ri，故Ri-1和Ri为反序，由此可知Ri-1和Ri必定交换，证毕。
22.采用直接插入排序算法，因为记录序列已基本有序，直接插入排序比较次数少，且由于少量次序不对的记录与正确位置不远，使直接插入排序记录移动次数也相对较少，故选直接插入排序算法。 23. 各带标号语句的频度：(1)n (2)n-1 (3)(n+2)(n-1)/2 (4)n(n-1)/2 (5)n-1 时间复杂度O(n2), 属于直接选择排序。
24. 6, 13, 28, 39, 41, 72, 85, 20
i=1↑ m=4↑ r=7↑
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 21移动：21,07,39,10,65,14,61,17,50,[]
39移动：21,07,[],10,65,14,61,17,50,39 17移动：21,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 （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 一次调用：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(n2)。从10000个元素中选10个元素不能使用这种方法。而快速排序、插入排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。只有堆排序，在未结束全部排序前，可以有部分排序结果。建立堆后，堆顶元素就是最大（或最小，视大堆或小堆而定）元素，然后，调堆又选出次大（小）元素。凡要求在n个元素中选出k(k< 61 87 908 462 170 512 897 275 503 653 87 462 908 170 512 897 275 653 (2) 求次小值 908 87 170 275 87 170 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 71 73 71 72 23 71 73 71 ?2i?1.2(h?i)??i?h?12.(h?i)?i?2j?1.j?(2n)?j/2?4nj?1j 05 05 23 23 94 23 23 23 23 94 94 ∞ ∞ 68 68 68 16 16 05 05 68 72 71 73 71 23 23 16 16 16 16 ∞ 68 68 23 94