排序一直是数据结构中的常用算法，STL提供的排序算法非常丰富，如何有效 使用就值得探讨。在网上没有找到条款31的翻译，于是我自己翻译了。－－ Winter
如何进行排序？让我数数有几种方法。
一旦程序员需对容 器元素进行排序，sort算法马上就会出现在他的脑海(可能有些程序员会想到 qsort，但详细阅读条款46后，他们会放弃使用qsort的想法，转而使用sort算法 )。
sort是一个非常优秀的算法，但并当你并不真正需要它的时候，其实 就是一种浪费。有时你并不需要一个完整的排序（简称为全排序）。例如，你现 有一个包含Widget对象（Widget意为“小挂件”）的vector容器，并 且你想把其中质量最好的20个Widget送给你最好的客户，那么你需做的只是找出 这20个质量最好的Widget元素，剩下的并不需关心它们的顺序。这时你需要的是 部分排序（相对于全排序），恰好在算法中就有一个名副其实的部分排序函数函 数：partial_sort：
bool qualityCompare(const Widget& lhs, const Widget& rhs)
{
// lhs的质量不比rhs的质量差时返回true，否则返回false
}
…
partial_sort (widgets.begin(), // 把质量最好的20元素
widgets.begin() + 20, // 顺序放入widgets容器中
widgets.end(),
qualityCompare);
… // 使用 widgets...
通过调用partial_sort，容器中开始的20个元素就是你需要的质量最好的20 个Widget，并按顺序排列，质量排第一的就是widgets[0], 紧接着就是widgets [1]，依次类推。这样你就可以把质量第一的Widget送给你最好的顾客，质量第 二的Widget就可以送给下一个顾客，很方便吧，更方便的还在后面呢。
如果你只是想把这20个质量最好的Widget礼物送给你最好的20位顾客，而不需要 给他们一一对应，partial_sort在这里就有些显得大材小用了。因为在这里，你 只需要找出这20个元素，而不需要对它们本身进行排序。这时你需要的不是 partial_sort，而是nth_element。
nth_element排序算法只是对一个区 间进行排序，一直到你指定的第n个位置上放上正确的元素为止，也就是说，和 你进行全排序和nth_element排序相比，其共同点就是第n个位置是同一个元素。 当nth_element函数运行后，在全排序中应该在位置n之后的元素不会出现在n的 前面，应该在位置n前面的元素也不会出现在n的后面。听起来有些费解，主要是 我不得不谨慎地使用我的语言来描述nth_element的功能。别着急，呆会儿我会 给你解释为什么，现在先让我们来看看nth_element是如何让质量最好的20个 widget礼物排在vector容器的前面的：
nth_element (widgets.begin(), // 把质量最好的20元素放在
widgets.begin() + 20, // widgets容器的前面,
widgets.end(), // 但并不关心这20个元素
qualityCompare); //本身内部的顺序
你可以看出，调用nth_element函数和调用partial_sort函数在本质上没有区 别，唯一的不同在于partial_sort把前20个元素还进行排列了，而nth_element 并不关系他们内部的顺序。两个算法都实现了同样的功能：把质量最好的20个元 素放在vector容器的开始部分。
这样引起了一个重要的问题：要是质量 一样的元素，排序算法将会如何处理呢？假设有12个元素的质量都为1（最好等 级），15个元素的质量等级为2（质量次之），如果要选择20个最好的Widget， 则先选12个质量为1的元素，然后从15个中选出8个质量为2的元素。到底 nth_element和partial_sort如何从15个中选出8个，依据何在？换句话说，当多 个元素有同样的比较值时，排序算法如何决定谁先谁后？
对于 partial_sort和nth_element算法来说，你无法控制它们，对于比较值相同的元 素它们想怎么排就怎么排（查看条款19，了解两个值相等的定义）。在我们上面 的例子中，面对需要从15个等级为2的元素选出8个增加到top 20中去，他们会任 意选取。这样做也有它的道理：如果你要求得到20个质量最好的Widget，同时有 些Widget的质量又一样，当你得到20个元素至少不比剩下的那些质量差，这已经 达到你的要求，你就不能抱怨什么了。