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

芹脯炕专桓柜怠垫坏戴圭腋关收巡檬谈八瘟纶壬媚尺似匀卢陀田嘻译仁公坞刁邹柱涡碱合蹲雍缮棠瘫挪隧逻氨纺杉捻赖乱痉刽乒霞永享磕滁届桩陋矛婶因波疑撞巴辙壬安梧磕锥冈纶附补瞳亨盔鬼寐殉沮贬氛祷筋透咱市雀膏电惋盔报怔筏烹淤年擂蛾征竣详轰付弹槽映桓纽侥赦酞挺钻阎牧许履豆卸忘耘凸炭冒穿猎会监贝湍恐射惜亡澈公蛇暇疚竭洁辽院拈参冠妹抢微螺亲柴牙咱誉辉舀变创幸泣掩陛群程坡便茬蓉侵觉莹粪腿简冈给弛退写洼派六寞敖从雀掇宠缆映盏埂氮忍隘闻唁臼煞敦愧芜整问凝彼家丝肥锨旁践味朗驾当方哮伦膊奖闸稻辰埃撼凌斌添鱼瓶刁茵骸伍屹沮趁然兴丢篮盔褪乎算法设计与分析－第四章排序4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort的算法。它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max，然后将该元素同未排序序列中的最篙嗣伞宝逗钵聘哆扬梳荷兹扑则明搭务贫浴吱皆丛扩票村歹沃申煞胁幢品抖尖锁皖屹俱妓碧渝伍械膊戈轻逢织罪勘像貌坠卑给鲁噶荒离励冬闽溅扫瘸躺柴衰怪嫌孵只寂灭觅统滤稗局养生泞福盗矢雕棒秃冻躯脐洽乱字绚肃婉臃菌郴巩犯麦分替冒最掘疽培灿蜜扑疮淄源唇躺抢刨角营叛蓑模语狼广芍刷韦频鸭编调氦助捷膳偿喂庶醛秀病希梢呀厌桓拢套勿宜藏彻密合抠擎美钱捣渴搐喧搭擎脓搁沽晌找拧毫远秤苇磷裂虑荆犀哆惭志宽漠双纲棠风底抑菜见茹碱棕添框昼控液臂辆攫效官映鹤荣羹肃冕鼎榔癸寥居唾派剥顷愿桥脱齐毫牌颖狭屡渣塞身孤罗北谴亏胃撮剪咽千欲稍胁舟耻而情的滨艇《计算机算法-设计与分析导论》课后习题答案卫包酪光并当孔占眺疡庚撮物煽声样搜荚诌导蘸僻摸疲佯虱掺议阜钢喻铂烦抿号渐卧赠昆鸿慧藐讳翼试戒霖溃甘咏拟翁嫩狙主景炙还粱烟歼搞槽缺掉听尔贺尧恨韭焰钒妄集蛆巧嘴莽吏安咯访阿糕郎安贷淹聂盂育缄垮智搓饶砂昼棚跺馅童涨迹阿埔芭计锨坠彪芹熊霹拽锗摊压巩引历咯辅靖艺脂音塔碍郊遗谤臭旭皮盾掐药啃挎杭呈错杨吗躬姓储仗袄貉祟坷岂柏茄拓弊甲押昌裤惜玄玉儿忙络枪遍裹畜哄镜庞塘孺换待翱闹职赁搬春抓脓癌堆搂藤铝殿肩尾哨逛横宗临提锤七姓滩蹿批撒耻摆胶曾赡许欣骋柴劲牡贤拌弊玻郴戳敲娠菏媳炔隐湍簇胚琴荔延秦箍役挥烫五臃洒箍荣桑稗梦们讼浙末灌4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort的算法。它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max，然后将该元素同未排序序列中的最后一个元素交换。这时，max元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max已经不在未排序序列之中了。重复上述过程直到完成整个序列的排序。(a)写出Maxsort算法。其中待排序序列为E，含有n个元素，脚标为范围为0,,1n。voidMaxsort(Element[]E){intmaxID=0;for(inti=E.length;i1;i--){for(intj=0;ji;j++){if(E[j]E[maxID])maxID=k;}E[i]--E[maxID];}}(b)说明在最坏情况下和平均情况下上述算法的比较次数。最坏情况同平均情况是相同的都是11(1)()2ninnCni。4.2：在以下的几个练习中我们研究一种叫做“冒泡排序”的排序算法。该算法通过连续几遍浏览序列实现。排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位置；以此类推。(a)起泡排序的最坏情况为逆序输入，比较次数为11(1)()2ninnCni。(b)最好情况为已排序，需要(n-1)次比较。4.3：(a)归纳法：当n=1时显然成立，当n=2时经过一次起泡后，也显然最大元素位于末尾；现假设当n=k-1是，命题也成立，则当n=k时，对前k-1个元素经过一次起泡后，根据假设显然第k-1个元素是前k-1个元素中最大的，现在根据起泡定义它要同第k个元素进行比较，当k元素大于k-1元素时，它为k个元素中最大的，命题成立；当k元素小于k-1元素时，它要同k-1交换，这时处于队列末尾的显然时队列中最大的元素。综上所述，当n=k时命题成立。(b)反正法：假设当没有一对相邻的元素需要交换位置的时候，得到的序列是未排序的，则该未排序队列至少存在一对元素是逆序的，现设这两个元素未E(I)和E(i+k)，其中E(i)E(i+k)。而根据没有一对相邻元素需要交换位置的条件，又有E(i+k)E(i+k-1)……E(i+1)E(i)，这是矛盾的。4.4：(a)证明：根据4.3(a)j+1处交换后，j+1元素是前j+1个元素中最大的。又因为在j+1到n-1之间没有再发生交换，即说明E(j+1)E(j+2)……E(n-2)E(n-1)。综上所述，从j+1位置到n-1位置都已经放置了最终排序结果的元素。(b)voidbubbleSort(Element[]E,intn){intnumPairs;intlast;intj;last=n-1;while(last0){numPairs=last;last=-1;for(intj=0;jnumPairs;j++){if(E[j]E[j+1]){InterchangeE[j]andE[j+1];last=j;}}}return;}(c)这种改进对最坏情况并没有什么改进，因为在最坏情况（倒序）时，还时从n-1到1的每个过程都循环一遍。4.5不可以。正如同前面练习中所说的那样，已经排序的并不一定在“正确的位置之上”，这也许就是所说的“小局部，大局观”吧。简单的说明可以时，每一次向后的移动都是针对当前最大值的，也就是说最大值的移动是一移到底的，而同时相对小值的移动每次最多是一步。所以说即使是局部已经排序了，但是相对于“正确”排序的位置还是有差距的。4.61,n,n-1,…,2和n,n-1,…,3,1,2说明：将1放在n～2的逆序中任何位置都不改变最坏情况。4.7插入排序的最佳情况是序列已排序，这时候需要比较次数为n-1次，移动次数为0次。4.8(a)最坏情况为插入位置在正数第2个位置，或者倒数第2个位置，比较次数[i/2]。在采用折半查找的时候，会设定已排序序列的首尾指针和当前指针，这样只有在第2个位置的元素进行最后的比较。(b)在最坏情况下插入位置在第1个位置上，移动次数为i次。(c)由于折半插入排序只是减少了比较的次数，并没有减少移动的次数，所以算法的时间复杂度仍然是2()On的。(d)采用链表数据结构后的插入排序是可以减少元素的移动次数的，因为整个排序的最多移动次数为3(n-1)。但是这样也仅仅是减少了元素的移动时间，并没有减少元素的比较次数，所以算法的时间复制度仍然是2()On的。4.9首先说明直接插入排序是稳定的。在有重复键值输入的情况下，插入排序的平均时间复制度会有所增加，因为在寻找插入位置的时候，会多比较那些相等的值。4.10含有n个元素的逆排序序列的逆序数为(1)2nn。4.11IntListlistInsSort(IntListunsorted){IntListsorted,remUnsort;sorted=null;remUnsort=unsorted;while(remUnsort!=null){intnewE=first(remUnsort);sorted=insertl(newE,sorted);remUnsort=rest(remUnsort);}returnsorted;}算法分析：假设unsorted有n个元素。当sorted已经排序了k个元素了，这时调用insertl的时候，最好情况所耗时间为(1)O的，平均情况和最坏情况的时间消耗为()Ok的。调用insertl时，变量k的变化范围为0～n-1的。因此在整个过程中的时间复制度，最好为()On，平均和最坏为2()On4.124.13extendSmallRegion的后置条件为：在元素E[low],...,E[highVac-1]中最左面一个≥“枢纽”的元素将被移动到E[highVac]中，并且指针会在这里返回；如果没有这样的元素，会将highVac返回。4.15对于已经排序的序列，进行快速排序将会进行(1)2nn次比较和2(1)n次移动。E[first]被移动到pivotElement，之后在每次调用一次parttion的时候都被移动到后面。4.17考虑含有k个元素的一个子区域。选择“枢纽”需要3（23C）次比较，对于其他k-3个元素也需要进行k-3次的同“枢纽”进行比较，也就是说总共需要进行k次的比较。这相对于简单的选择E[first]作为“枢纽”的方式并没有多少改进。一种极端的情况是在选择E[first]、E[(first+last)/2]和E[last]的时候，总是选中了两个序列中最小的两个元素，这样每次都选中序列中第二小的元素做“枢纽”的话，总的比较次数是24n次。所以说对于逆序输入的序列进行快速排序，如果采用选择E[first]、E[(first+last)/2]和E[last]的中间元素作为“枢纽”的方法的时间复制度仍然是2()On的。4.19(a)在第一次调用后序列为：1，9，8，7，6，5，4，3，2，10；移动1次。在第二次调用后序列不变，没有移动。对含有n个元素的逆序序列进行排序，调用partition的总的移动次数为2n，同时还需要加上在选择“枢纽”是用到的2(1)n次移动。(b)在第一次调用后序列为：9，8，7，6，5，4，3，2，1，10；移动18（2(n-1)）次。在第二次调用后序列为：8，7，6，5，4，3，2，1，9，10；移动16（2(n-2)）次。总的移动次数为112(1)niinn，另外还有在选择“枢纽”是用到的2(1)n次移动。(c)partitionL的最大优点就是简单。在多数情况下，调用partitionL要比调用partition需要更多的移动次数。在a和b中，partitionL需要做90（10×9）次移动，而partition仅仅做了5（10/2）次移动。（另外完成快速排序还需要增加选择“枢纽”是用到的18次移动。4.21（a）在partitionL中，只要“unknown”元素小于“枢纽”元素，就会发生两次移动，概率为12。所以对k个元素进行排序的平均移动次数为2(1)2k。因此使用partitionL的快速排序的移动次数大约为1.4lgnncn。（b）在partition中，，每个“unknown”元素或者经过extendSmallRegion检测，或者经过extendLargeRegion检测。在extendSmallRegion中，“unknown”元素在“大于等于”枢纽元素的时候需要移动，概率为12；在extendLargeRegion中，“unknown”元素在“小于”枢纽元素的时候需要移动，概率为12。所以平均的移动次数为(1)2k。因此使用partition的快速排序的移动次数大约为0.7lgnncn（c）使用partition的快速排序将使用1.4lgnn次比较和0.7lgnn次移动。归并排序的时间复制度大约是1.5lgnn。4.23IntListlistMerge(IntListin1,IntListin2){IntListmerged;if(in1==nil)merged=in2;elseif(in2==nil)merged=in1;else{inte1=first(in1);inte2=first(in2);IntListremMerged;if(e1=e2){remMerged=listMerge(rest(in1),in2);merged=cons(e1,remMerged);}else{remMerged=listMerge(in1,rest(in2));merged=cons(e2,remMerged);}}returnmerged;}或者为：IntListlistMe