📄 详细解说 stl 排序(sort) -- stlsortalgorithms.htm
字号:
<P>STL几乎封装了所有的数据结构中的算法，从链表到队列，从向量到堆栈，对hash到二叉树，从搜索到排序，从增加到删除......可以说，如果你理解了STL，你会发现你已不用拘泥于算法本身，从而站在巨人的肩膀上去考虑更高级的应用。
<P>排序是最广泛的算法之一，本文详细介绍了STL中不同排序算法的用法和区别。
<H3><A name="1 STL提供的Sort 算法"></A>1 STL提供的Sort 算法 </H3>
<HR>
C++之所以得到这么多人的喜欢，是因为它既具有面向对象的概念，又保持了C语言高效的特点。STL
排序算法同样需要保持高效。因此，对于不同的需求，STL提供的不同的函数，不同的函数，实现的算法又不尽相同。
<H4><A name="1.1 所有sort算法介绍"></A>1.1 所有sort算法介绍
</H4>所有的sort算法的参数都需要输入一个范围，[begin,
end)。这里使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator),
也就是说可以随机访问的迭代器，如：it+n什么的。（partition 和stable_partition 除外）
<P>如果你需要自己定义比较函数，你可以把你定义好的仿函数(functor)作为参数传入。每种算法都支持传入比较函数。以下是所有STL
sort算法函数的名字列表:
<TABLE class=twikiTable
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 class=twikiTableEven>
<TH class=twikiFirstCol bgColor=#dadada maxcols="0"><A
title="Sort by this column" style="COLOR: #000000"
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: #000000"
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 class=twikiTableOdd>
<TD class=twikiFirstCol bgColor=#eaeaea>sort </TD>
<TD bgColor=#eaeaea>对给定区间所有元素进行排序 </TD></TR>
<TR class=twikiTableEven>
<TD class=twikiFirstCol bgColor=#ffffff>stable_sort </TD>
<TD bgColor=#ffffff>对给定区间所有元素进行稳定排序 </TD></TR>
<TR class=twikiTableOdd>
<TD class=twikiFirstCol bgColor=#eaeaea>partial_sort </TD>
<TD bgColor=#eaeaea>对给定区间所有元素部分排序 </TD></TR>
<TR class=twikiTableEven>
<TD class=twikiFirstCol bgColor=#ffffff>partial_sort_copy </TD>
<TD bgColor=#ffffff>对给定区间复制并排序 </TD></TR>
<TR class=twikiTableOdd>
<TD class=twikiFirstCol bgColor=#eaeaea>nth_element </TD>
<TD bgColor=#eaeaea>找出给定区间的某个位置对应的元素 </TD></TR>
<TR class=twikiTableEven>
<TD class=twikiFirstCol bgColor=#ffffff>is_sorted </TD>
<TD bgColor=#ffffff>判断一个区间是否已经排好序 </TD></TR>
<TR class=twikiTableOdd>
<TD class=twikiFirstCol bgColor=#eaeaea>partition </TD>
<TD bgColor=#eaeaea>使得符合某个条件的元素放在前面 </TD></TR>
<TR class=twikiTableEven>
<TD class="twikiFirstCol twikiLast" bgColor=#ffffff>stable_partition </TD>
<TD class=twikiLast bgColor=#ffffff>相对稳定的使得符合某个条件的元素放在前面
</TD></TR></TBODY></TABLE>其中nth_element
是最不易理解的，实际上，这个函数是用来找出第几个。例如：找出包含7个元素的数组中排在中间那个数的值，此时，我可能不关心前面，也不关心后面，我只关心排在第四位的元素值是多少。
<H4><A name="1.2 sort 中的比较函数"></A>1.2 sort 中的比较函数
</H4>当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数。
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE>vector < <FONT color=brown>int</FONT> > vect;
<FONT color=green>//...</FONT>
sort(vect.begin(), vect.end());
<FONT color=green>//此时相当于调用</FONT>
sort(vect.begin(), vect.end(), less<<FONT color=brown>int</FONT>>() );</PRE></PRE></DIV></DIV>上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数，以下是仿函数列表:
<TABLE class=twikiTable
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 class=twikiTableEven>
<TH class=twikiFirstCol bgColor=#dadada maxcols="0"><A
title="Sort by this column" style="COLOR: #000000"
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: #000000"
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 class=twikiTableOdd>
<TD class=twikiFirstCol bgColor=#eaeaea>equal_to </TD>
<TD bgColor=#eaeaea>相等 </TD></TR>
<TR class=twikiTableEven>
<TD class=twikiFirstCol bgColor=#ffffff>not_equal_to </TD>
<TD bgColor=#ffffff>不相等 </TD></TR>
<TR class=twikiTableOdd>
<TD class=twikiFirstCol bgColor=#eaeaea>less </TD>
<TD bgColor=#eaeaea>小于 </TD></TR>
<TR class=twikiTableEven>
<TD class=twikiFirstCol bgColor=#ffffff>greater </TD>
<TD bgColor=#ffffff>大于 </TD></TR>
<TR class=twikiTableOdd>
<TD class=twikiFirstCol bgColor=#eaeaea>less_equal </TD>
<TD bgColor=#eaeaea>小于等于 </TD></TR>
<TR class=twikiTableEven>
<TD class="twikiFirstCol twikiLast" bgColor=#ffffff>greater_equal </TD>
<TD class=twikiLast bgColor=#ffffff>大于等于
</TD></TR></TBODY></TABLE>需要注意的是，这些函数不是都能适用于你的sort算法，如何选择，决定于你的应用。另外，不能直接写入仿函数的名字，而是要写其重载的()函数：
<PRE>less<int>()
greater<int>()
</PRE>当你的容器中元素时一些标准类型（int float
char)或者string时，你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型的'<'操作赋。
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE><FONT color=navy>#include</FONT> <iostream>
<FONT color=navy>#include</FONT> <algorithm>
<FONT color=navy>#include</FONT> <functional>
<FONT color=navy>#include</FONT> <vector>
<FONT color=brown>using</FONT> <FONT color=brown>namespace</FONT> std;
<FONT color=brown>class</FONT> myclass {
<FONT color=brown>public</FONT>:
myclass(<FONT color=brown>int</FONT> a, <FONT color=brown>int</FONT> b):first(a), second(b){}
<FONT color=brown>int</FONT> first;
<FONT color=brown>int</FONT> second;
<FONT color=brown>bool</FONT> <FONT color=brown>operator</FONT> < (<FONT color=brown>const</FONT> myclass &m)<FONT color=brown>const</FONT> {
<FONT color=brown>return</FONT> first < m.first;
}
};
<FONT color=brown>bool</FONT> less_second(<FONT color=brown>const</FONT> myclass & m1, <FONT color=brown>const</FONT> myclass & m2) {
<FONT color=brown>return</FONT> m1.second < m2.second;
}
<FONT color=brown>int</FONT> main() {
vector< myclass > vect;
<FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < 10 ; i ++){
myclass my(10-i, i*3);
vect.push_back(my);
}
<FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < vect.size(); i ++)
cout<<"<FONT color=blue>(</FONT>"<<vect[i].first<<"<FONT color=blue>,</FONT>"<<vect[i].second<<"<FONT color=blue>)\n</FONT>";
sort(vect.begin(), vect.end());
cout<<"<FONT color=blue>after sorted by first:</FONT>"<<endl;
<FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < vect.size(); i ++)
cout<<"<FONT color=blue>(</FONT>"<<vect[i].first<<"<FONT color=blue>,</FONT>"<<vect[i].second<<"<FONT color=blue>)\n</FONT>";
cout<<"<FONT color=blue>after sorted by second:</FONT>"<<endl;
sort(vect.begin(), vect.end(), less_second);
<FONT color=brown>for</FONT>(<FONT color=brown>int</FONT> i = 0 ; i < vect.size(); i ++)
cout<<"<FONT color=blue>(</FONT>"<<vect[i].first<<"<FONT color=blue>,</FONT>"<<vect[i].second<<"<FONT color=blue>)\n</FONT>";
<FONT color=brown>return</FONT> 0 ;
}</PRE></PRE></DIV></DIV>知道其输出结果是什么了吧： <PRE>(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
after sorted by first:
(1,27)
(2,24)
(3,21)
(4,18)
(5,15)
(6,12)
(7,9)
(8,6)
(9,3)
(10,0)
after sorted by second:
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
</PRE>
<H4><A name="1.3 sort 的稳定性"></A>1.3 sort 的稳定性 </H4>你发现有sort和stable_sort，还有
partition 和stable_partition，
感到奇怪吧。其中的区别是，带有stable的函数可保证相等元素的原本相对次序在排序后保持不变。或许你会问，既然相等，你还管他相对位置呢，也分不清楚谁是谁了？这里需要弄清楚一个问题，这里的相等，是指你提供的函数表示两个元素相等，并不一定是一摸一样的元素。
<P>例如，如果你写一个比较函数:
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE><FONT color=brown>bool</FONT> less_len(<FONT color=brown>const</FONT> string &str1, <FONT color=brown>const</FONT> string &str2)
{
<FONT color=brown>return</FONT> str1.length() < str2.length();
}</PRE></PRE></DIV></DIV>此时，"apple" 和 "winter" 就是相等的，如果在"apple"
出现在"winter"前面，用带stable的函数排序后，他们的次序一定不变，如果你使用的是不带"stable"的函数排序，那么排序完后，"Winter"有可能在"apple"的前面。
<P>
<H4><A name="1.4 全排序"></A>1.4 全排序 </H4>全排序即把所给定范围所有的元素按照大小关系顺序排列。用于全排序的函数有
<P>
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE><FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator>
<FONT color=brown>void</FONT> sort(RandomAccessIterator first, RandomAccessIterator last);
<FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator, <FONT color=brown>class</FONT> StrictWeakOrdering>
<FONT color=brown>void</FONT> sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
<FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator>
<FONT color=brown>void</FONT> stable_sort(RandomAccessIterator first, RandomAccessIterator last);
<FONT color=brown>template</FONT> <<FONT color=brown>class</FONT> RandomAccessIterator, <FONT color=brown>class</FONT> StrictWeakOrdering>
<FONT color=brown>void</FONT> stable_sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);</PRE></PRE></DIV></DIV>在第1，3种形式中，sort 和
stable_sort都没有指定比较函数，系统会默认使用operator< 对区间[first,last)内的所有元素进行排序,
因此，如果你使用的类型义军已经重载了operator<函数，那么你可以省心了。第2, 4种形式，你可以随意指定比较函数，应用更为灵活一些。来看看实际应用：
<P>班上有10个学生，我想知道他们的成绩排名。
<DIV class=BeautifierPlugin>
<DIV class=fragment><PRE><PRE><FONT color=navy>#include</FONT> <iostream>
<FONT color=navy>#include</FONT> <algorithm>
<FONT color=navy>#include</FONT> <functional>
<FONT color=navy>#include</FONT> <vector>
<FONT color=navy>#include</FONT> <string>
<FONT color=brown>using</FONT> <FONT color=brown>namespace</FONT> std;
<FONT color=brown>class</FONT> student{
<FONT color=brown>public</FONT>:
student(<FONT color=brown>const</FONT> string &a, <FONT color=brown>int</FONT> b):name(a), score(b){}
string name;
<FONT color=brown>int</FONT> score;
<FONT color=brown>bool</FONT> <FONT color=brown>operator</FONT> < (<FONT color=brown>const</FONT> student &m)<FONT color=brown>const</FONT> {
<FONT color=brown>return</FONT> score< m.score;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -