Effective STL理解你的排序操作

排序一直是数据结构中的常用算法，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，了解两

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!