9.9 sorting algorithms

《9.9 sorting algorithms》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Il@veRuBoard9.9SortingAlgorithmsTheSTLprovidesseveralalgorithmstosortelementsofarange.Inadditiontofullsorting,itprovidesdifferentvariantsofpartialsorting.Iftheirresultisenough,youshouldpreferthembecausetheyusuallyhavebetterperformance.Youmightalsouseassociativecontainerstohaveelementssort

2、edautomatically.However,notethatsortingallelementsonceisusuallyfasterthankeepingthemsortedalways(seepage228fordetails).9.9.1SortingAllElementsvoidsort(RandomAccessIteratorbeg,RandomAccessIteratorend)voidsort(RandomAccessIteratorbeg,RandomAccessIteratorend,BinaryPredicateop)voidstable_sort

3、(RandomAccessIteratorbeg,RandomAccessIteratorend)voidstable_sort(RandomAccessIteratorbeg,RandomAccessIteratorend,BinaryPredicateop)Thefirstformsofsort()andstable_sort()sortallelementsintherange[beg,end)withoperator<.Thesecondformsofsort()andstable_sort()sortallelementsbyusingthebinarypr

4、edicateop(elem1,elem2)asthesortingcriterion.Notethatopshouldnotchangeitsstateduringafunctioncall.SeeSection8.1.4,fordetails.Thedifferencebetweensort()andstable_sort()isthatstable_sort()guaranteesthattheorderofequalelementsremainsstable.Youcan'tcallthesealgorithmsforlistsbecauselistsdon

5、otproviderandomaccessiterators.However,listsprovideaspecialmemberfunctiontosortelements:sort()(seepage245).sort()guaranteesagoodperformance(n-log-n)onaverage.However,ifavoidingworst-caseperformanceisimportant,youshouldusepartial_sort()or1stable_sort().Seethediscussionaboutsortingalgorith

6、msonpage328.Complexity:Forsort():n-log-nonaverage(approximatelynumberOfElements*log(numberOfElements)comparisonsonaverage).Forstable_sort():n-log-nifthereisenoughextramemory(numberOfElements*log(numberOfElements)comparisons),orn-log-n*log-notherwise(numberOfElements*log(numberOfElement

7、s)[]comparisons).Thefollowingexampledemonstratestheuseofsort()://algo/sort1.cpp#include"algostuff.hpp"usingnamespacestd;intmain(){dequecoll;INSERT_ELEMENTS(coll,1,9);INSERT_ELEMENTS(coll,1,9);PRINT_ELEMENTS(coll,"onentry:");//sortelementssort(coll.begin(),coll.