详细解说STL排序Sort

1、,详细解说STL排序(Sort)o 0前言：STL ,为什么你必须掌握o 1 STL提供的Sort算法1.1 所有sort算法介绍1.2 sort 中的比较函数1.3 sort 的稳定性1.4全排序1.5 局部排序1.6 nth_element 指定元素排序1.7 partition 和 stable partitiono 2 Sort 和容器o 3选择合适的排序函数o 4小结o 5参考文档一切复杂的排序操作，都可以通过 STL方便实现！0前言:STL ,为什么你必须掌握对丁程序员来说，数据结构是必修的一门课。从查找到排序，从链表到二义树，几乎所有的算法和原理都需要理解，理解不了也要死记硬背下

2、来。幸运的是这些 理论都已经比较成熟，算法也基本固定下来，不需要你再去花费心思去考虑其算 法原理，也不用再去验证其准确性。不过，等你开始应用计算机语言来工作的时 候，你会发现，面对不同的需求你需要一次乂一次去用代码重复实现这些已经成 熟的算法，而且会一次乂一次陷入一些由丁自己疏忽而产生的bug中。这时，你想找一种工具，已经帮你实现这些功能，你想怎么用就怎么用，同时不影响性能。 你需要的就是STL,标准模板库！西方有句谚语：不要重复发明轮子！STL几乎封装了所有的数据结构中的算法，从链表到队列，从向量到堆栈，对hash 到二义树，从搜索到排序，从增加到删除. 可以说，如果你理解了 STL,你 会

3、发现你已不用拘泥丁算法本身，从而站在巨人的肩膀上去考虑更高级的应用。排序是最广泛的算法之一，本文详细介绍了STL中不同排序算法的用法和区别。1 STL提供的Sort算法C+之所以得到这么多人的喜欢，是因为它既具有面向对象的概念，乂保持了 C 语言高效的特点。STL排序算法同样需要保持高效。因此，对丁不同的需求，STL 提供的不同的函数，不同的函数，实现的算法乂不尽相同。1.1所有sort算法介绍所有的sort算法的参数都需要输入一个范围，begin, end)。这里使用的迭代 器(iterator) 都需是随机迭代器(RadomAccessIterator), 也就是说可以随机访 问的迭代器，

4、如：it+n什么的。(partition 和stable_partition 除外)如果你需要自己定义比较函数，你可以把你定义好的仿函数 (functor)作为参数 传入。每种算法都支持传入比较函数。以下是所有 STL sort算法函数的名字列 表：函数名功能描述sort对给正区间所有兀系进仃排序stable_sort对给定区间所有元素进行稳定排序partial_sort对给定区间所有元素部分排序partial_sort_copy对给定区间复制并排序nth_element找出给定区间的某个位置对应的元素is_sorted判断一个区间是否已经排好序partition使得符合某个条件的元素放在前面

5、stable_partition相对稳定的使得符合某个条件的元素放在前面其中nth_element是最不易理解的，实际上，这个函数是用来找出第几个。例 如：找出&含7个元素的数组中排在中间那个数的值，此时，我可能不关心前面,也不关心后面，我只关心排在第四位的兀素值是多少。1.2 sort中的比较函数当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数。vector < int > vect;/.sort(vect.begin(), vect.end();/此时相当丁调用sort(vect.begin(), vect.end()

6、, less<int >();上述例子中系统自己为sort提供了 less仿函数。在STL中还提供了其他仿函数, 以下是仿函数列表：名称功能描述equal_to相等not_equal_to不相等less小丁greater大丁less_equal小于等于greater_equal大丁等丁需要注意的是，这些函数不是都能适用于你的sort算法，如何选择，决定于你的应用。另外，不能直接写入仿函数的名字，而是要写其重载的()函数：less<int>() greater<int>()当你的容器中元素时一些标准类型(int float char)或者string时，你可以

7、直 接使用这些函数棋板。但如果你时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型 的'<'操作赋。#include <iostream>#include <algorithm>#include <functional>#include <vector> using namespacestd;class myclass public :myclass( int a, int b):first(a), second(b) int first; int second;b

8、ool operator < ( const myclass &m) const return first < m.first;bool less_second( const myclass & m1, const myclass & m2) return m1.second < m2.second;int main() vector< myclass > vect;for (int i = 0 ; i < 10 ; i +) myclass my(10-i, i*3); vect.push_back(my);for ( int i

9、= 0 ; i < vect.size(); i +)cout<<" ( "<<vecti.first<<" , "<<vecti.second<<" )n " sort(vect.begin(), vect.end();cout<<" after sorted by first:"<<endl;for ( int i = 0 ; i < vect.size(); i +)cout<<" ( &qu

10、ot;<<vecti.first<<" , "<<vecti.second<<" )n "cout<<" after sorted by second: "<<endl;sort(vect.begin(), vect.end(), less_second);for ( int i = 0 ; i < vect.size(); i +)cout<<" ("<<vecti.first<<" , &

11、quot;<<vecti.second<<" )n "return 0 ;知道其输出结果是什么了吧：(10,0)(9,3)(8,6)(7,9)(6,12)(5,15)(4,18)(3,21)(2,24)(1,27)after sorted by first:(1,27)(2,24)(3,21)(4,18)(5,15)(6,12)(7,9)(8,6)(9,3)(10,0)after sorted by second:(10,0)(9,3)(8,6)(7,9)(6,12)(5,15)(4,18)(3,21)(2,24)(1,27)1.3 sort 的稳定

12、性你发现有 sort 和 stable_sort ，还有 partition 和 stable_partition ,感至U奇怪吧。其中的区别是，带有 stable的函数可保证相等元豪的原本相对次序在 排序后保持不变。或许你会问，既然相等，你还管他相对位置呢，也分不活楚谁 是谁了？这里需要弄活楚一个问题，这里的相等，是指你提供的函数表示两个元 素相等，并不一定是一摸一样的元素。例如，如果你写一个比较函数：bool less_len( const string &str1, const string &str2)return str1.length() < str2.len

13、gth();此时，"apple" 和"winter" 就是相等的，如果在"apple" 出现在"winter"前面, 用带stable的函数排序后，他们的次序一定不变，如果你使用的是不带"stable" 的函数排序，那么排序完后，"Winter"有可能在"apple"的前面。1.4全排序全排序即把所给定范围所有的元素按照大小关系顺序排列。用于全排序的函数有template < class RandomAccessIterator>void so

14、rt(RandomAccessIterator first, RandomAccessIterator last);template < class RandomAccessIterator, class StrictWeakOrdering>void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);template < class RandomAccessIterator>void stable_sort(RandomAccessIterator

15、first, RandomAccessIterator last);template < class RandomAccessIterator, class StrictWeakOrdering> void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);在第1, 3种形式中,sort和stable_sort都没有指定比较函数，系统会默认使用operator<对区间first,last)内的所有元素进行排序，因此，如果你使用的类型义军已经重载

