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指定比較函數，否則程序會自動提供給你一個比較函數。
 
上述例子中系統自己為sort提供了less仿函數。在STL中還提供了其他仿函數，以下是仿函數列表:

名稱	功能描述
equal_to	相等
not_equal_to	不相等
less	小于
greater	大于
less_equal	小于等于
greater_equal	大于等于

需要注意的是，這些函數不是都能適用于你的sort算法，如何選擇，決定于你的應用。另外，不能直接寫入仿函數的名字，而是要寫其重載的()函數：

less<int>()
greater<int>()

當你的容器中元素時一些標準類型（int float char)或者string時，你可以直接使用這些函數模板。但如果你時自己定義的類型或者你需要按照其他方式排序，你可以有兩種方法來達到效果：一種是自己寫比較函數。另一種是重載類型的'<'操作賦。
知道其輸出結果是什么了吧：

(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}