文档介绍：Insertionsort, P171Fall2005Insertionsort1)Initiallyp=12))Insertthe(p+1)thelementproperlyinthelistsothatnowp+)incrementpandgotostep(3)InsertionSortInsertionSort...ConsistsofN-1passesForpassp=1throughN-1,ensuresthattheelementsinpositions0throughpareinsortedorderelementsinpositions0throughp-1arealreadysortedmovetheelementinpositionpleftuntilitscorrectplaceisfoundamongthefirstp+/~matuszek/cse121-2003/Applets/Chap03/Insertion/:34864513221P=1;Lookatfirstelementonly,=2;tmp=8;34>tmp,,1stposition=tmpAftersecondpass:83464513221(first2elementsaresorted)P=3;tmp=64;34<64,sostopat3rdpositionandset3rdposition=64Afterthirdpass:83464513221(first3elementsaresorted)P=4;tmp=51;51<64,sowehave83464643221,34<51,sostopat2ndposition,set3rdposition=tmp,Afterfourthpass:83451643221(first4elementsaresorted)P=5;tmp=32,32<64,so83451646421,32<51,so83451516421,next32<34,so83434,516421,next32>8,sostopat1stpositionandset2ndposition=32,Afterfifthpass:83234516421P=6;tmp=21,...Aftersixthpass:82132345164Analysis:worst-caserunningtimeInnerloopisexecutedptimes,foreachp=1..NOverall:1+2+3+...+N=O(N2)SpacerequirementisO(N)AnalysisTheboundistight(N2)Thatis,thereexistssomeinputwhichactuallyuses(N2)timeConsiderinputisareversesortedlistWhenA[p]isinsertedintothesortedA[0..p-1],pareA[p]withallelementsinA[0..p-1]andmoveeachelementonepositiontotheright(i)stepsthetotalnumberofstepsis(1N-1i)=(N(N-1)/2)=(N2)Analysis:bestcaseTheinputisalreadysortedinincreasingorderWheninsertingA[p]intothesortedA[0..p-1],pareA[p]withA[p-1]andthereisnodatamovementForeachiterationoftheouterfor-loop,theinnerfor-loopterminatesaftercheckingtheloopconditiononce=>O(N)timeIfinputisnearlysorted,insertionsortrunsfastMergesortBasedondivide-and-conquerstrategyDividethelistintotwosmallerlistsofaboutequalsizesSorteachsmallerlistrecur