📄 详细解说 stl 排序(sort) -- stlsortalgorithms.htm
字号:
};
<FONT color=brown>int</FONT> main() {
vector< student> vect;
student st1("<FONT color=blue>Tom</FONT>", 74);
vect.push_back(st1);
st1.name="<FONT color=blue>Jimy</FONT>";
st1.score=56;
vect.push_back(st1);
st1.name="<FONT color=blue>Mary</FONT>";
st1.score=92;
vect.push_back(st1);
st1.name="<FONT color=blue>Jessy</FONT>";
st1.score=85;
vect.push_back(st1);
st1.name="<FONT color=blue>Jone</FONT>";
st1.score=56;
vect.push_back(st1);
st1.name="<FONT color=blue>Bush</FONT>";
st1.score=52;
vect.push_back(st1);
st1.name="<FONT color=blue>Winter</FONT>";
st1.score=77;
vect.push_back(st1);
st1.name="<FONT color=blue>Andyer</FONT>";
st1.score=63;
vect.push_back(st1);
st1.name="<FONT color=blue>Lily</FONT>";
st1.score=76;
vect.push_back(st1);
st1.name="<FONT color=blue>Maryia</FONT>";
st1.score=89;
vect.push_back(st1);
cout<<"<FONT color=blue>------before sort...</FONT>"<<endl;
<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;
stable_sort(vect.begin(), vect.end(),less<student>());
cout <<"<FONT color=blue>-----after sort ....</FONT>"<<endl;
<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;
<FONT color=brown>return</FONT> 0 ;
}</PRE></PRE></DIV></DIV>其输出是： <PRE>------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Lily: 76
Winter: 77
Jessy: 85
Maryia: 89
Mary: 92
</PRE>sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序，而是结合内插排序算法)。<A
class="twikiCurrentTopicLink twikiAnchorLink"
href="http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms#MyNote1">注1</A>，可以保证很好的平均性能、复杂度为n*log(n)，由于单纯的快速排序在理论上有最差的情况，性能很低，其算法复杂度为n*n，但目前大部分的STL版本都已经在这方面做了优化，因此你可以放心使用。stable_sort采用的是"归并排序"，分派足够内存是，其算法复杂度为n*log(n),
否则其复杂度为n*log(n)*log(n)，其优点是会保持相等元素之间的相对位置在排序前后保持一致。
<H4><A name="1.5 局部排序"></A>1.5 局部排序 </H4>局部排序其实是为了减少不必要的操作而提供的排序方式。其函数原型为：
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator>
<FONT color=brown>void</FONT> partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
<FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator, <FONT color=brown>class</FONT> StrictWeakOrdering>
<FONT color=brown>void</FONT> partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
StrictWeakOrdering comp);
<FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> InputIterator, <FONT color=brown>class</FONT> RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
<FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> InputIterator, <FONT color=brown>class</FONT> RandomAccessIterator,
<FONT color=brown>class</FONT> StrictWeakOrdering>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);</PRE></PRE></DIV></DIV>理解了sort
和stable_sort后，再来理解partial_sort 就比较容易了。先看看其用途:
班上有10个学生，我想知道分数最低的5名是哪些人。如果没有partial_sort，你就需要用sort把所有人排好序，然后再取前5个。现在你只需要对分数最低5名排序，把上面的程序做如下修改：
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE>stable_sort(vect.begin(), vect.end(),less<student>());
替换为：
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());</PRE></PRE></DIV></DIV>输出结果为：
<PRE>------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Lily: 76
Maryia: 89
</PRE>这样的好处知道了吗？当数据量小的时候可能看不出优势，如果是100万学生，我想找分数最少的5个人......
<P>partial_sort采用的堆排序（heapsort），它在任何情况下的复杂度都是n*log(n).
如果你希望用partial_sort来实现全排序，你只要让middle=last就可以了。
<P>partial_sort_copy其实是copy和partial_sort的组合。被排序(被复制)的数量是[first,
last)和[result_first, result_last)中区间较小的那个。如果[result_first,
result_last)区间大于[first, last)区间，那么partial_sort相当于copy和sort的组合。
<H4><A name="1.6 nth_element 指定元素排序"></A>1.6 nth_element 指定元素排序
</H4>nth_element一个容易看懂但解释比较麻烦的排序。用例子说会更方便：<BR>班上有10个学生，我想知道分数排在倒数第4名的学生。<BR>如果要满足上述需求，可以用sort排好序，然后取第4位（因为是由小到大排),
更聪明的朋友会用partial_sort, 只排前4位，然后得到第4位。其实这是你还是浪费，因为前两位你根本没有必要排序，此时，你就需要nth_element:
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator>
<FONT color=brown>void</FONT> nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
<FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator, <FONT color=brown>class</FONT> StrictWeakOrdering>
<FONT color=brown>void</FONT> nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp);</PRE></PRE></DIV></DIV>对于上述实例需求，你只需要按下面要求修改1.4中的程序：
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE>stable_sort(vect.begin(), vect.end(),less<student>());
替换为：
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());</PRE></PRE></DIV></DIV>运行结果为：
<PRE>------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jone: 56
Bush: 52
Jimy: 56
Andyer: 63
Jessy: 85
Mary: 92
Winter: 77
Tom: 74
Lily: 76
Maryia: 89
</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 name="1.7 partition 和stable_partition"></A>1.7 partition
和stable_partition
</H4>好像这两个函数并不是用来排序的，'分类'算法，会更加贴切一些。partition就是把一个区间中的元素按照某个条件分成两类。其函数原型为：
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> ForwardIterator, <FONT color=brown>class</FONT> Predicate>
ForwardIterator partition(ForwardIterator first,
ForwardIterator last, Predicate pred)
<FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> ForwardIterator, <FONT color=brown>class</FONT> Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last,
Predicate pred);</PRE></PRE></DIV></DIV>看看应用吧：班上10个学生，计算所有没有及格（低于60分）的学生。你只需要按照下面格式替换1.4中的程序：
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE>stable_sort(vect.begin(), vect.end(),less<student>());
替换为：
student exam("<FONT color=blue>pass</FONT>", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));</PRE></PRE></DIV></DIV>其输出结果为：
<PRE>------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jimy: 56
Jone: 56
Bush: 52
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
</PRE>看见了吗，Jimy，Jone, Bush(难怪说美国总统比较笨 <IMG title=smile alt=smile
src="详细解说 STL 排序(Sort) -- STLSortAlgorithms.files/smile.gif" border=0>
)都没有及格。而且使用的是stable_partition, 元素之间的相对次序是没有变.
<H3><A name="2 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函数对于下列容器是可用的：
<UL>
<LI>vector
<LI>string
<LI>deque </LI></UL>如果你自己定义的容器也支持随机型迭代器，那么使用排序算法是没有任何问题的。
<P>对于list容器，list自带一个sort成员函数list::sort().
它和算法函数中的sort差不多，但是list::sort是基于指针的方式排序，也就是说，所有的数据移动和比较都是此用指针的方式实现，因此排序后的迭代器一直保持有效（vector中sort后的迭代器会失效).
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -