Data Structure(C++) Slides-ENG 数据结构课件Chapter-8-Sorting-English

2026

DataStructuresChapter8

SortingBasicConcepts

ofSorting8.1

BasicConcepts

ofSorting[LearningFocus]◆Insertionsorting◆Swapsorting◆Selectionsorting◆Mergesorting◆Allocationsorting[LearningDifficulties]◆AlgorithmideasandC++implementationofquicksorting,heapsorting,andmergesorting.8.1DataStructuresChapter8

Sorting

Sorting:givenasetofrecords{r1,r2,...,rn}withkeys{k1,k2,...,kn},sortingarrangestheserecordsintoasequence{rs1,rs2,...,rsn}sothatthecorrespondingkeyssatisfyks1<=ks2<=...<=ksn(ascendingorder)orks1>=ks2>=...>=ksn(descendingorder).Positiveorder:therecordsinthesequencetobesortedarealreadyorderedbykey.Inverseorder(reverseorder):theorderoftherecordsinthesequencetobesortedisexactlyoppositetothesortedorder.BasicConcepts

ofSorting8.1

Defaultassumptions:(1)Thedatasequenceisstoredusingasequentialstoragestructure.(2)Onlykeysareconsideredandotherdataitemsareignored.Aone-dimensionalarrayoflengthN+1isused;theoriginalkeysequencestartsfromindex1,whileindex0isunusedorusedforotherpurposes.(3)Thedefaultsortingresultisascendingorder.8.1Stabilityofasortingalgorithm:ifseveralrecordsinthesettobesortedhavethesamekeyandtheirrelativeorderremainsunchangedaftersorting,thenthesortingalgorithmisstable.Thatis,ifki=kjandriprecedesrjintheoriginalsequence,thenristillprecedesrjinthesortedsequence;otherwise,thealgorithmisunstable.BasicConcepts

ofSorting

Multi-keySortingSingle-keySortingBasicConcepts

ofSorting8.1ClassificationofsortingStoragelocationofrecordsInternalsorting:allrecordstobesortedarekeptinmemorythroughoutthesortingprocess.Externalsorting:therearetoomanyrecordstobestoredentirelyinmemory,sosomerecordsarekeptinmemoryandothersinexternalstorage;datamustbeexchangedbetweeninternalandexternalstoragemultipletimestoobtainthesortedresult.Keys1.Comparison-based:basicoperationsincludekeycomparisonandrecordmovement.2.Non-comparison-based:basedonthedistributioncharacteristicsofkeys.8.1BasicConcepts

ofSortingPerformanceofsortingalgorithms1.Basicoperations.Ininternalsorting,thebasicoperationsare:Comparison:comparisonbetweenkeys.Movement:movingarecordfromonepositiontoanother.2.Auxiliarystoragespace.Auxiliarystoragespacereferstotheextrastoragerequiredbythealgorithm,inadditiontothestorageoccupiedbytherecordstobesorted,whenthedatasizeisfixed.3.Complexityofthealgorithmitself.8.1BasicConcepts

ofSortingChapterExperimentBasicrequirement:choosetwoofthethreesimplesortingalgorithms.Optionalenhancement:QuicksortingHeapsortingMergesortingTime:nextMonday(December8),periods3-4inthemorningand5-6intheafternoonChapterExperiment8.18.2Insertion

SortingInsertion

Sorting8.2.1Direct

Insertion

SortingShell

Sorting8.2.2118.2Direct

Insertion

Sorting8.2Themainoperationofinsertionsortingisinsertion.Eachtime,arecordtobesortedisinsertedintoanalreadyorderedsequenceaccordingtoitskey.Wheninsertingthei-th(i>1)record,theprecedingi-1recordshavealreadybeensorted.KeyquestionsHowtoconstructtheinitialorderedsequence?Howtofindtheinsertionpositionfortherecordtobeinserted?Ordered

SequenceUnordered

Sequencer1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……Keyquestion(1):Howtoconstructtheinitialorderedsequence?Solution:Treatthefirstrecordastheinitialorderedlist,andtheninsertrecordsfromthesecondoneintothisorderedlistonebyoneuntilthen-threcordisinserted.Algorithmdescription:

for(i=2;i<=n;i++){Insertthei-threcord,i.e.,thei-thpassofdirectinsertionsorting;}r0123456211825221025*8.2Direct

Insertion

Sorting8.2Keyquestion(2):Howtofindtheinsertionpositionfortherecordtobeinserted?

Solution:

Wheninsertingrecordr[i]intotheorderedzoner[1]~r[i-1],firstsearchsequentiallyforthecorrectinsertionpositionofr[i],andtheninsertr[i]intothatposition.Algorithmdescription:

r[0]=r[i];j=i-1;while(r[0]<r[j]){r[j+1]=r[j];j--;}r[0]hastwofunctions:1.Beforeenteringtheloop,ittemporarilystoresthevalueofr[i],sothecontentofr[i]willnotbelostwhenrecordsmovebackward.2.Itactsasasentinelintheloopthatsearchesfortheinsertionposition.r01234562125i=318221025*22Direct

Insertion

Sorting8.2r0123456211825221025*212125i=218221025*25i=318221025*2525222110252221102525*2522211025*252221181018181025*i=418i=61825*i=522Direct

Insertion

Sorting8.2PerformanceAnalysisofDirectInsertionSortingBestcase(positiveorder):Onecomparisonandtwomovementsineachpass12345Timecomplexity:O(n).Numberofcomparisons:n-1Numberofmovements:2(n-1)123451234512345123452345Direct

Insertion

Sorting8.2PerformanceAnalysisofDirectInsertionSortingWorstcase(inverseorderorreverseorder):Timecomplexity:O(n2).54321453213452123451123454321

Numberofcomparisons:Numberofmovements:Averagecase(randomorder):Timecomplexity:O(n2).Direct

Insertion

Sorting8.2PerformanceAnalysisofDirectInsertionSortingSpaceperformance:oneauxiliaryspaceforarecordisrequired.SummaryofDirectInsertionSortingDirectinsertionsortingisastablesortingalgorithm.Directinsertionsortingissimpleandeasytoimplement.Itissuitablewhentherecordstobesortedarealmostorderedorwhenthenumberofrecordsissmall.Whenthenumberofrecordsislarge,alargenumberofcomparisonsandmovementsreducestheefficiencyofdirectinsertionsorting.Direct

Insertion

SortingShell

Sorting8.2ShellSortingAnimprovementofdirectinsertionsorting,alsocalleddecremental-incrementsorting.Keyideasforimprovement:(1)Iftherecordstobesortedarenearlyorderedbykey,theefficiencyofdirectinsertionsortingcanbegreatlyimproved.(2)Sincedirectinsertionsortingissimple,itisalsoefficientwhenthenumberofrecordsnissmall.8.2Basicidea:divideallrecordstobesortedintoseveralsub-sequencesandperformdirectinsertionsortingwithineachsub-sequence.Whentheentiresequenceisnearlyordered,performdirectinsertionsortingonallrecords.Groupedinsertion:Firstchooseanintegerd1<nasthefirstincrementandgroupallrecords.Recordsseparatedbyd1areplacedinthesamegroup,anddirectinsertionsortingisperformedwithineachgroup.Thenchooseasecondincrementd2<d1andrepeatthegroupingandsortinguntilthechosenincrementdt=1(dt<...<d2<d1),sothatallrecordsareplacedinonegroupanddirectinsertionsortingisperformed.Shell

Sorting8.21234567894021254925*16Initialsequence300813d1=44021254925*16300813252125*300849131640d2=21325210825*16304940252125*300813164049d3=10825211325*16304049082513162125*403049Shell

Sorting8.2ShellSorting:TwoKeyQuestionsPartitioningrecordstobesortedFunction:reducethenumberofrecordsineachsub-sequenceandmakethewholesequencedeveloptowardanearlyorderedstate.Recordsseparatedbyacertain"increment"formonesub-sequence.Shelloriginallyproposedd1=n/2anddi+1=di/2.Howtoperformdirectinsertionsortingwithinasub-sequenceWheninsertingrecordr[i],searchbackwardfromr[i-d]injumpsofdtofindtheinsertionposition.Duringthesearch,recordsalsomovebackwardbydpositions.Inthewholesequence,thefirstdrecordsarethefirstrecordsofthedsub-sequences,soinsertionstartsfromthe(d+1)-threcord.d1=44021254925*16300813Shell

Sorting8.2PerformanceofShellSortingAtthebeginning,theincrementislargeandeachsub-sequencehasfewerrecords,sosortingisfast.Whentheincrementbecomessmall,eachsub-sequencehasmorerecords,butthewholesequenceisalreadynearlyordered,sosortingisalsofast.ThetimeperformanceofShellsortingdependsonthechosenincrementsequence.Sofar,nooptimalincrementsequencehasbeenfound.StudiesshowthatitstimeperformanceliesbetweenO(n2)andO(nlog2n).Shellsortingisunstable.Shellsortingisbetterthaninsertionsortingbutnotasgoodasquicksorting;itperformswellformedium-sizedproblems.Shell

Sorting

8.2Shell

Sorting8.3Swap

Sorting8.3.1BubbleSortingQuickSorting8.3.2Swap

Sorting8.3Themainoperationofswapsortingisexchange.Itsmainideaistoselecttworecordsinthesequencetobesorted,comparetheirkeys,andexchangetheirstoragepositionsiftheyareinreverseorder,thatis,iftheirorderisexactlyoppositetothesortedorder.Exchange

ifinreverseorderrirjBubble

Sorting8.3BubbleSortingBasicidea:compareadjacentrecordspairwise;iftheyareinreverseorder,exchangethemuntiltherearenorecordsinreverseorder.rjrj+1ri+1<=...<=rn-1<=rnUnorderedzoneOrderedzone1<=j<=i-1

AlreadyinfinalpositionExchangeifinreverseorderBubble

Sorting8.3ExampleoftheBubbleSortingProcess059812693853810598126938538105981269385381059812693853818.3KeyQuestionsinBubbleSorting(1)Inonepassofbubblesorting,ifmultiplerecordsreachtheirfinalpositions,howshouldthisberecorded?(Howtodistinguishtheorderedzonefromtheunorderedzone?)(2)Howtodeterminetherangeofbubblesortingsothatrecordsalreadyintheirfinalpositionsdonotparticipateinthenextpass?(3)Howtodeterminetheendofbubblesorting?Bubble

Sorting8.3(1)Inonepassofbubblesorting,ifmultiplerecordsreachtheirfinalpositions,howshouldthisberecorded?(Howtodistinguishtheorderedzonefromtheunorderedzone?)Solution:Usethevariableexchangetorecordthepositionofrecordexchange.Afteronesortingpass,exchangerecordsthepositionofthelastexchangeinthatpass,andallrecordsafterthispositionarealreadyordered.059812693853810598698112exchange38exchange53exchangeBubble

Sorting8.3(2)Howtodeterminetherangeofbubblesorting?Solution:Lettherecordatpositionboundbethelastrecordintheunorderedzone.Thentherangeofeachbubblesortingpassisr[1]~r[bound].Afteronepass,allrecordsaftertheexchangepositionmustbeordered,sobound=exchange.Algorithmdescription:bound=exchange;//sortingrangefor(j=1;j<bound;j++)if(r[j]>r[j+1]){//pairwisecomparison;exchangeifinreverseorderr[j]<==>r[j+1];exchange=j;//recordtheexchangeposition}Bubble

Sorting8.3(3)Howtodeterminetheendofbubblesorting?Solution:Beforeeachpassofbubblesorting,settheinitialvalueofexchangeto0.Duringsorting,ifanyrecordisexchanged,exchangebecomesgreaterthan0.Afteronepassofcomparison,checkwhetherexchangeis0todeterminewhetheranyrecordwasexchanged,andthusdeterminewhethertheentirebubblesortingprocesshasended.Algorithmdescription:voidBubbleSort(intr[],intn){exchange=n;while(exchange){bound=exchange;exchange=0;for(j=1;j<bound;j++)if(r[j]>r[j+1]){r[j]<->r[j+1];exchange=j;}}}Bubble

Sorting8.3TimePerformanceofBubbleSortingBestcase(positiveorder):

Timecomplexity:O(n).Worstcase(reverseorder):

Timecomplexity:O(n2).Averagecase:

Timecomplexity:O(n2).12345Numberofcomparisons:n-1Numberofmovements:054321Bubble

Sorting8.3Improvementfocus:inbubblesorting,recordsarecomparedandmovedonlybetweenadjacentunits.Eachexchangemovesarecordbyoneposition,somanycomparisonsandmovementsareneeded.Reducetotalcomparisons

andmovementsIncreasecomparison/movement

distanceMovelargerrecords:front→backMovesmallerrecords:back→frontBubble

SortingQuick

Sorting8.3BasicideaFirstchooseapivotvalue(thebasisforcomparison).Throughonesortingpass,dividetherecordstobesortedintotwoindependentparts:thekeysinthefirstpartarealllessthanorequaltothepivot,andthekeysinthesecondpartareallgreaterthanorequaltothepivot.Thenrepeattheabovemethodforthetwopartsrespectivelyuntiltheentiresequenceisordered.Keyquestions(1)Howtochoosethepivot?(2)Howtoperformpartitioning(onepartition)?(3)Howtoprocessthetwosub-sequencesobtainedbypartitioning?(4)Howtodeterminetheendofquicksorting?8.3Keyquestion(1):Howtochoosethepivot?Methodsforchoosingthepivot:Usethekeyofthefirstrecord.Usethekeyofthemiddlerecordinthesequence.Comparethekeysofthefirst,last,andmiddlerecords,choosethemediankeyasthepivot,andswapittothepositionofthefirstrecord.Chooseapivotrandomly.Effectofchoosingthepivot:Itdeterminesthelengthsofthetwosub-sequences.Ideally,thetwosub-sequencesshouldhaveequallength.(38,27,55,50,13,49,65)Quick

Sorting8.3Keyquestion(2):Howtoperformonepartition?Assumethesequencetobepartitionedisr[s]~r[t].Letiandjpointtotheleftandrightendsofthesub-sequence,withsubscriptssandtrespectively,andletr[s]bethepivot.Implementationmethod:1.r[i]isthepivot.Letjscanfrombacktofrontuntilr[j]<r[i],thenexchanger[j]andr[i]tomovetherecordwiththesmallerkey(relativetothepivot)tothefront.13652750384955jijj13386527504955Quick

Sorting8.3Keyquestion(2):Howtoperformonepartition?2.r[j]isthepivot.Letiscanfromfronttobackuntilr[i]>r[j],thenexchanger[j]andr[i]tomovetherecordwiththelargerkey(relativetothepivot)totheback.

3.Repeattheaboveprocessuntili=j.13386527504955jiii13652750493855ijjjQuick

Sorting8.3Keyquestion(2):Howtoperformonepartition?13652750384955ji1338652750495513652750493855jjiiijijjjQuick

