学习网站:http://www.stlchina.org/twiki/bin/view.pl/Main/STLTechArticles
http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms
排序(sort):所有sort算法介绍:使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator)
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时,你可以直接使用这些函数模板。但如果你
时自己定义的类型或者你需要按照其他方式排序,你可以有两种方法来达到效果:一种是自己写比较函数。另一种是重载类型的'<'操作赋。如:
bool less_second(const myclass & m1, const myclass & m2) {
return m1.second < m2.second;
}
3. 全排序:全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排序算法)。复杂度为n*log(n).stable_sort采用的是"归并排序",分派足够内存是,其算法复杂度为n*log(n), 否则其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。
用于全排序的函数有:
void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
4. 局部排序:partial_sort采用的堆排序(heapsort),它在任何情况下的复杂度都是n*log(n).
局部排序其实是为了减少不必要的操作而提供的排序方式。
其函数原型为:
1) void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);
2) void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,
RandomAccessIterator last, StrictWeakOrdering comp);
3) RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,RandomAccessIterator result_last);
4) RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,RandomAccessIterator result_last, Compare comp);
用法使用情况:班上有1000个学生,我想知道分数最低的5名是哪些人。
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());
5. nth_element 指定元素排序
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
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就是把一个区间中的元素按照某个条件分成两类,并没有排序。
其函数原型为:
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)
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对如何选择排序函数总结的很好:
1) 若需对vector, string, deque, 或 array容器进行全排序,你可选择sort或stable_sort;
若只需对vector, string, deque, 或 array容器中取得top n的元素,部分排序partial_sort是首选.
若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top
2) n中的内部顺序,nth_element是最理想的;
3) 若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开,你最好使用partition或stable_partition;
4) 若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。
分享到:
相关推荐
使用c++实现常见的排序算法,包括冒泡排序,快速排序,直接插入排序,带有完整注释
自己实现的各种排序算法,多多指教,包括归并、插入、冒泡 、希尔、快速、桶排序。
算法导论排序算法C++实现。被算法导论优美的叙述折服,用C++实现一下加深理解
通过几天学习终于将标准库中排序相关的函数学完了,虽然有些问题没有搞得非常透彻,但是这些算法用起来应该是没问题了!
排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际...
经过3天努力,在容器学完后又解决了非变异算法的战斗,感觉收获挺多,拿出来与大家分享,记下来还有变异算法、排序算法和数值算法的总结都会相继分享!
通过几天学习终于将标准库中排序相关的函数学完了,虽然有些问题没有搞得非常透彻,但是这些算法用起来应该是没问题了!
推荐的刷题顺序:二叉树—>线性表—>排序算法—>死磕二叉树—>动态规划—>滑动窗口—>回溯法—>其他类型(顺序随意)。一定要先刷二叉树,先刷二叉树,先刷二叉树,重要的事情说三遍。。。 (说一下本人的复习情况
算法模板 本库是对原有库的C++实现, 如有问题请;...排序算法 动态规划 算法思维 :lion: 递归思维 滑动窗口思想 二叉搜索树 回溯法 刷题路径 1、 algorithm-pattern 练习题 2、 LeetCode 卡片 3、 剑指 offer
代数算法:霍纳法则计算多项式和、矩阵乘法(2种)、方阵的LUP分解、解线性方程组(2种)、矩阵求逆(2种)、求伪逆矩阵(2种)、解正态方程组(2种)、最小二乘估计(2种)、多元最小二乘估计*、快速傅里叶变换、...
Bubble-Sort-Algorithm-Visualizer(Windows / Linux) 用纯C ++制作的冒泡排序算法可视化程序。笔记: 列表数组和#define值是唯一可编辑的变量。 向上增加LENGTH和WIDTH的值以获得更清晰的输出。 非商业用途
排序算法 Recursion_alg 递归算法 Tree_alg 树算法 LinkedList_alg 链表算法 Graph_alg 图算法 Greedy_alg 贪心算法 BFS/DFS_alg 广/深度算法 Everyday_alg 每日算法 HOT100 leetcode-100热题 UPDATE LOG 2020-12-15...
algorithm头文件是C++的标准算法库,它主要应用在容器上。 因为所有的算法都是通过迭代器进行操作的,所以算法的运算实际上是和具体的数据结构相分离的 ,也就是说,具有低耦合性。 因此,任何数据结构都能使用这套...
SortAlgorithm.h 代码如下:#include <vector>using namespace std; class SortAlgorithm{public: SortAlgorithm(int = 10); void displayVector(); void swap(int &, int &); void insertSort(); //O(n^2) ...
Algorithm-With-C使用环境Ubuntu18.04 LTSg++ 7.3.0CMake 3.10.2Vim 8.0.1453C++11常用算法总结选择排序、快速排序、希尔排序和堆排序是不稳定的排序算法冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法...
组合数学排序C++算法
算法由模板函数体现,这些函数不是容器类的成员函数,是独立的函数,它们可以用于STL容器,也可以用于普通的C++数组等. 头文件:#include<algorithm> 在STL的泛型算法中有4类基本的算法: 1)变序型队列算法: 可以改变...
主要是一些排序分类算法,学会应用这些算法进行排序很管用。
算法设计与分析课后程序实现会场安排。 // 会场安排问题 // #include #include <algorithm> #include using namespace std; int greedy(int n,int *a,int *b) //贪心选择 { int sum=0,curr=0,i,j,k; int *x; x...
1.C++语言兼容C语言。...9.在数组的泛型算法中,要输出数组的内容、对数组进行升幂排序、反转数组的内容、复制数组的内容等操作,需要包含头文件<algorithm>;要对数组进行降幂排序和检索,需要包含头文件。