//By skywind

STL中有多種排序算法，各有各的適用范圍，下面聽(tīng)我一一道來(lái)：

I、完全排序

1. sort()

首先要隆重推出的當(dāng)然是最最常用的sort了，sort有兩種形式，第一種形式有兩個(gè)迭代器參數(shù)，構(gòu)成一個(gè)前開(kāi)后閉的區(qū)間，按照元素的 less 關(guān)系排序；第二種形式多加一個(gè)指定排序準(zhǔn)則的謂詞。sort基本是最通用的排序函數(shù)，它使用快速排序算法，并且在遞歸過(guò)程中，當(dāng)元素?cái)?shù)目小于一個(gè)閾值（一般是16，我的試驗(yàn)是24）時(shí)，轉(zhuǎn)成直接插入排序。偉大的數(shù)學(xué)家Knuth已經(jīng)證明，在平均意義上，快速排序是最快的了；當(dāng)然，最壞復(fù)雜性比較差。sort要求隨機(jī)迭代器，因此對(duì)于很多編譯器來(lái)說(shuō)，對(duì)于前向迭代器（如list）使用sort是一個(gè)編譯錯(cuò)誤。(不過(guò)，在vc2005里面，這個(gè)錯(cuò)誤信息實(shí)在很糟糕)

sort的基本使用方式如下：

PLAIN TEXT

C++:

1. #include <vector>
2. #include <algorithm>
3. #include <functional>
4. #include <cstdlib>
5.  
6. using namespace std;
7.  
8. void func1()
9. {
10.     vector<int> ar;
11.     //向數(shù)組里面插入一些隨機(jī)數(shù)
12.     generate_n(back_inserter(ar), 100, rand);
13.     //按從小到大排序
14.     sort(ar.begin(), ar.end());
15. }

經(jīng)常有人問(wèn)如何從大到小逆排序，這個(gè)其實(shí)有很多種方式實(shí)現(xiàn)，如下面的例子：

PLAIN TEXT

C++:

16. void func2()
17. {
18.     vector<int> ar;
19.     //向數(shù)組里面插入一些隨機(jī)數(shù)
20.     generate_n(back_inserter(ar), 100, rand);
21.  
22.     //方法1：使用函數(shù)作為謂詞
23.     sort(ar.begin(), ar.end(), GreateThan);
24.     //方法2：使用仿函數(shù)作為謂詞
25.     //注意下面兩種方法都需要有個(gè)括號(hào)，實(shí)際上是要產(chǎn)生一個(gè)臨時(shí)對(duì)象
26.     sort(ar.begin(), ar.end(), CompareInt());
27.     //方法3：使用預(yù)定義的Adapter, 定義在 <functional> 中
28.     sort(ar.begin(), ar.end(), greater<int>());
29.     //方法4：正常排序，然后翻轉(zhuǎn)過(guò)來(lái)
30.     sort(ar.begin(), ar.end());
31.     reverse(ar.begin(), ar.end());
32.     //方法5：使用逆迭代器
33.     sort(ar.rbegin(), ar.rend());
34. }

最后一種方法是我比較欣賞的，可以不能直接對(duì)原生數(shù)組使用，也就是說(shuō)，如果ar的定義是int ar[MAXN]，上面其他的排序算法都可以簡(jiǎn)單的改成sort(ar, ar+MAXN, ...），但最后一個(gè)不行，要用另外一種比較丑陋的方式：

PLAIN TEXT

C++:

35. #include <iterator>
36. void func3(){
37.     int ax[5]={1,3,4,5,2};
38.     sort(reverse_iterator<int*>(ax+5), reverse_iterator<int*>(ax+0));
39. }
1. stable_sort

sort優(yōu)點(diǎn)一大堆，一個(gè)缺點(diǎn)就是它不是一種穩(wěn)定的排序。什么是排序的穩(wěn)定性？就是如果出現(xiàn)兩個(gè)元素相等時(shí)，要求排序之后他們之間保持原來(lái)的次序（比如我們先按學(xué)號(hào)排序，然后按成績(jī)排序，這時(shí)就希望成績(jī)相同的還是按照學(xué)號(hào)的次序排）。很可惜，快速排序算法就不是穩(wěn)定的，要追求這個(gè)，只好用stable_sort了。

在各種排序算法中，合并排序是穩(wěn)定的，但一般的合并排序需要額外的O(N)的存儲(chǔ)空間，而這個(gè)條件不是一定能夠滿足的（可能是比較奢侈的）。所以在stable_sort內(nèi)部，首先判斷是否有足夠的額外空間（如vecotr中的cap()-size()部分），有的話就使用普通合并函數(shù)，總的時(shí)間復(fù)雜性和快速排序一個(gè)數(shù)量級(jí)，都是O(N*logN)。如果沒(méi)有額外空間，使用了一個(gè)merge_without_buffer的關(guān)鍵函數(shù)進(jìn)行就地合并（如何實(shí)現(xiàn)是比較有技巧的，完全可以專(zhuān)門(mén)談一談），這個(gè)合并過(guò)程不需要額外的存儲(chǔ)空間（遞歸的堆棧除外），但時(shí)間復(fù)雜度變成O(N*logN)，這種情況下，總的stable_sort時(shí)間復(fù)雜度是O(N*logN*logN)。

總之，stable_sort稍微慢一點(diǎn)兒，但能夠保證穩(wěn)定，使用方法和sort一樣。但很多時(shí)候可以不用這種方式和這個(gè)函數(shù)，比如上面的例子，完全可以在排序比較準(zhǔn)則中寫(xiě)入成績(jī)和學(xué)號(hào)兩個(gè)條件就OK了。

PLAIN TEXT

C++:

1. class CStudent
2. {
3. public:
4.     CStudent();
5.     //注意這個(gè)比較函數(shù)中的const
6.     bool operator<(const CStudent& rhs) const
7.     {
8.         if (m_score != rhs.m_score)
9.             return (m_score <rhs.m_score);
10.         return m_name <rhs.m_name;
11.     }
12. protected:
13.     std::string m_name;
14.     int m_score;
15. };
16.  
17. void func4()
18. {
19.     vector<CStudent> arStu;
20.     sort(arStu.begin(), arStu.end());
21. }
2. sort_heap

堆排序也是一種快速的排序算法，復(fù)雜度也是O(N*logN)。STL中有一些和堆相關(guān)的函數(shù)，能夠構(gòu)造堆，如果在構(gòu)造好的堆上每次取出來(lái)根節(jié)點(diǎn)放在尾部，所有元素循環(huán)一遍，最后的結(jié)果也就有序了。這就是sort_heap了。它的使用要求區(qū)間已經(jīng)被構(gòu)造成堆，如：

PLAIN TEXT

C++:

1. void func5()
2. {
3.     vector<int> ar;
4.     //生成數(shù)據(jù)
5.     generate_n(back_inserter(ar), 100, rand);
6.     //構(gòu)造堆
7.     make_heap(ar.begin(), ar.end());
8.     //堆排序
9.     sort_heap(ar.begin(), ar.end());
10. }
3. list.sort

對(duì)于list容器，是不能直接使用sort的（包括stable_sort），從技術(shù)的角度來(lái)說(shuō)，sort要求隨機(jī)迭代器；從算法的角度來(lái)說(shuō)，list這種鏈表結(jié)構(gòu)本身就不適合用快速排序。因此，list容器內(nèi)部實(shí)現(xiàn)了專(zhuān)門(mén)的sort算法，這個(gè)算法采用的是合并排序，應(yīng)該是穩(wěn)定的（不確定）。如：

PLAIN TEXT

C++:

1. list<int> li;
2.     li.sort();
4. 其他

• 優(yōu)先隊(duì)列（priority_queue）每次彈出的都是max值。實(shí)際上就是heap的一個(gè)容器方式的包裝。
• 關(guān)聯(lián)式容器自身就必須是有序的（針對(duì)key），對(duì)其迭代時(shí)，key是遞增的。

II、部分排序

這些部分排序功能能夠完成一段數(shù)據(jù)（而不是所有）的排序，在適當(dāng)?shù)倪m合使用可以節(jié)省計(jì)算量。用的人不多，可能了解的也比較少。

