在待排序序列已有序的情况下就是如此 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向前移动,与其最终位置相反 但冒泡排序是稳定排序。快速排序中无这种现象 125,,22,34,15,4,76,66,100,8,14,20,2,5,1 设D=7 15;2,5,66;100,22,34,20,4,76,1 1,11,2,5,15,8,14,34,20,22,66,100,44,76,125 1,2,5,8,11,14,15,20,22,34,44,6,76,100,125 28.设待排序记录的个数为n,则快速排序的最小递归深度为 Logan h+1,最大递归深度n 29.平均性能最佳的排序方法是快速排序,该排序方法不稳定 初始序列:50,10,50,40,45,85,80 趟排序:[45,10,50,40]50[85,80]二趟排序:[40,10]45[50]50[80] 三趟排序:10,40,45,50,50,80,85 30.快速排序 31.(1)在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2-1, 那么第一遍划分得到两个长度均为n/2的子文件,第二遍划分得到4个长度均为Ln/4的 子文件,以此类推,总共进行k=1og2(n+1)遍划分,各子文件的长度均为1,排序完毕。当 n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件(长度均为3, k=2)进行排序,各需2次,共10次即可。 (2)在最好情况下快速排序的原始序列实例:4,1,3,2,6,5,7 (3)在最坏情况下,若每次用来划分的记录的关键字具有最大值(或最小值),那么只能 得到左(或右)子文件,其长度比原长度少1。因此,若原文件中的记录按关键字递减次序排 列,而要求排序后按递增次序排列时,快速排序的效率与冒泡排序相同,其时间复杂度为 0(n2)。所以当n=7时,最坏情况下的比较次数为21次 (4)在最坏情况下快速排序的初始序列实例:7,6,5,4,3,2,1,要求按递增排序。 32.该排序方法为快速排序
在待排序序列已有序的情况下就是如此。 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.不是。因为当序列已有序时,快速排序将退化成冒泡排序,时间复杂度为0(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 21,07,17,10,65,14,61,[],50,39 移动: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 ≤ji,i≮k≤t),然后再递归地将R[s.i-1]和R[i+1..t]进行快速排序。快速排序在记录有 序时蜕变为冒泡排序,可用“三者取中”法改善其性能,避免最坏情况的出现。具体排序实 例不再解答 35.(1)不可以,若m+1到n之间关键字都大于m的关键字时,<=k可将j定位到m上,若 为<k则j将定位到m-1上,将出界线,会造成错误。 (2)不稳定,例如2,1,2′,(m=1,n=3)对2,1,2排序,完成会变成1,2’,2 (3)各次调用 sorth的结果如下: 次调用m=1,n=10 4,18,22, 二次调用m=7,n=1011,3,16,4,18,22,40,30,58,60j=9(右部) 次调用m=10,n=10不变,返回m=7,n=811,3,16,4,18,22,30,40,58,60j=8 四次调用m=9,n=8不变,返回m=7,n=7返回m=1,n=5 4,3,11,16,18,22,30,40,58,60j=3(左部) 五次调用m=1,n=23,4,11,16,18,22,30,40,58,60j=2 六次调用m=1,n=1不变,返回m3,n=2返回m4,n=5 3,4,11,16,18,22,30,40,58,60j=4 七次调用m=4,n=3不变,返回注:一次划分后,左、右两部分调用算两次) 4)最大栈空间用量为0(10gn) 36.在具有n个元素的集合中找第k(1≤k≤n)个最小元素,应使用快速排序方法。其基 本思想如下:设n个元素的集合用一维数组表示,其第一个元素的下标为1,最后一个元素 下标为n。以第一个元素为“枢轴”,经过快速排序的一次划分,找到“枢轴”的位置i,若 ik,则该位置的元素即为所求;若ik,则在1至i-1间继续进行快速排序的划分;若i<k, 则在i+1至n间继续进行快速排序的划分。这种划分一直进行到i为止,第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,合并后子文件长
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<i,i<k≤t),然后再递归地将 R[s..i-1]和 R[i+1..t]进行快速排序。快速排序在记录有 序时蜕变为冒泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。具体排序实 例不再解答。 35．（1）不可以，若 m+1 到 n 之间关键字都大于 m 的关键字时,<=k 可将 j 定位到 m 上，若 为<k 则 j 将定位到 m-1 上，将出界线，会造成错误。 （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， 则在 i+1 至 n 间继续进行快速排序的划分。这种划分一直进行到 i=k 为止，第 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,9 (6)12,3,26,45,61,70,87,97 (1)是大堆;(2)是大堆:(4)是小堆 (3)不是堆,调成大堆100,98,66,85,80,60,40,77,82,10,2 类似叙述(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次, 其时间复杂度是0(n2)。从1000个元素中选10个元素不能使用这种方法。而快速排序、插 入排序、归并排序、基数排序等时间性能好的排序,都要等到最后才能确定各元素位置。只 有堆排序,在未结束全部排序前,可以有部分排序结果。建立堆后,堆顶元素就是最大(或 最小,视大堆或小堆而定)元素,然后,调堆又选出次大(小)元素。凡要求在n个元素中 选出k(k<<n,k>2)个最大(或最小)元素,一般均使用堆排序。因为堆排序建堆比较次数至 多不超过4n,对深度为k的堆,在调堆算法中进行的关键字的比较次数至多为2(k-1)次,且 辅助空间为0(1)。 41.(1)建小堆 503 51 (2)求次小值 :62八(512(897 462(512 897 42.用堆排序方法,详见第40题的分析。从序列{59,11,26,34,14,91,25}得到{11, 7,25}共用14次比较。其中建堆输出11比较8次,调堆输出17和25各需要比较4次和 2次 类似本的另外叙述题的解答: )堆排序,分析同前,共20+5+4+5=34次比较。 43.对具体例子的手工堆排序略 堆与败者树的区别:堆是n个元素的序列,在向量中存储,具有如下性质
度为 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<<n,k>2)个最大（或最小）元素，一般均使用堆排序。因为堆排序建堆比较次数至 多不超过 4n,对深度为 k 的堆，在调堆算法中进行的关键字的比较次数至多为 2(k-1)次，且 辅助空间为 O(1)。 41. (1)建小堆 (2) 求次小值 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 个元素的序列，在向量中存储，具有如下性质： 503 653 908 275 462 512 897 87 170 61 908 653 61 503 462 512 897 275 170 87 503 653 61 275 462 5122 897 87 170 908 275 653 462 61 908 170 897 87 512 503
或 k≥k2 k,≤k2 1(i=1,2,…,Ln/2」 由于堆的这个性质中下标i和2i、2i+1的关系,恰好和完全二叉树中第i个结点和其 子树结点的序号间的关系一致,所以堆可以看作是n个结点的完全二叉树。而败者树是由参 加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶(双亲)结点中存放的是两个 子结点中的败者数据,而让胜者去参加更高一级的比赛。另外,还需增加一个结点,即结点 0,存放比赛的全局获胜者 44.(1)堆的存储是顺序的 (2)最大值元素一定是叶子结点,在最下两层上 (3)在建含有n个元素、深度为h的堆时,其比较次数不超过4n,推导如下: 由于第i层上的结点数至多是2-,以它为根的二叉树的深度为h-i+1,则调用Ln/2次 筛选算法时总共进行的关键字比较次数不超过下式之值: ∑212h-0)=∑2(h-)=∑21js(2n∑j/2s4n 45.(1) 冠军 (2)树形选择排序基本思想:首先对n个待排序记录的关键字进行两两比较,从中选出 「n/2个较小者再两两比较,直到选出关键字最小的记录为止,此为一趟排序。我们将一趟 选出的关键字最小的记录称为“冠军”,而“亚军”是从与“冠军”比较失败的记录中找出 具体做法为:输出“冠军”后,将其叶子结点关键字改为“最大值”,然后从该叶子结点开 始,和其左(或右)兄弟比较,修改从叶子结点到根结点路径上各结点的关键字,则根结点 的关键字即为次小关键字。如此下去,可依次选出从小到大的全部关键字 (3)树形选择排序与直接选择排序相比较,其优点是从求第2个元素开始,从ni+1个 元素中不必进行ni次比较,只比较 Logan次,比较次数远小于直接选择排序;其缺点是 辅助储存空间大 (4)堆排序基本思想是:堆是n个元素的序列,先建堆,即先选得一个关键字最大或最 小的记录,然后与序列中最后一个记录交换,之后将序列中前n-1记录重新调整为堆(调堆 的过程称为“筛选”),再将堆顶记录和当前堆序列的最后一个记录交换,如此反复直至排序 结東。优点是在时间性能与树形选择排序属同一量级的同时,堆排序只需要一个记录大小供
+ 2 +1 2 2 1 2 i i i i i i i i k k k k k k k k 或 （i=1,2,…,n/2） 由于堆的这个性质中下标 i 和 2i、2i+1 的关系，恰好和完全二叉树中第 i 个结点和其 子树结点的序号间的关系一致，所以堆可以看作是 n 个结点的完全二叉树。而败者树是由参 加比赛的 n 个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个 子结点中的败者数据，而让胜者去参加更高一级的比赛。另外，还需增加一个结点，即结点 0，存放比赛的全局获胜者。 44.（1）堆的存储是顺序的 （2）最大值元素一定是叶子结点，在最下两层上。 （3）在建含有 n 个元素、深度为 h 的堆时，其比较次数不超过 4n，推导如下： 由于第 i 层上的结点数至多是 2 i-1 ,以它为根的二叉树的深度为 h-i+1，则调用 n/2 次 筛选算法时总共进行的关键字比较次数不超过下式之值： h i h i j n j n h j j i h i h h j i i h j 2 .2( ) 2 .( ) 2 . (2 ) / 2 4 1 1 1 1 1 1 1 1 1 − = − = − = − = − − − = − = 45.(1) (2)树形选择排序基本思想：首先对 n 个待排序记录的关键字进行两两比较，从中选出 n/2 个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟 选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出， 具体做法为：输出“冠军”后，将其叶子结点关键字改为“最大值”，然后从该叶子结点开 始，和其左（或右）兄弟比较，修改从叶子结点到根结点路径上各结点的关键字，则根结点 的关键字即为次小关键字。如此下去，可依次选出从小到大的全部关键字。 (3) 树形选择排序与直接选择排序相比较，其优点是从求第 2 个元素开始，从 n-i+1 个 元素中不必进行 n-i 次比较，只比较 log2n 次，比较次数远小于直接选择排序；其缺点是 辅助储存空间大。 (4) 堆排序基本思想是：堆是 n 个元素的序列，先建堆，即先选得一个关键字最大或最 小的记录，然后与序列中最后一个记录交换，之后将序列中前 n-1 记录重新调整为堆（调堆 的过程称为“筛选”），再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序 结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供 05 23 05 71 23 16 05 72 73 71 23 94 16 05 68 16 23 16 71 23 16 68 72 73 71 23 94 16 ∞ 68 23 23 68 71 23 94 68 72 73 71 23 94 ∞ ∞ 68