数据结构与算法分析 第13章 答案 larry nyhoff 清华大学出版社

《数据结构与算法分析 第13章 答案 larry nyhoff 清华大学出版社》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter13Chapter13:SortingExercises13.11.Afterfirstpass,elementsofxare:105070304060.Aftersecondpass:103070504060.2.(a)607050402010706050402010(b)3,sincenointerchangesoccuronthethirdpass.(c)Worstcaseiswhenelementsareinreverseorder.3.(a)Afterx[4]ispositioned:203040601050Afte

2、rx[5]ispositioned:102030406050(b)Ifthelistisinincreasingorder;nointerchangesarerequired.4.(a)Afteronepass:105060304070Aftertwopasses:103040506070(b)Functiontoperformdouble-endedselectionsort:templatevoiddoubleEndedSelectionSort(ElementTypex[],intn)/*--

3、-------------------------------------------------------------------Sortalistintoascendingorderusingdouble-endedselectionsort.Precondition:arrayxcontainsnelements.Postcondition:Thenelementsofarrayhavebeensortedintoascendingorder.---------------------------------------------

4、-----------------------*/{intminValue,maxValue,minPos,maxPos;for(inti=1;i<=n/2;i++){minValue=maxValue=x[i];minPos=maxPos=i;//findminandmaxvaluesamongx[i],...,x[n]–226–Chapter13for(intj=i+1;j<=n-i+1;j++){if(x[j]maxValue){maxValue=x

5、[j];maxPos=j;}}//makesurethatpositioningminvaluedoesn'toverwritemaxif(i==maxPos)maxPos=minPos;x[minPos]=x[i];x[i]=minValue;x[maxPos]=x[n-i+1];x[n-i+1]=maxValue;}}2(c)ComputingtimeisO(n).5.(a)Afterstep1executes,x[i]'sare:305090106070201008040Thereare5passesforstep2.x[i]'sar

6、e:Afterfirstpass:105040206070309080100Aftersecondpass:102040306070508090100Afterthirdpass:102030406070508090100Afterfourthpass:102030405060708090100Afterfifthpass:102030405060708090100(b)ThefunctionsbelowimplementMin-MaxSort.templatevoidswap(ElementTyp

7、ex[],inta,intb){inttemp=x[a];x[a]=x[b];x[b]=temp;}–227–Chapter13templatevoidminMaxSort(ElementTypex[],intn){//Createrainbowpatternfor(inti=1;i<=n/2;i++)if(x[i]>x[n+1-i])swap(x,i,n+1-i);//Findsmallestinfirsthalfoflistfor(inti=1;i<=n/2;i++){intminPos=i;i

8、ntminValue=x[i];for(intj=i+1;j<=n/2;j++)if(x[j]