计算机算法导论_第8章

《计算机算法导论_第8章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoAlgorithms计算机算法导论2007~2008年第一学期SortingandOrderStatisticsIntroductionSortingproblemDefinition:Input:Asequenceofnumbers.Output:Apermutation,suchthata'1≤a'2≤…≤a'n.ThestructureofthedataDefinition:Record=key+satellitedat

2、aAssumption:TheinputconsistsonlyofnumbersWhysorting?TheneedinherentinanapplicationAlgorithmsoftenusesortingasakeysubroutineAwidevarietyofsortingalgorithms,arichsetoftechniquesAproblemcanbeprovedanontriviallowerbound.Manyengineeringissuescometoforewhenimple

3、mentingsortingalgorithms.SortingalgorithmsAin-placesortingalgorithmComparisonsortThecountingsortalgorithmTheradixsortalgorithmThebucketsortalgorithmOrderstatisticsTheithorderstatisticofasetofnnumbersistheithsmallestnumberintheset.8、Sortinginlineartime8.1Lo

4、werboundsforsortingAssumption:AlloftheinputelementsaredistinctAllcomparisonshavetheformai≤ajHowfastcanwesort?Allthesortingalgorithmswehaveseensofararecomparisonsorts:onlyusecomparisonstodeterminetherelativeorderofelements.•E.g.,insertionsort,mergesort,quic

5、ksort,heapsort.Thebestworst-caserunningtimethatwe’veseenforcomparisonsortingisO(nlgn).IsO(nlgn)thebestwecando?Decisiontreescanhelpusanswerthisquestion.Decision-treemodelAdecisiontreecanmodeltheexecutionofanycomparisonsort:•Onetreeforeachinputsizen.•Viewthe

6、algorithmassplittingwheneveritcomparestwoelements.•Thetreecontainsthecomparisonsalongallpossibleinstructiontraces.•Therunningtimeofthealgorithm=thelengthofthepathtaken.•Worst-caserunningtime=heightoftree.Lowerboundfordecision-treesortingLowerboundforcompar

7、isonsortingCorollary.Heapsortandmergesortareasymptoticallyoptimalcomparisonsortingalgorithms.8.2CountingsortSortinginlineartimeCountingsort:Nocomparisonsbetweenelements.•Input:A[1..n],whereA[j]∈{1,2,…,k}.•Output:B[1..n],sorted.•Auxiliarystorage:C[1..k].Cou

8、ntingsortfori←1tokdoC[i]←0forj←1tondoC[A[j]]←C[A[j]]+1⊳C[i]=

9、{key=i}

10、fori←2tokdoC[i]←C[i]+C[i–1]⊳C[i]=

11、{key≤i}

12、forj←ndownto1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–1RunningtimeIfk=O(n),thencountingsorttakesΘ(n)time.