详细解说 stl 排序(sort) - liuruigong_lrg - 网易博客.htm
来自「STL sort（）函数使用详细介绍 包含ＳＴＬ算法介绍文档」· HTM 代码 · 共 571 行 · 第 1/3 页
HTM
571 行
href="http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms?sortcol=0;table=1;up=0#sorted_table"
rel=nofollow>函数名</A> </TH>
<TH bgColor=#dadada maxcols="0"><A title="Sort by this column"
style="COLOR: rgb(0,0,0)"
href="http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms?sortcol=1;table=1;up=0#sorted_table"
rel=nofollow>功能描述</A> </TH></TR>
<TR>
<TD bgColor=#eaeaea>sort </TD>
<TD bgColor=#eaeaea>对给定区间所有元素进行排序 </TD></TR>
<TR>
<TD bgColor=#ffffff>stable_sort </TD>
<TD bgColor=#ffffff>对给定区间所有元素进行稳定排序 </TD></TR>
<TR>
<TD bgColor=#eaeaea>partial_sort </TD>
<TD bgColor=#eaeaea>对给定区间所有元素部分排序 </TD></TR>
<TR>
<TD bgColor=#ffffff>partial_sort_copy </TD>
<TD bgColor=#ffffff>对给定区间复制并排序 </TD></TR>
<TR>
<TD bgColor=#eaeaea>nth_element </TD>
<TD bgColor=#eaeaea>找出给定区间的某个位置对应的元素 </TD></TR>
<TR>
<TD bgColor=#ffffff>is_sorted </TD>
<TD bgColor=#ffffff>判断一个区间是否已经排好序 </TD></TR>
<TR>
<TD bgColor=#eaeaea>partition </TD>
<TD bgColor=#eaeaea>使得符合某个条件的元素放在前面 </TD></TR>
<TR>
<TD bgColor=#ffffff twikiLast?>stable_partition </TD>
<TD bgColor=#ffffff>相对稳定的使得符合某个条件的元素放在前面 </TD></TR></TBODY></TABLE>其中nth_element
是最不易理解的，实际上，这个函数是用来找出第几个。例如：找出包含7个元素的数组中排在中间那个数的值，此时，我可能不关心前面，也不关心后面，我只关心排在第四位的元素值是多少。
<H4><A 中的比较函数? sort></A>1.2 sort 中的比较函数
</H4>当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数。
<DIV>
<DIV><PRE><PRE>vector < <FONT color=brown>int</FONT> > vect;<BR><FONT color=green>//...</FONT><BR>sort(vect.begin(), vect.end());<BR><FONT color=green>//此时相当于调用</FONT><BR>sort(vect.begin(), vect.end(), less<<FONT color=brown>int</FONT>>() );</PRE></PRE></DIV></DIV>上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数，以下是仿函数列表:
<TABLE
style="BORDER-TOP-WIDTH: 0px; BORDER-LEFT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; BORDER-RIGHT-WIDTH: 0px"
cellSpacing=1 cellPadding=1 border=0>
<TBODY>
<TR>
<TH bgColor=#dadada maxcols="0"><A title="Sort by this column"
style="COLOR: rgb(0,0,0)"
href="http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms?sortcol=0;table=2;up=0#sorted_table"
rel=nofollow>名称 </A></TH>
<TH bgColor=#dadada maxcols="0"><A title="Sort by this column"
style="COLOR: rgb(0,0,0)"
href="http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms?sortcol=1;table=2;up=0#sorted_table"
rel=nofollow>功能描述 </A></TH></TR>
<TR>
<TD bgColor=#eaeaea>equal_to </TD>
<TD bgColor=#eaeaea>相等 </TD></TR>
<TR>
<TD bgColor=#ffffff>not_equal_to </TD>
<TD bgColor=#ffffff>不相等 </TD></TR>
<TR>
<TD bgColor=#eaeaea>less </TD>
<TD bgColor=#eaeaea>小于 </TD></TR>
<TR>
<TD bgColor=#ffffff>greater </TD>
<TD bgColor=#ffffff>大于 </TD></TR>
<TR>
<TD bgColor=#eaeaea>less_equal </TD>
<TD bgColor=#eaeaea>小于等于 </TD></TR>
<TR>
<TD bgColor=#ffffff twikiLast?>greater_equal </TD>
<TD bgColor=#ffffff>大于等于
</TD></TR></TBODY></TABLE>需要注意的是，这些函数不是都能适用于你的sort算法，如何选择，决定于你的应用。另外，不能直接写入仿函数的名字，而是要写其重载的()函数：
<PRE>less<int>()<BR>greater<int>()<BR></PRE>当你的容器中元素时一些标准类型（int
float
char)或者string时，你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型的'<'操作赋。
<DIV>
<DIV><PRE><PRE><FONT color=navy>#include</FONT> <iostream><BR><FONT color=navy>#include</FONT> <algorithm><BR><FONT color=navy>#include</FONT> <functional><BR><FONT color=navy>#include</FONT> <vector><BR><FONT color=brown>using</FONT> <FONT color=brown>namespace</FONT> std;<BR><BR><FONT color=brown>class</FONT> myclass {<BR> <FONT color=brown>public</FONT>:<BR> myclass(<FONT color=brown>int</FONT> a, <FONT color=brown>int</FONT> b):first(a), second(b){}<BR> <FONT color=brown>int</FONT> first;<BR> <FONT color=brown>int</FONT> second;<BR> <FONT color=brown>bool</FONT> <FONT color=brown>operator</FONT> < (<FONT color=brown>const</FONT> myclass &m)<FONT color=brown>const</FONT> {<BR> <FONT color=brown>return</FONT> first < m.first;<BR> }<BR>};<BR><BR><FONT color=brown>bool</FONT> less_second(<FONT color=brown>const</FONT> myclass & m1, <FONT color=brown>const</FONT> myclass & m2) {<BR> <FONT color=brown>return</FONT> m1.second < m2.second;<BR>}<BR><BR><FONT color=brown>int</FONT> main() {<BR> <BR> vector< myclass > vect;<BR> <FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < 10 ; i ++){<BR> myclass my(10-i, i*3);<BR> vect.push_back(my);<BR> }<BR> <FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < vect.size(); i ++) <BR> cout<<"<FONT color=blue>(</FONT>"<<vect[i].first<<"<FONT color=blue>,</FONT>"<<vect[i].second<<"<FONT color=blue>)\n</FONT>";<BR> sort(vect.begin(), vect.end());<BR> cout<<"<FONT color=blue>after sorted by first:</FONT>"<<endl;<BR> <FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < vect.size(); i ++) <BR> cout<<"<FONT color=blue>(</FONT>"<<vect[i].first<<"<FONT color=blue>,</FONT>"<<vect[i].second<<"<FONT color=blue>)\n</FONT>";<BR> cout<<"<FONT color=blue>after sorted by second:</FONT>"<<endl;<BR> sort(vect.begin(), vect.end(), less_second);<BR> <FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < vect.size(); i ++) <BR> cout<<"<FONT color=blue>(</FONT>"<<vect[i].first<<"<FONT color=blue>,</FONT>"<<vect[i].second<<"<FONT color=blue>)\n</FONT>";<BR> <BR> <FONT color=brown>return</FONT> 0 ;<BR>}</PRE></PRE></DIV></DIV>知道其输出结果是什么了吧：
<PRE>(10,0)<BR>(9,3)<BR>(8,6)<BR>(7,9)<BR>(6,12)<BR>(5,15)<BR>(4,18)<BR>(3,21)<BR>(2,24)<BR>(1,27)<BR>after sorted by first:<BR>(1,27)<BR>(2,24)<BR>(3,21)<BR>(4,18)<BR>(5,15)<BR>(6,12)<BR>(7,9)<BR>(8,6)<BR>(9,3)<BR>(10,0)<BR>after sorted by second:<BR>(10,0)<BR>(9,3)<BR>(8,6)<BR>(7,9)<BR>(6,12)<BR>(5,15)<BR>(4,18)<BR>(3,21)<BR>(2,24)<BR>(1,27)<BR></PRE>
<H4><A sort 的稳定性?></A>1.3 sort 的稳定性 </H4>你发现有sort和 stable_sort，还有 partition
和stable_partition，感到奇怪吧。其中的区别是，带有stable的函数可保证相等元素的原本相对次序在排序后保持不变。或许你会问，既然相等，你还管他相对位置呢，也分不清楚谁是谁了？这里需要弄清楚一个问题，这里的相等，是指你提供的函数表示两个元素相等，并不一定是一摸一样的元素。
<P>例如，如果你写一个比较函数: </P>
<DIV>
<DIV><PRE><PRE><FONT color=brown>bool</FONT> less_len(<FONT color=brown>const</FONT> string &str1, <FONT color=brown>const</FONT> string &str2)<BR>{<BR> <FONT color=brown>return</FONT> str1.length() < str2.length();<BR>}</PRE></PRE></DIV></DIV>此时，"apple"
和 "winter" 就是相等的，如果在"apple"
出现在"winter"前面，用带stable的函数排序后，他们的次序一定不变，如果你使用的是不带"stable"的函数排序，那么排序完后，
"Winter"有可能在"apple"的前面。
<P></P>
<H4><A 全排序?></A>1.4 全排序 </H4>全排序即把所给定范围所有的元素按照大小关系顺序排列。用于全排序的函数有
<P></P>
<DIV>
<DIV><PRE><PRE><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator><BR><FONT color=brown>void</FONT> sort(RandomAccessIterator first, RandomAccessIterator last);<BR><BR><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator, <FONT color=brown>class</FONT> StrictWeakOrdering><BR><FONT color=brown>void</FONT> sort(RandomAccessIterator first, RandomAccessIterator last,<BR>StrictWeakOrdering comp);<BR><BR><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator><BR><FONT color=brown>void</FONT> stable_sort(RandomAccessIterator first, RandomAccessIterator last);<BR><BR><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator, <FONT color=brown>class</FONT> StrictWeakOrdering><BR><FONT color=brown>void</FONT> stable_sort(RandomAccessIterator first, RandomAccessIterator last, <BR>StrictWeakOrdering comp);</PRE></PRE></DIV></DIV>在第1，3种形式中，sort
和 stable_sort都没有指定比较函数，系统会默认使用operator< 对区间[first,last)内的所有元素进行排序,
因此，如果你使用的类型义军已经重载了operator<函数，那么你可以省心了。第2, 4种形式，你可以随意指定比较函数，应用更为灵活一些。来看看实际应用：
<P>班上有10个学生，我想知道他们的成绩排名。 </P>
<DIV>
<DIV><PRE><PRE><FONT color=navy>#include</FONT> <iostream><BR><FONT color=navy>#include</FONT> <algorithm><BR><FONT color=navy>#include</FONT> <functional><BR><FONT color=navy>#include</FONT> <vector><BR><FONT color=navy>#include</FONT> <string><BR><FONT color=brown>using</FONT> <FONT color=brown>namespace</FONT> std;<BR><BR><FONT color=brown>class</FONT> student{<BR> <FONT color=brown>public</FONT>:<BR> student(<FONT color=brown>const</FONT> string &a, <FONT color=brown>int</FONT> b):name(a), score(b){}<BR> string name;<BR> <FONT color=brown>int</FONT> score;<BR> <FONT color=brown>bool</FONT> <FONT color=brown>operator</FONT> < (<FONT color=brown>const</FONT> student &m)<FONT color=brown>const</FONT> {<BR> <FONT color=brown>return</FONT> score< m.score;<BR> }<BR>};<BR><BR><FONT color=brown>int</FONT> main() {<BR> vector< student> vect;<BR> student st1("<FONT color=blue>Tom</FONT>", 74);<BR> vect.push_back(st1);<BR> st1.name="<FONT color=blue>Jimy</FONT>";<BR> st1.score=56;<BR> vect.push_back(st1);<BR> st1.name="<FONT color=blue>Mary</FONT>";<BR> st1.score=92;<BR> vect.push_back(st1);<BR> st1.name="<FONT color=blue>Jessy</FONT>";<BR> st1.score=85;<BR> vect.push_back(st1);<BR> st1.name="<FONT color=blue>Jone</FONT>";<BR> st1.score=56;<BR> vect.push_back(st1);<BR> st1.name="<FONT color=blue>Bush</FONT>";<BR> st1.score=52;<BR> vect.push_back(st1);<BR> st1.name="<FONT color=blue>Winter</FONT>";<BR> st1.score=77;<BR> vect.push_back(st1);<BR> st1.name="<FONT color=blue>Andyer</FONT>";<BR> st1.score=63;<BR> vect.push_back(st1);<BR> st1.name="<FONT color=blue>Lily</FONT>";<BR> st1.score=76;<BR> vect.push_back(st1);<BR> st1.name="<FONT color=blue>Maryia</FONT>";<BR> st1.score=89;<BR> vect.push_back(st1);<BR> cout<<"<FONT color=blue>------before sort...</FONT>"<<endl;<BR> <FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<"<FONT color=blue>:\t</FONT>"<<vect[i].score<<endl;<BR> stable_sort(vect.begin(), vect.end(),less<student>());<BR> cout <<"<FONT color=blue>-----after sort ....</FONT>"<<endl;<BR> <FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<"<FONT color=blue>:\t</FONT>"<<vect[i].score<<endl;<BR> <FONT color=brown>return</FONT> 0 ;<BR>}</PRE></PRE></DIV></DIV>其输出是：
<PRE>------before sort...<BR>Tom: 74<BR>Jimy: 56<BR>Mary: 92<BR>Jessy: 85<BR>Jone: 56<BR>Bush: 52<BR>Winter: 77<BR>Andyer: 63<BR>Lily: 76<BR>Maryia: 89<BR>-----after sort ....<BR>Bush: 52<BR>Jimy: 56<BR>Jone: 56<BR>Andyer: 63<BR>Tom: 74<BR>Lily: 76<BR>Winter: 77<BR>Jessy: 85<BR>Maryia: 89<BR>Mary: 92<BR></PRE>sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序，而是结合内插排序算法)。<A
href="http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms#MyNote1"
twikiAnchorLink?>注1</A>，可以保证很好的平均性能、复杂度为n*log(n)，由于单纯的快速排序在理论上有最差的情况，性能很低，其算法复杂度为n*n，但目前大部分的STL版本都已经在这方面做了优化，因此你可以放心使用。stable_sort采用的是"归并排序"，分派足够内存是，其算法复杂度为n*log(n),
否则其复杂度为n*log(n)*log(n)，其优点是会保持相等元素之间的相对位置在排序前后保持一致。
<H4><A 局部排序?></A>1.5 局部排序 </H4>局部排序其实是为了减少不必要的操作而提供的排序方式。其函数原型为：
<DIV>
<DIV><PRE><PRE><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator><BR><FONT color=brown>void</FONT> partial_sort(RandomAccessIterator first, <BR>RandomAccessIterator middle,<BR>RandomAccessIterator last);<BR><BR><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator, <FONT color=brown>class</FONT> StrictWeakOrdering><BR><FONT color=brown>void</FONT> partial_sort(RandomAccessIterator first,<BR>RandomAccessIterator middle,<BR>RandomAccessIterator last, <BR>StrictWeakOrdering comp);<BR><BR><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> InputIterator, <FONT color=brown>class</FONT> RandomAccessIterator><BR>RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,<BR>RandomAccessIterator result_first,<BR>RandomAccessIterator result_last);<BR><BR><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> InputIterator, <FONT color=brown>class</FONT> RandomAccessIterator, <BR><FONT color=brown>class</FONT> StrictWeakOrdering><BR>RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,<BR>RandomAccessIterator result_first,<BR>RandomAccessIterator result_last, Compare comp);</PRE></PRE></DIV></DIV>理解了sort
和stable_sort后，再来理解partial_sort 就比较容易了。先看看其用途:
班上有10个学生，我想知道分数最低的5名是哪些人。如果没有partial_sort，你就需要用sort把所有人排好序，然后再取前5个。现在你只需要对分数最低5名排序，把上面的程序做如下修改：
<DIV>
<DIV><PRE><PRE>stable_sort(vect.begin(), vect.end(),less<student>());<BR>替换为：<BR>partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());</PRE></PRE></DIV></DIV>输出结果为：
<PRE>------before sort...<BR>Tom: 74<BR>Jimy: 56<BR>Mary: 92<BR>Jessy: 85<BR>Jone: 56<BR>Bush: 52<BR>Winter: 77<BR>Andyer: 63<BR>Lily: 76<BR>Maryia: 89<BR>-----after sort ....<BR>Bush: 52<BR>Jimy: 56<BR>Jone: 56<BR>Andyer: 63<BR>Tom: 74<BR>Mary: 92<BR>Jessy: 85<BR>Winter: 77<BR>Lily: 76<BR>Maryia: 89<BR></PRE>这样的好处知道了吗？当数据量小的时候可能看不出优势，如果是100万学生，我想找分数最少的5个人......
<P>partial_sort采用的堆排序（heapsort），它在任何情况下的复杂度都是n*log(n).
如果你希望用partial_sort来实现全排序，你只要让middle=last就可以了。 </P>
<P>partial_sort_copy其实是copy和partial_sort的组合。被排序(被复制)的数量是[first,
last)和[result_first, result_last)中区间较小的那个。如果[result_first,
result_last)区间大于[first, last)区间，那么partial_sort相当于copy和sort的组合。 </P>
<H4><A 指定元素排序? nth_element></A>1.6 nth_element 指定元素排序
</H4>nth_element一个容易看懂但解释比较麻烦的排序。用例子说会更方便：<BR>班上有10个学生，我想知道分数排在倒数第4名的学生。<BR>如果要满足上述需求，可以用sort排好序，然后取第4位（因为是由小到大排),
更聪明的朋友会用partial_sort, 只排前4位，然后得到第4位。其实这是你还是浪费，因为前两位你根本没有必要排序，此时，你就需要nth_element:
<DIV>
<DIV><PRE><PRE><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator><BR><FONT color=brown>void</FONT> nth_element(RandomAccessIterator first, RandomAccessIterator nth,<BR>RandomAccessIterator last);<BR><BR><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator, <FONT color=brown>class</FONT> StrictWeakOrdering><BR><FONT color=brown>void</FONT> nth_element(RandomAccessIterator first, RandomAccessIterator nth,<BR>RandomAccessIterator last, StrictWeakOrdering comp);</PRE></PRE></DIV></DIV>对于上述实例需求，你只需要按下面要求修改1.4中的程序：
<DIV>
<DIV><PRE><PRE>stable_sort(vect.begin(), vect.end(),less<student>());<BR>替换为：<BR>nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());</PRE></PRE></DIV></DIV>运行结果为：
<PRE>------before sort...<BR>Tom: 74<BR>Jimy: 56<BR>Mary: 92<BR>Jessy: 85<BR>Jone: 56<BR>Bush: 52<BR>Winter: 77<BR>Andyer: 63<BR>Lily: 76<BR>Maryia: 89<BR>-----after sort ....<BR>Jone: 56<BR>Bush: 52<BR>Jimy: 56<BR>Andyer: 63<BR>Jessy: 85<BR>Mary: 92<BR>Winter: 77<BR>Tom: 74<BR>Lily: 76<BR>Maryia: 89<BR></PRE>第四个是谁？Andyer，这个倒霉的家伙。为什么是begin()+3而不是+4?
我开始写这篇文章的时候也没有在意，后来在<A href="http://www.stlchina.org/bbs/viewpro.php?uid=350"
target=_top>ilovevc</A> 的提醒下，发现了这个问题。begin()是第一个，begin()+1是第二个，...
begin()+3当然就是第四个了。
<H4><A 和stable_partition? partition></A>1.7 partition 和stable_partition
</H4>好像这两个函数并不是用来排序的，'分类'算法，会更加贴切一些。partition就是把一个区间中的元素按照某个条件分成两类。其函数原型为：
<DIV>
<DIV><PRE><PRE><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> ForwardIterator, <FONT color=brown>class</FONT> Predicate><BR>ForwardIterator partition(ForwardIterator first,<BR>ForwardIterator last, Predicate pred)<BR><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> ForwardIterator, <FONT color=brown>class</FONT> Predicate><BR>ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, <BR>Predicate pred);</PRE></PRE></DIV></DIV>看看应用吧：班上10个学生，计算所有没有及格（低于60分）的学生。你只需要按照下面格式替换1.4中的程序：
<DIV>
<DIV><PRE><PRE>stable_sort(vect.begin(), vect.end(),less<student>());<BR>替换为：<BR>student exam("<FONT color=blue>pass</FONT>", 60);<BR>stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));</PRE></PRE></DIV></DIV>其输出结果为：
<PRE>------before sort...<BR>Tom: 74<BR>Jimy: 56<BR>Mary: 92<BR>Jessy: 85<BR>Jone: 56<BR>Bush: 52<BR>Winter: 77<BR>Andyer: 63<BR>Lily: 76<BR>Maryia: 89<BR>-----after sort ....<BR>Jimy: 56<BR>Jone: 56<BR>Bush: 52<BR>Tom: 74<BR>Mary: 92<BR>Jessy: 85<BR>Winter: 77<BR>Andyer: 63<BR>Lily: 76<BR>Maryia: 89<BR></PRE>看见了吗，Jimy，Jone,
Bush(难怪说美国总统比较笨 <IMG title=smile alt=smile
src="详细解说 STL 排序(Sort) - liuruigong_lrg - 网易博客.files/smile.gif" border=0>
)都没有及格。而且使用的是stable_partition, 元素之间的相对次序是没有变.
<H3><A 和容器? Sort></A>2 Sort 和容器 </H3>
<HR>
STL中标准容器主要vector, list, deque, string, set, multiset, map, multimay， 其中set,
multiset, map, multimap都是以树结构的方式存储其元素详细内容请参看：<A
href="http://stl.winterxy.com/html/000039.html" target=_top>学习STL map, STL
set之数据结构基础</A>. 因此在这些容器中，元素一直是有序的。
<P>这些容器的迭代器类型并不是随机型迭代器，因此，上述的那些排序函数，对于这些容器是不可用的。上述sort函数对于下列容器是可用的： </P>
<UL>
<LI>vector
<LI>string
<LI>deque </LI></UL>如果你自己定义的容器也支持随机型迭代器，那么使用排序算法是没有任何问题的。
<P>对于list容器，list自带一个sort成员函数list::sort().
它和算法函数中的sort差不多，但是list::sort是基于指针的方式排序，也就是说，所有的数据移动和比较都是此用指针的方式实现，因此排序后的迭代器一直保持有效（vector中sort后的迭代器会失效).
</P>
<P></P>
<H3><A 选择合适的排序函数?></A>3 选择合适的排序函数 </H3>
<HR>
为什么要选择合适的排序函数？可能你并不关心效率(这里的效率指的是程序运行时间), 或者说你的数据量很小， 因此你觉得随便用哪个函数都无关紧要。
<P>其实不然，即使你不关心效率，如果你选择合适的排序函数，你会让你的代码更容易让人明白，你会让你的代码更有扩充性，逐渐养成一个良好的习惯，很重要吧 <IMG
title=smile alt=smile
src="详细解说 STL 排序(Sort) - liuruigong_lrg - 网易博客.files/smile.gif" border=0> 。 </P>
<P>如果你以前有用过C语言中的qsort,
想知道qsort和他们的比较，那我告诉你，qsort和sort是一样的，因为他们采用的都是快速排序。从效率上看，以下几种sort算法的是一个排序，效率由高到低（耗时由小变大）：
</P>
<OL>
<LI>partion
<LI>stable_partition
<LI>nth_element
<LI>partial_sort
<LI>sort
<LI>stable_sort </LI></OL>记得，以前翻译过Effective STL的文章，其中对<A
href="http://stl.winterxy.com/html/000026.html" target=_top>如何选择排序函数</A>总结的很好：
<UL>
<LI>若需对vector, string, deque, 或 array容器进行全排序，你可选择sort或stable_sort；
<LI>若只需对vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首选.
<LI>若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top
n中的内部顺序，nth_element是最理想的；
<LI>若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开，你最好使用partition或stable_partition；
<LI>若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和
stable_sort排序。若你需要得到partial_sort或nth_element的排序效果，你必须间接使用。正如上面介绍的有几种方式可以选择。
</LI></UL>总之记住一句话： <STRONG>如果你想节约时间，不要走弯路, 也不要走多余的路!</STRONG>
<H3><A 小结?></A>4 小结 </H3>
<HR>
讨论技术就像个无底洞，经常容易由一点可以引申另外无数个技术点。因此需要从全局的角度来观察问题，就像观察STL中的sort算法一样。其实在
STL还有make_heap,
sort_heap等排序算法。本文章没有提到。本文以实例的方式，解释了STL中排序算法的特性，并总结了在实际情况下应如何选择合适的算法。 </DIV>
<DIV class=g_p_center style="WIDTH: 760px">
<DIV class="g_blog_circle g_circle_perm g_t_hide"
id=relateBlogCircle__fks_FXVaIFjMoN6fQjOSRSFbhTNbP47TZJns
style="MARGIN-LEFT: 25px"></DIV></DIV>
<DIV class=g_p_center style="WIDTH: 760px">
<DIV class="g_recent_read g_t_hide"
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?