《计算机算法-设计与分析导论》课后习题答案

《《计算机算法-设计与分析导论》课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、4.1：在我们所了解的早期排序算法Z中有一种叫做Maxsort的算法。它的工作流程如2首先在未排序序列(初始时为整个序列)中选择其中最大的元索max,然后将该元索同未排序序列中的最后一个元素交换。这时，max元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max□经不在未排序序列之中了。重复上述过程直到完成整个序列的排序。(a)写出Maxsort算法。其中待排序序列为E,含有n个元索，脚标为范围为…丿-1。voidMaxsort(Sement[]E){intmaxID=0;for(inti=Elength;i>1;i-){for(intj=0;j

2、){if(旦j]>E[maxlD])maxlD=k;}E[i]<->日maxID];}}(b)说明在最坏情况下和平均情况下上述算法的比较次数。最坏情况同平均情况是和同的都是C(n)==巴—or=l24.2：在以下的几个练习屮我们研究一种叫做“冒泡排序”的排序算法。该算法通过连续几遍浏览序列实现。排序策略是顺序比较相邻元索，如果这两个元素未排序则交换这两个元素的位置。也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元索的位置；然后比较第二个元索与第三个元索，按照需要交换两个元索的位置；以此类推。(a)起泡排序的最坏情况为逆序输入，比较次数为C

3、(n)=Y心也二U。(b)最好情况为已排j=i2序，需要(n・l)次比较。4.3：(a)归纳法：当n=l时显然成立，当n=2吋经过一次起泡后，也显然最犬元素位于末尾；现假设当n二k・l是，命题也成立，则当n=k时，对前k・l个元素经过一次起泡后，根据假设显然第k-1个元索是前k-1个元索中最大的，现在根据起泡定义它要同第k个元索进行比较，当k元素大于k・l元素时，它为k个元素屮最大的，命题成立；当k元素小于k・l元素时，它要同k・l交换，这时处丁队列末尾的显然时队列中最大的元素。综上所述，当n=k时命题成立。(b)反正法：假设当没有一对相邻的元素需耍交换位置的时候，得到的序

4、列是未排序的,则该未排序队列至少存在一对元索是逆序的，现设这两个元索未玖I)和E(i+k)，其中E(i)>E(i+k)。而根据没有一对相邻元素需要交换位置的条件，又有E(i+k)>E(i+k-l)>>E(i+1)>E(i),这是矛盾的。4.4：(a)证明：根据4.3(a)j+l处交换后，j+1元素是前j+1个元素中最大的。又因为在j+1到之间没有再发生交换，即说明E(j+l)vE(j+2)v......

5、lmPairs;intlast;intj;last=n・1;while(last>0){numPairs=last;last=-1;for(intj=0;jvnumPairs;j++){if但j]>耳j+1]){InterchangeE[j]andE[j+1];last=j;}}}return;}(b)这种改进对最坏情况并没冇什么改进，因为在最坏情况(倒序)时，还时从至IJ1的每个过程都循环一遍。4.5不可以。正如同前而练习屮所说的那样，已经排序的并不一定在“正确的位置之上”，这也许就是所说的“小局部，大局观”吧。简单的说明可以时，每一次向后的移动都是针对当前最大值的，也就

6、是说最人值的移动是一移到底的，而同吋相对小值的移动每次最多是一步。所以说即使是局部已经排序了，但是相对于“正确”排序的位置还是有差距的。4.6和.,3,1,2说明:将1放在n〜2的逆序中任何位置都不改变最坏情况。4.7插入排序的最佳情况是序列已排序，这时候需耍比较次数为ml次，移动次数为0次。4.8(a)最坏情况为插入位置在正数第2个位置，或者倒数第2个位置，比较次数［i/2］。在采用折半查找的时候，会设定已排序序列的首尾指针和当前指针，这样只有在第2个位置的元素进行最后的比较。(b)在最坏情况下插入位置在第1个位置上，移动次数为i次。(c)由于折半插入排序只是减少了比较的

7、次数，并没有减少移动的次数，所以算法的时间复杂度仍然是0(川)的。(d)采用链表数据结构后的插入排序是可以减少元素的移动次数的，因为整个排序的最多移动次数为3(n-l)。但是这样也仅仅是减少了元索的移动时间，并没冇减少元索的比较次数，所以算法的时间复制度仍然是0(川)的。4.9首先说明直接插入排序是稳定的。在有重复键值输入的情况下，插入排序的平均吋间复制度会有所增加，因为在寻找插入位置的时候，会多比较那些相等的值。4.10含有n个元素的逆排序序列的逆序数为巴二U。24」1IntListlistlnsSort(lnt