16、了 operator<函数，那么你可以省心了。第 2, 4种形式, 你可以随意指定比较函数，应用更为灵活一些。来看看实际应用：班上有10个学生，我想知道他们的成绩排名。#include <iostream>#include <algorithm>#include <functional>#include <vector>#include <string> using namespacestd;class student(public :student( const string &a, int b):name(a), s

17、core(b)( string name;int score;bool operator < ( const student &m) const ( return score< m.score;int main() (vector< student> vect;student st1(" Tom, 74);vect.push_back(st1);=" Jimy"st1.score=56;vect.push_back(st1);=" Mary"st1.score=92;vect.pu

18、sh_back(st1);=" Jessy"st1.score=85;vect.push_back(st1);=" Jone"st1.score=56;vect.push_back(st1);=" Bush"st1.score=52;vect.push_back(st1);=" Winter"st1.score=77;vect.push_back(st1);=" Andyer"st1.score=63;vect.pu

19、sh_back(st1);=" Lily "st1.score=76;vect.push_back(st1);=" Maryia"st1.score=89;vect.push_back(st1);cout<<" before sort. "<<endl;for (int i = 0 ; i < vect.size(); i +)cout<<<<" :t "<<vecti.score<<e

20、ndl;stable_sort(vect.begin(), vect.end(),less<student>();cout <<"after sort . "<<endl;for (int i = 0 ; i < vect.size(); i +)cout<<<<" :t "<<vecti.score<<endl;return 0 ;其输出是：before sort.Tom: 74Jimy: 56Mary: 92Jessy: 85Jone: 56

21、Bush: 52Winter: 77Andyer: 63Lily: 76Maryia: 89after sort .Bush: 52Jimy: 56Jone: 56Andyer: 63Tom: 74Lily: 76Winter: 77Jessy: 85Maryia: 89Mary: 92sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的 快速排序，而是结合内插排序算法)。面，可以保证很好的平均性能、复杂度 为n*log(n),由丁单纯的快速排序在理论上有最差的情况，性能很低，其算法 复杂度为n*n,但目前大部分的STL版本都已经在这方面做了优化，

22、因此你可以 放心使用。stable_sort采用的是”归并排序”，分派足够内存是，其算法复杂度 为n*log(n),否则其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。1.5局部排序局部排序其实是为了减少不必要的操作而提供的排序方式。其函数原型为：template < class RandomAccessIterator>void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);templ

23、ate < class RandomAccessIterator, class StrictWeakOrdering> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering comp);template < class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(In

24、putIterator first, InputIterator last,RandomAccessIterator result_first, RandomAccessIterator result_last);template < class InputIterator, class RandomAccessIterator,class StrictWeakOrdering>RandomAccessIterator partial_sort_copy(InputIterator first,InputIterator last,RandomAccessIterator resu

25、lt_first, RandomAccessIterator result_last, Compare comp);理解了 sort和stable_sort 后，再来理解partial_sort就比较容易了。先看看其用途：班上有10个学生，我想知道分数最低的5名是哪些人。如果没有 partial_sort ，你就需要用sort把所有人排好序，然后再取前5个。现在你只需要对分数最低5名排序，把上面的程序做如下修改：stable_sort(vect.begin(), vect.end(),less<student>();替换赤:partial_sort(vect.begin(), ve

26、ct.begin()+5,vect.end(),less<student>();输出结果为：before sort.Tom: 74Jimy: 56Mary: 92Jessy: 85Jone: 56Bush: 52Winter: 77Andyer: 63Lily: 76Maryia: 89after sort .Bush: 52Jimy: 56Jone: 56Andyer: 63Tom: 74Mary: 92Jessy: 85Winter: 77Lily: 76Maryia: 89这样的好处知道了吗？当数据量小的时候可能看不出优势，如果是 100万学生,我想找分数最少的5个人part

27、ial_sort 采用的堆排序(heapsort ),它在任何情况下的复杂度都是 n*log(n).如果你希望用partial_sort来实现全排序，你只要让middle=last就可以了。的组合。被排序(被复制)的数中区间较小的那个。如果last)区间，那么 partial_sortpartial_sort_copy 其实是 copy 木日 partial_sort 量是first, last) 和result_first, result_last) result_first, result_last) 区间大于first, 相当于copy和sort的组合。1.6 nth_element 指

28、定元素排序nth_element 一个容易看懂但解释比较麻烦的排序。用例子说会更方便：班C有10个学生，我想知道分数排在倒数第 4名的学生。如果要满足上述需求，可以用sort排好序，然后取第4位(因为是由小到大排), 更聪明的朋友会用partial_sort, 只排前4位，然后得到第4位。其实这是你 还是浪费，因为前两位你根本没有必要排序，此时，你就需要 nth_element:template < class RandomAccessIterator>void nth_element(RandomAccessIterator first, RandomAccessIterator

29、 nth, RandomAccessIterator last);class first,StrictWeakOrdering>RandomAccessIterator nth,template < class RandomAccessIterator, void nth_element(RandomAccessIterator RandomAccessIterator last, StrictWeakOrdering comp);对于上述实例需求，你只需要按下面要求修改1.4中的程序：stable_sort(vect.begin(), vect.end(),less<stu

30、dent>();替换为：nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>();运行结果为：before sort.Tom: 74Jimy: 56Mary: 92Jessy: 85Jone: 56Bush: 52Winter: 77Andyer: 63Lily: 76Maryia: 89after sort .Jone: 56Bush: 52Jimy: 56Andyer: 63Jessy: 85Mary: 92Winter: 77Tom: 74Lily: 76Maryia: 89第四个是谁？ A

31、ndyer,这个倒霉的家伙。为什么是begin()+3而不是+4?我开始写这篇文章的时候也没有在意，后来在 ilovevc的提醒下，发现了这个问题。begin()是第一个，begin()+1是第二个，. begin()+3当然就是第四个了。1.7 partition 和 stable_partition好像这两个函数并不是用来排序的，分类算法，会更加贴切一些。partition就是把一个区间中的元素按照某个条件分成两类。其函数原型为：template < class ForwardIterator, class PredicateForwardIterator partition(For

32、wardIterator first,Forwarditerator last, Predicate pred)template < class Forwarditerator, class Predicate>Forwarditerator stable_partition(Forwarditerator first,Forwarditerator last,Predicate pred);看看应用吧：班上10个学生，计算所有没有及格(低丁 60分)的学生。你只需要按照下面格式替换1.4中的程序：stable_sort(vect.begin(), vect.end(),less&

33、lt;student>();替换侦student exam(" pass", 60);stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam);其输出结果为：before sort.Tom: 74Jimy: 56Mary: 92Jessy: 85Jone: 56Bush: 52Winter: 77Andyer: 63Lily: 76Maryia: 89after sort .Jimy: 56Jone: 56Bush: 52Tom: 74Mary: 92Jessy: 8

34、5Winter: 77Andyer: 63Lily: 76Maryia: 89看见了吗，Jimy, Jone, Bush（难怪说美国总统比较笨）都没有及格。而且使用的是stable_partition,元素之间的相对次序是没有变.2 Sort 和容器STL中标准容器主要 vector, list, deque, string, set, multiset, map, multimay , 其中set, multiset, map, multimap都是以树结构的方式存储其元 素详细内容请参看： 学习STL map, STL set之数据结构基础.因此在这些容器 中，元素一直是有序的。这些容器的迭代器类型并不是随机型迭代器，因此，上述的那些排序函数，对丁这些容器是不可用的。上述sort函数对丁下列容器是可用的： vector string deque如果你自己定义的容器也支持随机型迭代器，那么使用排序算法是没有任何问题的。对丁 list容器,list自带一个sort成员函数list:so