1. partial_sort(), partial_sort_copy()

這兩個(gè)函數(shù)能夠?qū)⒄麄€(gè)區(qū)間中給定數(shù)目的元素進(jìn)行排序，也就是說(shuō)，結(jié)果中只有最小的M個(gè)元素是有序的。你當(dāng)然也可以使用sort，區(qū)別就在于效率。如果M顯著地小于N，時(shí)間就比較短；當(dāng)然M太小了也不好，那還不如挨個(gè)找最小值了。

partial_sort接受三個(gè)參數(shù)，分別是區(qū)間的頭，中間和結(jié)尾。執(zhí)行后，將前面M（M=中間－頭）個(gè)元素有序地放在前面，后面的元素肯定是比前面的大，但他們內(nèi)部的次序沒(méi)有保證。partial_sort_copy的區(qū)別在于把結(jié)果放到另外指定的迭代器區(qū)間中：

PLAIN TEXT

C++:

1. void func6()
2. {
3.     int ar[12]={69,23,80,42,17,15,26,51,19,12,35,8};
4.     //只排序前7個(gè)數(shù)據(jù)
5.     partial_sort(ar, ar+7, ar+12);
6.     //結(jié)果是 8 12 15 17 19 23 26 80 69 51 42 35，后5個(gè)數(shù)據(jù)次序不定，依賴(lài)于實(shí)現(xiàn)
7.     vector<int> res(7);
8.     //前7項(xiàng)排序后放入res
9.     partial_sort_copy(ar, ar+7, res.begin(), res.end(), greater<int>() );
10. }

這兩個(gè)函數(shù)的實(shí)現(xiàn)使用的是堆的方法，先將前M個(gè)元素構(gòu)造成堆，然后挨個(gè)檢查后面的元素，看看是否小于堆的最大值，是的話就彼此交換，然后重排堆；最后將前面已經(jīng)是最小的M個(gè)元素構(gòu)成的堆作一次sort_heap就可以了。算法的復(fù)雜度差不多是O(N*logM)

2. nth_element

這個(gè)函數(shù)只真正排序出一個(gè)元素來(lái)，就是第n個(gè)。函數(shù)有三個(gè)迭代器的輸入（當(dāng)然還可以加上一個(gè)謂詞），執(zhí)行完畢后，中間位置指向的元素保證和完全排序后這個(gè)位置的元素一致，前面區(qū)間的元素都小于（精確地說(shuō)，是不大于）后面區(qū)間的元素。

熟悉快速排序的馬上就能發(fā)現(xiàn)，這實(shí)際上是一個(gè)按位置劃分的算法。STL的規(guī)范中要求此函數(shù)的平均復(fù)雜度是線性的，和快速排序一樣，這種算法的最壞復(fù)雜度比較差。在一般的實(shí)現(xiàn)（如SGI）中，采用三種取1的方法尋找劃分元素，最壞復(fù)雜度是O(N^N)。雖然理論上有一些算法可以保證最壞線性復(fù)雜度，但算法過(guò)于復(fù)雜，STL一般也不采用。

III、排序輔助功能

1. partition, stable_partition
2. merge, inplace_merge

IV、有序區(qū)間操作

這個(gè)準(zhǔn)備單獨(dú)寫(xiě)一篇