詳細(xì)解說 STL 排序(Sort)
詳細(xì)解說 STL 排序(Sort)
作者Winter0 前言: STL,，為什么你必須掌握
對(duì)于程序員來說，數(shù)據(jù)結(jié)構(gòu)是必修的一門課,。從查找到排序,，從鏈表到二叉樹，幾乎所有的算法和原理都需要理解,，理解不了也要死記硬背下來,。幸運(yùn)的是這些理論都已經(jīng)比較成熟，算法也基本固定下來,，不需要你再去花費(fèi)心思去考慮其算法原理,，也不用再去驗(yàn)證其準(zhǔn)確性。不過,，等你開始應(yīng)用計(jì)算機(jī)語言來工作的時(shí)候,，你會(huì)發(fā)現(xiàn),，面對(duì)不同的需求你需要一次又一次去用代碼重復(fù)實(shí)現(xiàn)這些已經(jīng)成熟的算法，而且會(huì)一次又一次陷入一些由于自己疏忽而產(chǎn)生的bug中,。這時(shí),，你想找一種工具，已經(jīng)幫你實(shí)現(xiàn)這些功能,，你想怎么用就怎么用,，同時(shí)不影響性能。你需要的就是STL, 標(biāo)準(zhǔn)模板庫,！
西方有句諺語：不要重復(fù)發(fā)明輪子,！
STL幾乎封裝了所有的數(shù)據(jù)結(jié)構(gòu)中的算法，從鏈表到隊(duì)列,，從向量到堆棧,，對(duì)hash到二叉樹，從搜索到排序,，從增加到刪除......可以說,，如果你理解了STL，你會(huì)發(fā)現(xiàn)你已不用拘泥于算法本身,，從而站在巨人的肩膀上去考慮更高級(jí)的應(yīng)用,。
排序是最廣泛的算法之一，本文詳細(xì)介紹了STL中不同排序算法的用法和區(qū)別,。
1 STL提供的Sort 算法
C++之所以得到這么多人的喜歡,，是因?yàn)樗染哂忻嫦驅(qū)ο蟮母拍睿直３至薈語言高效的特點(diǎn),。STL 排序算法同樣需要保持高效,。因此，對(duì)于不同的需求,，STL提供的不同的函數(shù),，不同的函數(shù)，實(shí)現(xiàn)的算法又不盡相同,。
1.1 所有sort算法介紹
所有的sort算法的參數(shù)都需要輸入一個(gè)范圍,，[begin, end)。這里使用的迭代器(iterator)都需是隨機(jī)迭代器(RadomAccessIterator), 也就是說可以隨機(jī)訪問的迭代器,，如：it+n什么的,。（partition 和stable_partition 除外）如果你需要自己定義比較函數(shù)，你可以把你定義好的仿函數(shù)(functor)作為參數(shù)傳入,。每種算法都支持傳入比較函數(shù),。以下是所有STL sort算法函數(shù)的名字列表:
| 函數(shù)名 | 功能描述 |
|---|---|
| sort | 對(duì)給定區(qū)間所有元素進(jìn)行排序 |
| stable_sort | 對(duì)給定區(qū)間所有元素進(jìn)行穩(wěn)定排序 |
| partial_sort | 對(duì)給定區(qū)間所有元素部分排序 |
| partial_sort_copy | 對(duì)給定區(qū)間復(fù)制并排序 |
| nth_element | 找出給定區(qū)間的某個(gè)位置對(duì)應(yīng)的元素 |
| is_sorted | 判斷一個(gè)區(qū)間是否已經(jīng)排好序 |
| partition | 使得符合某個(gè)條件的元素放在前面 |
| stable_partition | 相對(duì)穩(wěn)定的使得符合某個(gè)條件的元素放在前面 |
1.2 sort 中的比較函數(shù)
當(dāng)你需要按照某種特定方式進(jìn)行排序時(shí)，你需要給sort指定比較函數(shù),，否則程序會(huì)自動(dòng)提供給你一個(gè)比較函數(shù)。vector < int > vect; //... sort(vect.begin(), vect.end()); //此時(shí)相當(dāng)于調(diào)用 sort(vect.begin(), vect.end(), less<int>() );
| 名稱 | 功能描述 |
|---|---|
| equal_to | 相等 |
| not_equal_to | 不相等 |
| less | 小于 |
| greater | 大于 |
| less_equal | 小于等于 |
| greater_equal | 大于等于 |
less<int>() greater<int>()當(dāng)你的容器中元素時(shí)一些標(biāo)準(zhǔn)類型（int float char)或者string時(shí),，你可以直接使用這些函數(shù)模板。但如果你時(shí)自己定義的類型或者你需要按照其他方式排序,，你可以有兩種方法來達(dá)到效果：一種是自己寫比較函數(shù),。另一種是重載類型的'<'操作賦。
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
class myclass {
public:
myclass(int a, int b):first(a), second(b){}
int first;
int second;
bool 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 = 0 ; i < vect.size(); i ++)
cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
sort(vect.begin(), vect.end());
cout<<"after sorted by first:"<<endl;
for(int i = 0 ; i < vect.size(); i ++)
cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
cout<<"after sorted by second:"<<endl;
sort(vect.begin(), vect.end(), less_second);
for(int i = 0 ; i < vect.size(); i ++)
cout<<"("<<vect[i].first<<","<<vect[i].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 的穩(wěn)定性
你發(fā)現(xiàn)有sort和stable_sort,，還有 partition 和stable_partition,， 感到奇怪吧。其中的區(qū)別是,，帶有stable的函數(shù)可保證相等元素的原本相對(duì)次序在排序后保持不變,。或許你會(huì)問,，既然相等,，你還管他相對(duì)位置呢，也分不清楚誰是誰了,？這里需要弄清楚一個(gè)問題,，這里的相等，是指你提供的函數(shù)表示兩個(gè)元素相等,，并不一定是一摸一樣的元素,。例如，如果你寫一個(gè)比較函數(shù):
bool less_len(const string &str1, const string &str2)
{
return str1.length() < str2.length();
}
1.4 全排序
全排序即把所給定范圍所有的元素按照大小關(guān)系順序排列,。用于全排序的函數(shù)有
template <class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class StrictWeakOrdering> void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp); template <class RandomAccessIterator> void stable_sort(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class StrictWeakOrdering> void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
班上有10個(gè)學(xué)生，我想知道他們的成績排名,。
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
using namespace std;
class student{
public:
student(const string &a, int b):name(a), score(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);
st1.name="Jimy";
st1.score=56;
vect.push_back(st1);
st1.name="Mary";
st1.score=92;
vect.push_back(st1);
st1.name="Jessy";
st1.score=85;
vect.push_back(st1);
st1.name="Jone";
st1.score=56;
vect.push_back(st1);
st1.name="Bush";
st1.score=52;
vect.push_back(st1);
st1.name="Winter";
st1.score=77;
vect.push_back(st1);
st1.name="Andyer";
st1.score=63;
vect.push_back(st1);
st1.name="Lily";
st1.score=76;
vect.push_back(st1);
st1.name="Maryia";
st1.score=89;
vect.push_back(st1);
cout<<"------before sort..."<<endl;
for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
stable_sort(vect.begin(), vect.end(),less<student>());
cout <<"-----after sort ...."<<endl;
for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
return 0 ;
}------before sort... Tom: 74 Jimy: 56 Mary: 92 Jessy: 85 Jone: 56 Bush: 52 Winter: 77 Andyer: 63 Lily: 76 Maryia: 89 -----after sort .... Bush: 52 Jimy: 56 Jone: 56 Andyer: 63 Tom: 74 Lily: 76 Winter: 77 Jessy: 85 Maryia: 89 Mary: 92sort采用的是成熟的"快速排序算法"(目前大部分STL版本已經(jīng)不是采用簡單的快速排序,，而是結(jié)合內(nèi)插排序算法)。注1,，可以保證很好的平均性能,、復(fù)雜度為n*log(n)，由于單純的快速排序在理論上有最差的情況,，性能很低,，其算法復(fù)雜度為n*n，但目前大部分的STL版本都已經(jīng)在這方面做了優(yōu)化,，因此你可以放心使用,。stable_sort采用的是"歸并排序"，分派足夠內(nèi)存是,，其算法復(fù)雜度為n*log(n), 否則其復(fù)雜度為n*log(n)*log(n),，其優(yōu)點(diǎn)是會(huì)保持相等元素之間的相對(duì)位置在排序前后保持一致。
1.5 局部排序
局部排序其實(shí)是為了減少不必要的操作而提供的排序方式,。其函數(shù)原型為：template <class RandomAccessIterator> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template <class RandomAccessIterator, class StrictWeakOrdering> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering comp); template <class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(InputIterator 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 result_first, RandomAccessIterator result_last, Compare comp);
stable_sort(vect.begin(), vect.end(),less<student>()); 替換為： partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());
------before sort... Tom: 74 Jimy: 56 Mary: 92 Jessy: 85 Jone: 56 Bush: 52 Winter: 77 Andyer: 63 Lily: 76 Maryia: 89 -----after sort .... Bush: 52 Jimy: 56 Jone: 56 Andyer: 63 Tom: 74 Mary: 92 Jessy: 85 Winter: 77 Lily: 76 Maryia: 89這樣的好處知道了嗎？當(dāng)數(shù)據(jù)量小的時(shí)候可能看不出優(yōu)勢,，如果是100萬學(xué)生,，我想找分?jǐn)?shù)最少的5個(gè)人......
partial_sort采用的堆排序（heapsort），它在任何情況下的復(fù)雜度都是n*log(n). 如果你希望用partial_sort來實(shí)現(xiàn)全排序,，你只要讓middle=last就可以了,。
partial_sort_copy其實(shí)是copy和partial_sort的組合。被排序(被復(fù)制)的數(shù)量是[first, last)和[result_first, result_last)中區(qū)間較小的那個(gè),。如果[result_first, result_last)區(qū)間大于[first, last)區(qū)間,，那么partial_sort相當(dāng)于copy和sort的組合。
1.6 nth_element 指定元素排序
nth_element一個(gè)容易看懂但解釋比較麻煩的排序,。用例子說會(huì)更方便：班上有10個(gè)學(xué)生,，我想知道分?jǐn)?shù)排在倒數(shù)第4名的學(xué)生。
如果要滿足上述需求,，可以用sort排好序,，然后取第4位（因?yàn)槭怯尚〉酱笈?, 更聰明的朋友會(huì)用partial_sort, 只排前4位,，然后得到第4位,。其實(shí)這是你還是浪費(fèi)，因?yàn)榍皟晌荒愀緵]有必要排序,，此時(shí),，你就需要nth_element:
template <class RandomAccessIterator> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template <class RandomAccessIterator, class StrictWeakOrdering> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering comp);
stable_sort(vect.begin(), vect.end(),less<student>()); 替換為： nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());
------before sort... Tom: 74 Jimy: 56 Mary: 92 Jessy: 85 Jone: 56 Bush: 52 Winter: 77 Andyer: 63 Lily: 76 Maryia: 89 -----after sort .... Jone: 56 Bush: 52 Jimy: 56 Andyer: 63 Jessy: 85 Mary: 92 Winter: 77 Tom: 74 Lily: 76 Maryia: 89第四個(gè)是誰,？Andyer,，這個(gè)倒霉的家伙。為什么是begin()+3而不是+4? 我開始寫這篇文章的時(shí)候也沒有在意,，后來在ilovevc 的提醒下,，發(fā)現(xiàn)了這個(gè)問題。begin()是第一個(gè),，begin()+1是第二個(gè),，... begin()+3當(dāng)然就是第四個(gè)了。
1.7 partition 和stable_partition
好像這兩個(gè)函數(shù)并不是用來排序的,，'分類'算法,，會(huì)更加貼切一些。partition就是把一個(gè)區(qū)間中的元素按照某個(gè)條件分成兩類,。其函數(shù)原型為：template <class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred) template <class ForwardIterator, class Predicate> ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
stable_sort(vect.begin(), vect.end(),less<student>());
替換為：
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));------before sort... Tom: 74 Jimy: 56 Mary: 92 Jessy: 85 Jone: 56 Bush: 52 Winter: 77 Andyer: 63 Lily: 76 Maryia: 89 -----after sort .... Jimy: 56 Jone: 56 Bush: 52 Tom: 74 Mary: 92 Jessy: 85 Winter: 77 Andyer: 63 Lily: 76 Maryia: 89看見了嗎,，Jimy,，Jone, Bush(難怪說美國總統(tǒng)比較笨
)都沒有及格,。而且使用的是stable_partition, 元素之間的相對(duì)次序是沒有變.
2 Sort 和容器
STL中標(biāo)準(zhǔn)容器主要vector, list, deque, string, set, multiset, map, multimay， 其中set, multiset, map, multimap都是以樹結(jié)構(gòu)的方式存儲(chǔ)其元素詳細(xì)內(nèi)容請(qǐng)參看：學(xué)習(xí)STL map, STL set之?dāng)?shù)據(jù)結(jié)構(gòu)基礎(chǔ). 因此在這些容器中,，元素一直是有序的,。
這些容器的迭代器類型并不是隨機(jī)型迭代器，因此,，上述的那些排序函數(shù),，對(duì)于這些容器是不可用的。上述sort函數(shù)對(duì)于下列容器是可用的：
- vector
- string
- deque
對(duì)于list容器，list自帶一個(gè)sort成員函數(shù)list::sort(). 它和算法函數(shù)中的sort差不多,，但是list::sort是基于指針的方式排序,，也就是說，所有的數(shù)據(jù)移動(dòng)和比較都是此用指針的方式實(shí)現(xiàn),，因此排序后的迭代器一直保持有效（vector中sort后的迭代器會(huì)失效).
3 選擇合適的排序函數(shù)
為什么要選擇合適的排序函數(shù),？可能你并不關(guān)心效率(這里的效率指的是程序運(yùn)行時(shí)間), 或者說你的數(shù)據(jù)量很小， 因此你覺得隨便用哪個(gè)函數(shù)都無關(guān)緊要,。
其實(shí)不然,，即使你不關(guān)心效率，如果你選擇合適的排序函數(shù),，你會(huì)讓你的代碼更容易讓人明白,，你會(huì)讓你的代碼更有擴(kuò)充性，逐漸養(yǎng)成一個(gè)良好的習(xí)慣,，很重要吧 ,。
如果你以前有用過C語言中的qsort, 想知道qsort和他們的比較，那我告訴你,，qsort和sort是一樣的,，因?yàn)樗麄儾捎玫亩际强焖倥判颉男噬峡?，以下幾種sort算法的是一個(gè)排序,，效率由高到低（耗時(shí)由小變大）：
- partion
- stable_partition
- nth_element
- partial_sort
- sort
- stable_sort
- 若需對(duì)vector, string, deque, 或 array容器進(jìn)行全排序,，你可選擇sort或stable_sort；
- 若只需對(duì)vector, string, deque, 或 array容器中取得top n的元素,，部分排序partial_sort是首選.
- 若對(duì)于vector, string, deque, 或array容器,，你需要找到第n個(gè)位置的元素或者你需要得到top n且不關(guān)系top n中的內(nèi)部順序，nth_element是最理想的；
- 若你需要從標(biāo)準(zhǔn)序列容器或者array中把滿足某個(gè)條件或者不滿足某個(gè)條件的元素分開,，你最好使用partition或stable_partition,；
- 若使用的list容器，你可以直接使用partition和stable_partition算法,，你可以使用list::sort代替sort和stable_sort排序,。若你需要得到partial_sort或nth_element的排序效果，你必須間接使用,。正如上面介紹的有幾種方式可以選擇,。
4 小結(jié)
討論技術(shù)就像個(gè)無底洞,，經(jīng)常容易由一點(diǎn)可以引申另外無數(shù)個(gè)技術(shù)點(diǎn),。因此需要從全局的角度來觀察問題，就像觀察STL中的sort算法一樣,。其實(shí)在STL還有make_heap, sort_heap等排序算法,。本文章沒有提到。本文以實(shí)例的方式,，解釋了STL中排序算法的特性,，并總結(jié)了在實(shí)際情況下應(yīng)如何選擇合適的算法。
5 參考文檔
條款31：如何選擇排序函數(shù)The Standard Librarian: Sorting in the Standard Library
Effective STL中文版
Standard Template Library Programmer's Guide vvvv
