0 前言: STL，为什么你必须掌握
对于程序员来说，数据结构是必修的一门课。从查找到排序，从链表到二叉树，几乎所有的算法和原理都需要理解，理解不了也要死记硬背下来。幸运的是这些理论都已经比较成熟，算法也基本固定下来，不需要你再去花费心思去考虑其算法原理，也不用再去验证其准确性。不过，等你开始应用计算机语言来工作的时候，你会发现，面对不同的需求你需要一次又一次去用代码重复实现这些已经成熟的算法，而且会一次又一次陷入一些由于自己疏忽而产生的bug中。这时，你想找一种工具，已经帮你实现这些功能，你想怎么用就怎么用，同时不影响性能。你需要的就是STL, 标准模板库！
西方有句谚语：不要重复发明轮子！
STL几乎封装了所有的数据结构中的算法，从链表到队列，从向量到堆栈，对hash到二叉树，从搜索到排序，从增加到删除......可以说，如果你理解了STL，你会发现你已不用拘泥于算法本身，从而站在巨人的肩膀上去考虑更高级的应用。
排序是最广泛的算法之一，本文详细介绍了STL中不同排序算法的用法和区别。
1 STL提供的Sort 算法
C++之所以得到这么多人的喜欢，是因为它既具有面向对象的概念，又保持了C语言高效的特点。STL 排序算法同样需要保持高效。因此，对于不同的需求，STL提供的不同的函数，不同的函数，实现的算法又不尽相同。
1.1 所有sort算法介绍
所有的sort算法的参数都需要输入一个范围，[begin, end)。这里使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator), 也就是说可以随机访问的迭代器，如：it+n什么的。（partition 和stable_partition 除外）
如果你需要自己定义比较函数，你可以把你定义好的仿函数(functor)作为参数传入。每种算法都支持传入比较函数。以下是所有STL sort算法函数的名字列表:
| 函数名 |
功能描述 |
| sort |
对给定区间所有元素进行排序 |
| stable_sort |
对给定区间所有元素进行稳定排序 |
| partial_sort |
对给定区间所有元素部分排序 |
| partial_sort_copy |
对给定区间复制并排序 |
| nth_element |
找出给定区间的某个位置对应的元素 |
| is_sorted |
判断一个区间是否已经排好序 |
| partition |
使得符合某个条件的元素放在前面 |
| stable_partition |
相对稳定的使得符合某个条件的元素放在前面 |
其中nth_element 是最不易理解的，实际上，这个函数是用来找出第几个。例如：找出包含7个元素的数组中排在中间那个数的值，此时，我可能不关心前面，也不关心后面，我只关心排在第四位的元素值是多少。
1.2 sort 中的比较函数
当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数。
1
vector < int > vect;
2//
3sort(vect.begin(), vect.end());
4//此时相当于调用
5sort(vect.begin(), vect.end(), 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时，你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型的'<'操作赋。
1#include <iostream>
2#include <algorithm>
3#include <functional>
4#include <vector>
5using namespace std;
6
7class myclass {
8 public:
9 myclass(int a, int b):first(a), second(b){}
10 int first;
11 int second;
12 bool operator < (const myclass &m)const {
13 return first < m.first;
14 }
15};
16
17bool less_second(const myclass & m1, const myclass & m2) {
18 return m1.second < m2.second;
19}
20
21int main() {
22
23 vector< myclass > vect;
24 for(int i = 0 ; i < 10 ; i ++){
25 myclass my(10-i, i*3);
26 vect.push_back(my);
27 }
28 for(int i = 0 ; i < vect.size(); i ++)
29 cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
30 sort(vect.begin(), vect.end());
31 cout<<"after sorted by first:"<<endl;
32 for(int i = 0 ; i < vect.size(); i ++)
33 cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
34 cout<<"after sorted by second:"<<endl;
35 sort(vect.begin(), vect.end
知道其输出结果是什么了吧：
(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 的稳定性
你发现有sort和stable_sort，还有 partition 和stable_partition， 感到奇怪吧。其中的区别是，带有stable的函数可保证相等元素的原本相对次序在排序后保持不变。或许你会问，既然相等，你还管他相对位置呢，也分不清楚谁是谁了？这里需要弄清楚一个问题，这里的相等，是指你提供的函数表示两个元素相等，并不一定是一摸一样的元素。
例如，如果你写一个比较函数:
1bool less_len(const string &str1, const string &str2)
2{
3 return str1.length() < str2.length();
4}此时，"apple" 和 "winter" 就是相等的，如果在"apple" 出现在"winter"前面，用带stable的函数排序后，他们的次序一定不变，如果你使用的是不带"stable"的函数排序，那么排序完后，"Winter"有可能在"apple"的前面。
1.4 全排序
全排序即把所给定范围所有的元素按照大小关系顺序排列。用于全排序的函数有
1template <class RandomAccessIterator>
2void sort(RandomAccessIterator first, RandomAccessIterator last);
3
4template <class RandomAccessIterator, class StrictWeakOrdering>
5void sort(RandomAccessIterator first, RandomAccessIterator last,
6StrictWeakOrdering comp);
7
8template <class RandomAccessIterator>
9void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
10
11template <class RandomAccessIterator, class StrictWeakOrdering>
12void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
13StrictWeakOrdering comp);
在第1，3种形式中，sort 和 stable_sort都没有指定比较函数，系统会默认使用operator< 对区间[first,last)内的所有元素进行排序, 因此，如果你使用的类型义军已经重载了operator<函数，那么你可以省心了。第2, 4种形式，你可以随意指定比较函数，应用更为灵活一些。来看看实际应用：
班上有10个学生，我想知道他们的成绩排名。
1#include <iostream>
2#include <algorithm>
3#include <functional>
4#include <vector>
5#include <string>
6using namespace std;
7
8class student{
9 public:
10 student(const string &a, int b):name(a), score(b){}
11 string name;
12 int score;
13 bool operator < (const student &m)const {
14 return score< m.score;
15 }
16};
17
18int main() {
19 vector< student> vect;
20 student st1("Tom", 74);
21 vect.push_back(st1);
22 st1.name="Jimy";
23 st1.score=56;
24 vect.push_back(st1);
25 st1.name="Mary";
26 st1.score=92;
27 vect.push_back(st1);
28 st1.name="Jessy";
29 st1.score=85;
30 vect.push_back(st1);
31 st1.name="Jone";
32 st1.score=56;
33 vect.push_back(st1);
34 st1.name="Bush";
35 st1.score=52;
36 vect.push_back(st1);
37 st1.name="Winter";
38 st1.score=77;
39 vect.push_back(st1);
40 st1.name="Andyer";
41 st1.score=63;
42 vect.push_back(st1);
43 st1.name="Lily";
44 st1.score=76;
45 vect.push_back(st1);
46 st1.name="Maryia";
47 st1.score=89;
48 vect.push_back(st1);
49 cout<<"------before sort"<<endl;
50 for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
51 stable_sort(vect.begin(), vect.end(),less<student>());
52 cout <<"-----after sort ."<<endl;
53 for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
54 return 0 ;
55}