the standard librarian: sorting in the standard library
matthew austern
http://www.cuj.com/experts/1908/austern.htm?topic=experts
--------------------------------------------------------------------------------
当你有一个数据序列时，你最想做的操作之一就是排序。将数据排序使得它易于被人理解，而且排序是许多泛型算法的第一步－－即使是计算一系列数字的和这样的微末算法。每个编程系统都提供了几种形式的排序；标准c++运行库提供了6种！（或可能更多，这取决于你怎么数了。）他们有多么大的差异，并且什么时候你该使用其中某一个而不是另外的那些？
用泛型算法进行排序
c++标准24章有一个小节叫“sorting and related operations”。它包含了很多对已序区间进行的操作，和三个排序用泛型算法：sort()，stable_sort()，和partial_sort()。
前两个，sort()和stable_sort()，本质上有相同的接口：同通常的stl泛型算法一样，传入指明了需要排序的区间的random access iterator。 同样，作为可选项，你也能提供第三个参数以指明如何比较元素：第三个参数是一个functor，接受两个参数（x和y），在x应该位于y之前时返回true。所以，举例来说，如果v是一个int的vector：
std::sort(v.begin(), v.end());
将以升序来排序它。要改为降序，你需要提供应该不同的比较方法：
std::sort(v.begin(), v.end(), std::greater<int>());
注意，我们正在以greater作为第三参数，而不是greater_equal。这很重要，它是所有stl排序算法的前提条件：比较函数必须在两个参数相同时返回false（wq注：参看《effective stl》item 21）。在某种程度上，这太武断了：看起来完全可以随便使用“<”或者“<=”这样形式的比较函数来表达一个排序算法的。然而，作出明确的选择是必需的，并且要始终坚持这个选择。标准c++运行库选择了前者。如果你传给sort()一个对等价的参数返回true的functor，你将得到不可预知的、完全依赖于具体实现的结果；在某些系统下，它看起来能工作，而在另外一些系统下可能导致无限循环或内存保护错误。
对于比较简单的场合，使用stable_sort()代替sort()，你不会看出很多差异。与sort()一样，stable_sort()对[first, last)区间进行排序，默认是升序，并且，同样你可以提供一个比较函数以改变顺序。如果你读过c++标准，你将会看到sort()和stable_sort()的两个不同：
l 如名字所示，stable_sort()是稳定的。如果两个元素比较结果为等价，stable_sort()不改变它们的相对顺序。
l 性能上的承诺是不同的。
