资源描述：
《sorting and order statistics》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、SortingandOrderStatisticsIanParberryDepartmentofComputerSciencesUniversityofNorthTexasFebruary20,1997Wewillanalyzethenumberofcomparisonsneededtosolvetheproblemofsortingndistinctitemsintoascendingorder,andtherelatedproblemofselectingthekthsmallestitemfromanunsortedlistofnitems.Section1examine
2、smergesort,analgorithmwithexcellentworstcaseperformance,andSection2examinesquicksort,analgorithmwithex-cellentaveragecaseperformance.Section3containssomedecisiontreelowerboundsonthenumberofcomparisonsusedbyanycomparison-basedsortingalgorithmintheworstandaveragecases.Section4containstwolinear-
3、timeselectionalgorithms,oneaveragecaseandoneworstcase,andalowerboundbasedontheadversarymethod.1MergesortdlogneMergesortisasortingalgorithmthatrunsinO(nlogn)timeandmakesndlogne?2+1comparisonsintheworstcase.Wewillanalyzetherunningtimeandnumberofcomparisonsusedbymergesort,demonstratingseveraltec
4、hniquesthatcanbeusedtosolverecurrencerelationswith
oorsandceilingsinthem,includingroundingnuptothenextpowerof2(Section1.1),simplifyingtherecurrencerelation(Section1.2),simplifyingexpressionswithmultiple
oorandceilingoperators(Section1.3),andmathematicalinduction(Section1.4).1.1TheAlgorithmCon
5、siderthefollowingalgorithmforsortingalistLofelementsfromatotallyorderedset:dividethelistasevenlyaspossibleintotwosublistsLandL,sorteachofLandL1212recursively,andthenmergethemtogether.functionmergesort(L;n)commentsortalistLofnobjects1.ifn1thenreturn(L)else2.breakLinto2listsL;Lofalmostequalsiz
6、e123.return(merge(mergesort(L;dn=2e),mergesort(L;bn=2c)))12Author'saddress:Dept.ofComputerSciences,Univ.ofNorthTexas,P.O.Box13886,Denton,TX76203{3886,U.S.A.Email:ian@cs.unt.edu.URL:http://hercule.csci.unt.edu/ian.1Themergeoperationcanbeperformedbyiteratingthefollowingstep:comparetheitemsatth
7、eheadofthetwolists,andappendthesmallerofthetwotothetailofanewlist.functionmerge(L;L)12commentmergetwosortedlistsL;Lintoasinglesortedlist124.L:=theemptylist5.whilebothL;Larenotemptydo126.x:= rstelementofL;y:= rstelementofL127.ifxy8.thenremove
