文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > STL全排序,部分排序等
侵权投诉

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容器的前面,

第1页

你可能喜欢

热门文档

相关文档

  • 详细解说 STL 排序

    Winter: 77 Jessy: 85 Maryia: 89 Mary: 92 sort 采用的是成熟的"快速排序算法"(目前大部分 STL 版本已经不是采用简单的快速排序, 而是 结合内插排序算法)。...

  • stl排序总结

    Effective STL 对如何选择排序函数总结的很好: 1) 若需对 vector, string, deque, 或 array 容器进行全排序,你可选择 sort 或 stable_sort; 部分排序 partial_...

  • STl中的排序算法

    所有 STL sort 算法函数的名字列表: 函数名 功能描述 sort 对给定区间所有元素...对给定区间所有元素部分排序 partial_sort_copy 对给定区间复制并排序 nth_...

  • STL排序的几种用法

    STL全排序,部分排序等 4页 免费 STL排序算法 4页 免费 stl排序总结 3页 1...STL 排序方法 在<algorithm>中 sort 稳定排序 、堆排序的用法举例 //#include...

  • STL排序算法

    STL排序算法_计算机软件及应用_IT/计算机_专业资料。数据结构,算法基础, STL...II、部分排序 这些部分排序功能能够完成一段数据(而不是所有)的排序,在适当的...

  • 标准模板库STL_排序(Sort)算法

    Lily: 76 Winter: 77 Jessy: 85 Maryia: 89 Mary: 92 sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排序算法...

  • C++ STL中Map的按Key排序和按Value排序

    = name_score_map.end(); ++iter) { cout << *iter << endl; 【运行结果】 二、C++ STL 中 Map 的按 Value 排序在第一部分中,我们借助 map 提供的...

  • 全排列的STL实现

    全排列的 STL 实现 全排列在很多程序都有应用,是一个很常见的算法,常规的算法... STL全排序,部分排序等 4页 免费 STL排序算法 4页 免费 STL map 按值排序 ...

  • STL自定义排序准则

    STL自定义排序准则_计算机软件及应用_IT/计算机_专业资料。修改set和map的排序... STL全排序,部分排序等 4页 免费 STL排序算法 4页 免费 stl排序总结 3页 1...

  • 排序查找的经典算法与STL

    排序查找的经典算法与STL_理学_高等教育_教育专区。关于编程的排序算法排序查找的经典算法与STL InkBest 冒泡排序 ? 三个杯子A,B,C ,A中装了红色的水,B 中装...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email