📄 csdn技术中心 cuj：标准库：标准库中的排序算法.htm
字号:
<TR>
<TD align=middle bgColor=#003399 height=16><FONT
color=#ffffff>关键字</FONT></TD>
<TD width=500> <SPAN
id=ArticleTitle1_ArticleTitle1_lblKeywords>CUJ、STL、排序、Matthew
Austern</SPAN></TD></TR>
<TR>
<TD align=middle bgColor=#003399 height=16><FONT
color=#ffffff>出处</FONT></TD>
<TD> <SPAN
id=ArticleTitle1_ArticleTitle1_lblSource>http://www.cuj.com/experts/1908/austern.htm?topic=experts</SPAN></TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD width=10></TD>
<TD><SPAN id=ArticleContent1_ArticleContent1_lblContent>
<H2 style="MARGIN: auto 0cm; TEXT-ALIGN: center" align=center><SPAN
lang=EN-US style="FONT-SIZE: 16pt; mso-bidi-font-size: 18.0pt"><FONT
face=宋体>The Standard Librarian: Sorting in the Standard
Library<o:p></o:p></FONT></SPAN></H2>
<H3 style="MARGIN: auto 0cm; TEXT-ALIGN: center" align=center><SPAN
lang=EN-US
style="FONT-WEIGHT: normal; FONT-SIZE: 10.5pt; mso-bidi-font-size: 13.5pt"><FONT
face=宋体>Matthew Austern<o:p></o:p></FONT></SPAN></H3>
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="FONT-FAMILY: 宋体"><FONT
size=3>http://www.cuj.com/experts/1908/austern.htm?topic=experts<B><o:p></o:p></B></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT
face=宋体>--------------------------------------------------------------------------------<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT face=宋体><SPAN
style="mso-tab-count: 1">
</SPAN>当你有一个数据序列时，你最想做的操作之一就是排序。将数据排序使得它易于被人理解，而且排序是许多泛型算法的第一步－－即使是计算一系列数字的和这样的微末算法。每个编程系统都提供了几种形式的排序；标准C++运行库提供了6种！（或可能更多，这取决于你怎么数了。）他们有多么大的差异，并且什么时候你该使用其中某一个而不是另外的那些？<o:p></o:p></FONT></FONT></SPAN></P>
<H3 style="MARGIN: auto 0cm"><FONT face=宋体>用泛型算法进行排序</FONT></H3>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT face=宋体><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>C++标准24章有一个小节叫“Sorting and related
operations”。它包含了很多对已序区间进行的操作，和三个排序用泛型算法：sort()，stable_sort()，和partial_sort()。<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT face=宋体><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>前两个，sort()和stable_sort()，本质上有相同的接口：同通常的STL泛型算法一样，传入指明了需要排序的区间的Random
Access Iterator。
同样，作为可选项，你也能提供第三个参数以指明如何比较元素：第三个参数是一个functor，接受两个参数（x和y），在x应该位于y之前时返回true。所以，举例来说，如果v是一个int的vector：<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT face=宋体><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>std::sort(v.begin(),
v.end());<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
style="mso-hansi-font-family: 宋体"><FONT face=宋体><FONT
size=3>将以升序来排序它。要改为降序，你需要提供应该不同的比较方法：<SPAN
lang=EN-US><o:p></o:p></SPAN></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT face=宋体><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>std::sort(v.begin(), v.end(),
std::greater<int>());<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT face=宋体><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>注意，我们正在以greater作为第三参数，而不是greater_equal。这很重要，它是所有STL排序算法的前提条件：比较函数必须在两个参数相同时返回false<B>（WQ注：参看《Effective
STL》Item
21）</B>。在某种程度上，这太武断了：看起来完全可以随便使用“<”或者“<=”这样形式的比较函数来表达一个排序算法的。然而，作出明确的选择是必需的，并且要始终坚持这个选择。标准C++运行库选择了前者。如果你传给sort()一个对等价的参数返回true的functor，你将得到不可预知的、完全依赖于具体实现的结果；在某些系统下，它看起来能工作，而在另外一些系统下可能导致无限循环或内存保护错误。<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT face=宋体><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>对于比较简单的场合，使用stable_sort()代替sort()，你不会看出很多差异。与sort()一样，stable_sort()对[first,
last)区间进行排序，默认是升序，并且，同样你可以提供一个比较函数以改变顺序。如果你读过C++标准，你将会看到sort()和stable_sort()的两个不同：<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText
style="MARGIN: 0cm 0cm 0pt 21pt; TEXT-INDENT: -21pt; tab-stops: list 21.0pt; mso-list: l0 level1 lfo2"><SPAN
lang=EN-US style="FONT-FAMILY: Wingdings"><FONT size=3>l</FONT><SPAN
style="FONT: 7pt 'Times New Roman'">
</SPAN></SPAN><SPAN style="mso-hansi-font-family: 宋体"><FONT
face=宋体><FONT size=3>如名字所示，<SPAN
lang=EN-US>stable_sort()是稳定的。如果两个元素比较结果为等价，stable_sort()不改变它们的相对顺序。
<o:p></o:p></SPAN></FONT></FONT></SPAN></P>
<P class=MsoPlainText
style="MARGIN: 0cm 0cm 0pt 21pt; TEXT-INDENT: -21pt; tab-stops: list 21.0pt; mso-list: l0 level1 lfo2"><SPAN
lang=EN-US style="FONT-FAMILY: Wingdings"><FONT size=3>l</FONT><SPAN
style="FONT: 7pt 'Times New Roman'">
</SPAN></SPAN><SPAN style="mso-hansi-font-family: 宋体"><FONT
size=3><FONT face=宋体>性能上的承诺是不同的。<SPAN lang=EN-US>
<o:p></o:p></SPAN></FONT></FONT></SPAN></P>
<P class=MsoPlainText
style="MARGIN: 0cm 0cm 0pt; TEXT-INDENT: 21pt"><SPAN
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT
face=宋体>第一点，稳定，比较容易懂。它对<SPAN
lang=EN-US>int类型通常无所谓(一个“42”和另外一个“42”完全相同)，但有时对其它数据类型就非常重要了。比如，你正对task根据优先级排序，你或许期望高优先级的task被提到低优先级的task之前，但相同优先级的任务保持它们原来的先后顺序。sort()没有这个承诺，而stable_sort()承诺了这一点。<o:p></o:p></SPAN></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><FONT
face=宋体><SPAN lang=EN-US style="mso-hansi-font-family: 宋体"><FONT
size=3><SPAN style="mso-tab-count: 1">
</SPAN>标准对性能的描述就不怎么直观了：sort()和stable_sort()的承诺都很复杂，并且都不完备。标准说sort()的“平均”复杂度是O(N
log N)，而没有说最坏的情况；stable_sort()的复杂度是O(N (log
N)</FONT></SPAN><SUP><SPAN lang=EN-US
style="FONT-SIZE: 16pt; mso-bidi-font-size: 10.5pt; mso-hansi-font-family: 宋体">2</SPAN></SUP><SPAN
lang=EN-US style="mso-hansi-font-family: 宋体"><FONT
size=3>)，但在有足够额外内存时同样是O( N log
N)。<o:p></o:p></FONT></SPAN></FONT></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT face=宋体><SPAN
style="mso-tab-count: 1">
</SPAN>怎样搞清楚所有这些不同情况？<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><FONT
face=宋体><SPAN lang=EN-US style="mso-hansi-font-family: 宋体"><FONT
size=3><SPAN style="mso-tab-count: 1">
</SPAN>性能的承诺是和特殊的实现技巧联系在一起的，而如果你知道这些技巧是什么的话，这个承诺就更明白了。允许sort()以快速排序（递归分割区间）来实现，而stable_sort()以归并排序（递归归并已序子区间）来实现[注1]。快速排序是已知的最快速排序算法之一，复杂度几乎总是O(N
log N)，但对一些特殊序列是O(N</FONT></SPAN><SUP><SPAN lang=EN-US
style="FONT-SIZE: 16pt; mso-bidi-font-size: 10.5pt; mso-hansi-font-family: 宋体">2</SPAN></SUP><SPAN
lang=EN-US style="mso-hansi-font-family: 宋体"><FONT
size=3>)；如果标准总要求sort()是O(N log
N)，将不能使用快速排序。同样，归并两个子区间在有额外缓冲区以拷贝结果时将很容易实现；归并排序在可以使用与原始区间同样大的辅助缓冲区时是O(N
log N)，如果不能获得任何辅助缓冲区时是O(N (log N)</FONT></SPAN><SUP><SPAN lang=EN-US
style="FONT-SIZE: 16pt; mso-bidi-font-size: 10.5pt; mso-hansi-font-family: 宋体">2</SPAN></SUP><SPAN
lang=EN-US style="mso-hansi-font-family: 宋体"><FONT
size=3>)。如果它只能使用一个较小的辅助缓冲区，复杂度将在两者之间－－但，在现实中，更接近于O(N log
N)。<o:p></o:p></FONT></SPAN></FONT></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT face=宋体><SPAN
style="mso-tab-count: 1">
</SPAN>这解释了标准中说的东西，但还不全。标准说“如果最坏情况时的行为很重要”，你就不该使用sort()。然而，事实并不象标准第一次写下这条建议时那样。许多标准运行库的实作，包括GNU
g++和Microsoft Visual
C++，现在使用快速排序的一个新的变种，称为introsort[注2]<B>（WQ注：参看侯捷《STL源码剖析》）</B>。Introsort一般说来和快速排序同样快，但它的复杂度总是O(N
log N)。 除非你顾虑老的标准库的实作，最差情况时的行为不再成为避免使用sort()的理由。并且，虽然stable_sort
(通常)也是O(N log N)，这个O掩盖了很多细节。<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT face=宋体><SPAN
style="mso-tab-count: 1">
</SPAN>在绝大多数情况下，stable_sort()比sort()慢很多，因为它必须对每个元素作更多操作；这就是你要为“稳定”付出的代价。使用stable_sort()应付等价元素维持原来的相对顺序很重要的情况（比如，根据优先级进行排序，但要对相同优先级的条目保持<B>先来先处理</B>的顺序），而使用sort()处理其它情况。<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT face=宋体><SPAN
style="mso-tab-count: 1">
</SPAN>另一个泛型排序算法是partial_sort()（包括一个小变种，partial_sort_copy()）。它的功能稍有不同，语法也稍有区别：它查找并排序区间内的前n名元素。和其它情况一样，默认是通过“<”比较进行升序排列，但能提供一个functor来改变它。于是，举例来说，如果你只对序列的前10名的元素感兴趣，可以这样找到它们：<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT face=宋体><SPAN
style="mso-tab-count: 1">
</SPAN>partial_sort(first, first+10, last,
greater<T>());<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT
face=宋体>然后，最大的<SPAN lang=EN-US>10个元素将被容纳在[first, fist + 10)(降序排列)，
其余元素容纳在[first + 10,
last)。<o:p></o:p></SPAN></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT face=宋体><SPAN
style="mso-tab-count: 1">
</SPAN>这儿有一个明显的受限情况：如果你写partial_sort(first, last,
last)，那么你正要求partial_sort()排序整个[first,
last)区间。于是，虽然语法稍有不同，你能仍然能以使用sort()的同样的方法使用partial_sort()。有理由这么做吗？实际是没有。查看一下C++标准对复杂度的描述，你将看到partial_sort()和sort一样，也是O(N<SPAN
style="mso-spacerun: yes"> </SPAN>log N)，但是，再一次，这是不完全的描述。两个O(N
log N)的运算不必然有同样的速度；对此例，sort()通常快得多。
<o:p></o:p></FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="mso-hansi-font-family: 宋体"><FONT size=3><FONT face=宋体><SPAN
style="mso-tab-count: 1">
</SPAN>partial_sort()的存在是为了部分排序。假如你有一个一百万个名字的列表，而你需要找前一千个，按字母排序。通过对整个列表排序并忽略后面的部分，你可以得到这一千个名字，但那会非常浪费。使用partial_sort()或partial_sort_copy()会快得多：<o:p></o:p></FONT></FONT></SPAN></P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -