STl中的排序算法详细解析

软件编程 C 语言 分类:[default] 更新日期: 2015-11-09
全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的"快速排序算法"目前大部分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排 序。


> 本站内容系网友提交或本网编辑转载,其目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题,请及时与本网联系,我们将在第一时间删除内容!

相关文章
  • php项目开发中用到的快速排序算法分析
    这篇文章主要介绍了php项目开发中用到的快速排序算法,结合实例形式详细分析了php快速排序的原理与使用方法,需要的朋友可以参考下本文实例讲述了php项目开发中用到的快速排序算法.分享给大家供大家参考,具体如下: 实际上在,做web开发,比较少遇到使用一些算法之类的,毕竟不是做搜索引擎,也不是写底层(比如写个类似于mysql这样的数据库,里面需要自己实现排序算 ...
  • 探讨Ajax中有关readyState状态值和status状态码)的问题
    这篇文章主要介绍了探讨Ajax中有关readyState状态值和status状态码的问题的相关资料,非常不错,具有参考借鉴价值,需要的朋友可以参考下先看下面一段代码,然后给大家详细介绍,Ajax中有关readyState(状态值)和status(状态码)的问题,具体内容如下所示: var getXmlHttpRequest = function () { t ...
  • Swift中内置的集合类型学习笔记
    Swift中内置的集合类型学习笔记
    Swift中自带数组.set.字典三大集合类型,这里将学习过程中的基础的Swift中内置的集合类型学习笔记进行整理,需要的朋友可以参考下一.引言 Swift中提供了3种集合类型,Array数据类型,Set集合类型,Dictionary字典类型.Array用于存放一组有序的数据,数据角标从0开始一次递增:Set用于存放一组无序的数据,数据不可以重复:Dicti ...
  • MongoDB的Master-Slave主从模式配置及主从复制要点解析
    主从复制是数据库运维中一种常见的备份方式,这里我们来看一下MongoDB的Master-Slave主从模式配置及主从复制要点解析,需要的朋友可以参考下主从配置mongodb的master-slave模式配置方式如下1.keyFile生成key_file openssl rand -base64 741 > mongo_key 将mongo_key 分别 ...
  • js选择器全面解析
    下面小编就为大家带来一篇js选择器全面解析.小编觉得挺不错的,现在就分享给大家,也给大家做个参考.一起跟随小编过来看看吧原生JS选择器有getElementById.getElementsByName.getElementsByTagName和getElementsByClassName这四个,下面我就一个一个介绍这四个选择器的用法. 1.getElemen ...
  • Bootstrap中文本框的宽度变窄并且加入一副验证码图片的实现方法
    Bootstrap中文本框的宽度变窄并且加入一副验证码图片的实现方法
    这篇文章主要介绍了Bootstrap中文本框的宽度变窄并且加入一副验证码图片的实现方法的相关资料,非常不错,具有参考借鉴价值,需要的朋友可以参考下今天项目经理刚交给一个活儿,要我实现这样一个功能:要实现的是验证码文本框变窄一点,然后右边加入一副验证码图片,并且在响应式布局的情况下在移动端访问的时候验证码图片能保持和验证码文本框在同一行,这个怎么做?难为了半天 ...
猜你喜欢