Sorting8.3OnePartition:AlgorithmDescriptionintPartition(intr[],intfirst,intend){i=first;j=end;//Initializewhile(i<j){while(i<j&&r[i]<=r[j])j--;//Scanfromtherightif(i<j){r[i]<->r[j];i++;//Movethesmallerrecordtothefront}while(i<j&&r[i]<=r[j])i++;//Scanfromtheleftif(i<j){r[j]<->r[i];j--;//Movethelargerrecordtotheback}}returni;//iisthefinalpositionofthepivotrecord}Quick

Sorting8.3Keyquestion(3):Howtoprocessthetwosub-sequencesobtainedbypartitioning?Solution:Recursivelyperformquicksortingonthetwosub-sequencesobtainedbypartitioning.1327386550495513275038495565ijijQuick

Sorting8.3Keyquestion(3):Howtoprocessthetwosub-sequencesobtainedbypartitioning?Algorithmdescription:voidQuickSort(intr[],intfirst,intend){pivotpos=Partition(r,first,end);//OnepartitionQuickSort(r,first,pivotpos-1);//Performquicksortingonthefirstsub-sequenceQuickSort(r,pivotpos+1,end);//Performquicksortingonthesecondsub-sequence}Quick

Sorting8.3Keyquestion(4):Howtodeterminetheendofquicksorting?Solution:Ifthesequencetobesortedhasnorecordsoronlyonerecord,itisobviouslyorderedandthealgorithmends;otherwise,recursivesortingisperformed.Algorithmdescription:voidQuickSort(intr[],intfirst,intend){//Recursivelyperformquicksortingonthesequencefromfirsttoendif(first<end){pivotpos=Partition(r,first,end);QuickSort(r,first,pivotpos-1);QuickSort(r,pivotpos+1,end);}}Quick

Sorting8.3TimePerformanceAnalysisofQuickSortingBestcase:aftereachpartitionpositionsonerecord,theleftandrightsublistshavethesamelength:O(nlog2n).Worstcase:eachpartitionproducesonlyonesub-sequencewithonefewerrecordthanbefore(theothersub-sequenceisempty):O(n2).Averagecase:O(nlog2n)Recursiondepth:O(log2n)~O(n)Spaceperformance:Stability:O(1)UnstableQuick

Sorting8.3Classexercise:Giventhekeysequence(46,79,56,38,40,84),usequicksortingandtakethefirstrecordasthepivot.Theresultofonepartitionis()A(38,40,46,56,79,84)B(40,38,46,79,56,84)C(40,38,46,56,79,84)D(40,38,46,84,56,79)CQuick

Sorting8.3Classexercise:Giventhekeysequence(22,12,26,40,18,38,14,20,30,16,28),usequicksortingandtakethefirstrecordasthepivot.Findtheresultofonepartition.Quick

Sorting8.4Selection

SortingSelection

Sorting8.4Themainoperationofselectionsortingisselection.Itsmainideaistoselecttherecordwiththesmallestkeyfromthecurrentsequencetobesortedineachpassandaddittotheorderedsequence.OrderedSequencer1r2ri-1rirnrk…………UnorderedSequencernri+1r1r2ri-1……riri……ExchangeMinimumrecordSimple

Selection

Sorting8.4Basicidea:Inthei-thpass,selecttherecordwiththesmallestkeyfromn-i+1records(i=1,2,...,n-1)asthei-threcordintheorderedsequence.Keyquestions(1)Howtoselecttherecordwiththesmallestkeyfromthesequencetobesorted?(2)Howtodeterminethepositionoftherecordwiththesmallestkeyintheorderedsequence?8.4Example0821i=2Minimum:08Exchange21,08Minimum:16Exchange25,16Minimum:21Exchange49,212128i=12516490808i=3210828492128491625161625Simple

Selection

Sorting8.4Examplei=4Minimum:25Exchange25,28i=5Minimum:28Noexchange492108281625254921081628252849210816282528OnlyonerecordintheunorderedzoneSimple

Selection

Sorting8.4Keyquestion1:Howtoselecttherecordwiththesmallestkeyfromtheunorderedzone?Solution:Setanintegervariableindextorecordthepositionoftherecordwiththesmallestkeyduringonepassofcomparison.Keyquestion2:Howtodeterminethepositionoftherecordwiththesmallestkeyintheorderedsequence?212825164908indexindexindex08index=i; for(j=i+1;j<=n;j++)if(r[j]<r[index])index=j;Simple

Selection

Sorting8.4ImplementationvoidselectSort(intr[],intn){for(i=1;i<n;i++){index=i; for(j=i+1;j<=n;j++)if(r[j]<r[index])index=j;if(index!=i)r[i]<==>r[index]; }}Timecomplexity:O(n2)Simple

Selection

Sorting8.4Heap

SortingImprovementfocus:howtoreducethenumberofcomparisonsbetweenkeys.Iftheresultsofeachpasscanbeused,thatis,whilefindingtherecordwiththesmallestkey,alsofindrecordswithrelativelysmallkeys,thenthenumberofcomparisonsinlaterselectionscanbereduced,improvingtheefficiencyoftheentiresortingprocess.ReducethenumberofcomparisonsbetweenkeysFindsmallervalueswhilefindingtheminimumvalue8.4Heap:Acompletebinarytreewithoneofthefollowingproperties:thevalueofeachnodeislessthanorequaltothevaluesofitsleftandrightchildnodes(calledamin-heap),orthevalueofeachnodeisgreaterthanorequaltothevaluesofitsleftandrightchildnodes(calledamax-heap).182032364525385040281.Therootnodeofamin-heapisthesmallestofallnodes.2.Smallernodesareclosertotheroot,butnotabsolutely.3.Amax-heaphassimilarproperties.Heap

Sorting8.4Heapandsequence:whenaheapisstoredwithasequentialstoragestructure,theheapcorrespondstoasequence.503845402836322018285038453236402820182812345678910UsesequentialstorageHeap

Sorting8.4Basicideaofheapsorting:Firstconstructtherecordsequencetobesortedintoaheap.Atthispoint,thelargestrecordintheheapisselected.Thenremoveitfromtheheapandadjusttheremainingrecordsintoaheapagain.Inthisway,thesecond-largestrecordisfound,andtheprocesscontinuesuntilonlyonerecordremainsintheheap.Keyquestions(1)Howtobuildaheapfromanunorderedsequence(initialheapconstruction)?(2)Howtoprocesstheheap-toprecord?(3)Howtoadjusttheremainingrecordsintoanewheap(rebuildtheheap)?Heap

Sorting8.4Heapadjustment:Inacompletebinarytree,ifboththeleftandrightsubtreesoftherootareheaps,howcantherootnodebeadjustedsothatthewholecompletebinarytreebecomesaheap?283632163029321630293628321629363028Intheinitialstate,ifthesubscriptof28isk,whatisthesubscriptof36?2*kHeap

Sorting8.4HeapAdjustment:AlgorithmDescriptionvoidsift(intr[],intk,intm){//Thenumberofthenodetobesiftedisk;thelastnodeintheheapismi=k;j=2*i;temp=r[i];//Temporarilystoretherecordtobesiftedwhile(j<=m)//Siftinghasnotreachedaleaf{if(j<m&&r[j]<r[j+1])j++;//Choosethelargerofthetwochildrenif(r[i]>r[j])break;else{r[i]<=>r[j];i=j;j=2*i;}}}Heap

Sorting8.4HowtobuildaheapfromanunorderedsequenceAlgorithmdescription:for(i=n/2;i>=1;i--)sift(r,i,n);Ifthenumberofthelastnode(leaf)isn,whatnodecorrespondston/2?Therefore,theorderofheapconstructionistoperformheapadjustmentonebyonestartingfromthelastbranchnode.50384540283632201828iiiHeap

Sorting8.4Howtobuildaheapfromanunorderedsequence282516321836163216282518362532162818362528323628161825iiiHeap

Sorting8.4Keyquestion(2):Howtoprocesstheheap-toprecord?323628161825362832251816123456CorrespondsExchange162832251836123456Corresponds321628361825Heap

Sorting8.4Question(3):Howtoadjusttheremainingrecordsintoanewheap?32162836182516281632361825Torebuildtheheap,onlytheheap-toprecordneedstobeadjusted.Heap

Sorting8.4HeapSortingAlgorithmvoidHeapSort(intr[],intn){for(i=n/2;i>=1;i--)sift(r,i,n);for(i=1;i>n;i++){r[1]←→r[n-i+1];sift(r,1,n-i);}}//Initialheapconstruction//Processtheheap-toprecord//RebuildtheheapHeap

Sorting8.4PerformanceAnalysisofHeapSortingThefirstforloopistheinitialheapconstruction,whichrequiresO(n)time.Thesecondforloopoutputstheheap-toprecordandrebuildstheheap.Ittakestheheap-toprecordn-1times.Thei-thtimerequiresO(log2i)timetorebuildtheheap,sothetotaltimeisO(nlog2n).Therefore,theoveralltimecomplexityisO(nlog2n),whichisthebest,worst,andaveragetimecostofheapsorting.Heapsortingisunstable.Heap

Sorting8.4Exercise:Performheapsortingonthekeysequence{23,

17,

72,

60,

25,

8,

68,

71,

52}.1.Afteroutputtingthetwolargestkeys,theremainingheapis().2.Afteroutputtingthetwosmallestkeys,theremainingheapis().Heap

Sorting8.5Merge

Sorting8.5Merge

SortingThemainoperationofmergesortingismerging.Itsmainideaistograduallymergeseveralorderedsequencesuntilafinalorderedsequenceisobtained.Merging:theprocessofcombiningtwoormoreorderedsequencesintooneorderedsequence.Mergesortingcanbedividedintotwo-waymergingandmulti-waymerging.Two-waymergingissuitableforinternalsorting,whilemulti-waymergingisoftenusedinexternalsorting.8.5Two-wayMergeSortingBasicidea:treatasequencewithnrecordstobesortedasnorderedsequencesoflength1.Thenmergethempairwisetoobtainn/2orderedsequencesoflength2;mergethempairwiseagaintoobtainn/4orderedsequencesoflength4;andcontinueuntilanorderedsequenceoflengthnisobtained.Keyquestions(1)Howtomergetwoorderedsequencesintooneorderedsequence?(2)Howtocompleteonepassofmerging?(3)Howtocontroltheendoftwo-waymergesorting?Merge

Sorting8.5Two-way

Merge

SortingKeyquestion(1):Howtomergetwoorderedsequencesintooneorderedsequence?60203154455652060531445565

6020315445565ij5kj20i31j60Duringthemergingprocess,theoriginalorderedsequencesmaybedestroyed,sothemergingresultisstoredinanotherarray.8.5Keyquestion(1):Howtomergetwoorderedsequencesintooneorderedsequence?

Assumethattheadjacentorderedsequencesarer[s]~r[m]andr[m+1]~r[e],andtheyaremergedintoanorderedsequencer1[s]~r1[e].smm+1er[]ser1[]ijkTwo-way

Merge

Sorting8.5Keyquestion(1):Howtomergetwoorderedsequencesintooneorderedsequence?Algorithmdescription:voidMerge(intr[],intr1[],ints,intm,inte){i=s;j=m+1;k=s;while(i<=m&&j<=e){if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}if(i<=m)while(i<=m)//Tailprocessingr1[k++]=r[i++];//Firstsub-sequenceelsewhile(j<=e)r1[k++]=r[j++];//Secondsub-sequence}Two-way

Merge

Sorting8.5Keyquestion(2):Howtocompleteonepassofmerging?60203154455652060531445565

6020315445565ij5kj20i31j60Inonepassofmerging,exceptforthelastorderedsequence,the