STl中的排序算法详细解析
1. 所有STL sort算法函数的名字列表:
函数名 功能描述
sort 对给定区间所有元素进行排序
stable_sort 对给定区间所有元素进行稳定排序
partial_sort 对给定区间所有元素部分排序
partial_sort_copy 对给定区间复制并排序
nth_element 找出给定区间的某个位置对应的元素
is_sorted 判断一个区间是否已经排好序
partition 使得符合某个条件的元素放在前面
stable_partition 相对稳定的使得符合某个条件的元素放在前面
2. 比较函数:
当你需要按照某种特定方式进行排序时,你需要给sort指定比较函数,否则程序会自动提供给你一个比较函数
vector < int > vect;
sort(vect.begin(), vect.end());//此时相当于调用
sort(vect.begin(), vect.end(), less<int>() );
sort 中的其他比较函数
equal_to 相等
not_equal_to 不相等
less 小于
greater 大于
less_equal 小于等于
greater_equal 大于等于
上述例子中系统 自己为sort提供了less仿函数。在STL中还提供了其他仿函 数,以下是仿函数列表: 不能直接写入仿 函数的名字,而是要写其重载的()函数: less<int>();
当你的容器中元 素时一些标准类型(int float char)或者string时,你可以直 接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序,你可以有两种方法来达到效果:一种是自己写比较函数。另一种是重载类型的'<'操作赋。
3. 全排序:
全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排序算法)。复杂度为n*log(n)。stable_sort采用的是"归并排序",分派足够内存时,其算法复杂度为n*log(n), 否则 其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。
用于全排序的函 数有:
1.void sort(RandomAccessIterator first, RandomAccessIterator last);
2.void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);
3.void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
4.void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
4. 局部排序:
partial_sort采用的堆排序(heapsort),它在任何情况下的复杂度都是n*log(n)。
局部排序其实是为了减少不必要的操作而提供的排序方式。
其函数原型为:
4.1 void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);
4.2 void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last, StrictWeakOrdering comp);
4.3 RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last);
4.4 RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last, Compare comp);
例如:班上有1000个学生,我想知道分数最低的5名是哪些人。
partial_sort(vect.begin(),vect.begin()+5,vect.end(),less<student>());
5. nth_element 指定元素排序
5.1 void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
5.2 void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last,
StrictWeakOrdering comp);
例如:班上有1000个学生,我想知道分数排在倒数第4名的学生。
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());
6. partition 和stable_partition
partition就是把一个区间中的元素按照某个条件分成两类,并没有排序。
其函数原型为:
6.1 ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)
6.2 ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
例如:班上10个学生,计算所有没有及格(低于60分)的学生:
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));
7. 效率由高到低(耗时由小变大):
partion
stable_partition
nth_element
partial_sort
sort
stable_sort
8. Effective STL对如何选择排序函数总结的很好:
8.1 若需对vector, string, deque, 或array容器进行全排序,你可选择sort或stable_sort;
8.2 若只需对vector, string, deque, 或array容器中取得top n的元素,部分排序partial_sort是首选.
8.3 若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部 顺序,nth_element是最 理想的;
8.4 若你需要从标准序列容器或者array中把满足某个条件 或者不满足某个条件的元素分开,你最好使用partition或stable_partition;
8.5 若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代替sort和stable_sort排 序。
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要为大家详细介绍了C/C++实现八大排序算法汇总,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了zlib库压缩和解压字符串STL string的实例详解的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++ STL中的容器适配器实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-20
- 这篇文章主要介绍了C语言演示对归并排序算法的优化实现,归并排序的最差时间复杂度为(n\log n),最优时间复杂为(n),存在可以改进的空间,需要的朋友可以参考下...2020-04-25
- 冒泡排序和快速排序算法在开发应用中各有优点了,下面我们来看几个关于php排序的几个例子。 使用PHP描述冒泡排序和快速排序算法,对象可以是一个数组。 使用PHP描...2016-11-25
- <STL 源码剖析>将其描述为空间配置器,理由是allocator可以将其它存储介质(例如硬盘)做为stl 容器的存储空间。由于内存是allocator管理的主要部分,因此,本文以STL内存管理为出发点介绍allocator...2020-04-25
- 这篇文章主要为大家详细介绍了C++排序算法之插入排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)
这篇文章主要介绍了stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列),需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了堆排序算法(选择排序改进),有需要的朋友可以参考一下...2020-04-25
- function quickSort(&$data, $beg, $end) 02 { 03 if ($end > $beg) { 04 $piv = $data[$beg]; 05 $k = $beg + 1; 06 $r = $end; 07 while ($k < $r) { 08 if...2016-11-25
stl容器set,map,vector之erase用法与返回值详细解析
在使用 list、set 或 map遍历删除某些元素时可以这样使用,如下所示...2020-04-25- 这篇文章主要介绍了一些常用排序算法整理,插入排序算法、直接插入排序、希尔排序、选择排序、冒泡排序等排序,需要的朋友可以参考下...2020-04-25
PHP常用排序算法实例小结【基本排序,冒泡排序,快速排序,插入排序】
小编推荐的这篇文章介绍了PHP常用排序算法实例小结,基本排序,冒泡排序,快速排序,插入排序,非常实用,有兴趣的同学快来看看吧。 代码如下复制代码classbevin{public$pub...2017-07-06- 关于set,必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序...2020-04-25
- 这篇文章主要介绍了Java排序算法三之归并排序的递归与非递归的实现示例解析,文章通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-05
- 这篇文章主要介绍了php排序算法,结合实例形式分析了php数据查询、排序、数组去重、遍历与排序的相关操作技巧与注意事项,需要的朋友可以参考下...2016-10-20
- 这篇文章主要介绍了c语言实现奇偶排序算法,有需要的朋友可以参考一下...2020-04-25