西方有句諺語:不要重復發明輪子!
STL幾乎封裝了所有的數據結構中的算法,從鏈表到隊列,從向量到堆棧,對hash到二叉樹,從搜索到排序,從增加到刪除......可以說,如果你理解了STL,你會發現你已不用拘泥於算法本身,從而站在巨人的肩膀上去考慮更高級的應用。
排序是最廣泛的算法之一,本文詳細介紹了STL中不同排序算法的用法和區別。
如果你需要自己定義比較函數,你可以把你定義好的仿函數(functor)作為參數傳入。每種算法都支持傳入比較函數。以下是所有STL sort算法函數的名字列表:
vector < int > vect; //... sort(vect.begin(), vect.end()); //此時相當於調用 sort(vect.begin(), vect.end(), less<int>() );上述例子中系統自己為sort提供了less仿函數。在STL中還提供了其他仿函數,以下是仿函數列表:
less<int>() greater<int>()當你的容器中元素時一些標准類型(int float char)或者string時,你可以直接使用這些函數模板。但如果你時自己定義的類型或者你需要按照其他方式排序,你可以有兩種方法來達到效果:一種是自己寫比較函數。另一種是重載類型的'<'操作賦。
#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)
例如,如果你寫一個比較函數:
bool less_len(const string &str1, const string &str2) { return str1.length() < str2.length(); }此時,"apple" 和 "winter" 就是相等的,如果在"apple" 出現在"winter"前面,用帶stable的函數排序後,他們的次序一定不變,如果你使用的是不帶"stable"的函數排序,那麼排序完後,"Winter"有可能在"apple"的前面。
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);在第1,3種形式中,sort 和 stable_sort都沒有指定比較函數,系統會默認使用operator< 對區間[first,last)內的所有元素進行排序, 因此,如果你使用的類型義軍已經重載了Operator<函數,那麼你可以省心了。第2, 4種形式,你可以隨意指定比較函數,應用更為靈活一些。來看看實際應用:
班上有10個學生,我想知道他們的成績排名。
#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版本已經不是采用簡單的快速排序,而是結合內插排序算法)。注1,可以保證很好的平均性能、復雜度為n*log(n),由於單純的快速排序在理論上有最差的情況,性能很低,其算法復雜度為n*n,但目前大部分的STL版本都已經在這方面做了優化,因此你可以放心使用。stable_sort采用的是"歸並排序",分派足夠內存是,其算法復雜度為n*log(n), 否則其復雜度為n*log(n)*log(n),其優點是會保持相等元素之間的相對位置在排序前後保持一致。
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);理解了sort 和stable_sort後,再來理解partial_sort 就比較容易了。先看看其用途: 班上有10個學生,我想知道分數最低的5名是哪些人。如果沒有partial_sort,你就需要用sort把所有人排好序,然後再取前5個。現在你只需要對分數最低5名排序,把上面的程序做如下修改:
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這樣的好處知道了嗎?當數據量小的時候可能看不出優勢,如果是100萬學生,我想找分數最少的5個人......
partial_sort采用的堆排序(heapsort),它在任何情況下的復雜度都是n*log(n). 如果你希望用partial_sort來實現全排序,你只要讓middle=last就可以了。
partial_sort_copy其實是copy和partial_sort的組合。被排序(被復制)的數量是[first, last)和[result_first, result_last)中區間較小的那個。如果[result_first, result_last)區間大於[first, last)區間,那麼partial_sort相當於copy和sort的組合。
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);對於上述實例需求,你只需要按下面要求修改1.4中的程序:
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第四個是誰?Andyer,這個倒霉的家伙。為什麼是begin()+3而不是+4? 我開始寫這篇文章的時候也沒有在意,後來在ilovevc 的提醒下,發現了這個問題。begin()是第一個,begin()+1是第二個,... begin()+3當然就是第四個了。
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);看看應用吧:班上10個學生,計算所有沒有及格(低於60分)的學生。你只需要按照下面格式替換1.4中的程序:
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(難怪說美國總統比較笨 )都沒有及格。而且使用的是stable_partition, 元素之間的相對次序是沒有變.
這些容器的迭代器類型並不是隨機型迭代器,因此,上述的那些排序函數,對於這些容器是不可用的。上述sort函數對於下列容器是可用的:
對於list容器,list自帶一個sort成員函數list::sort(). 它和算法函數中的sort差不多,但是list::sort是基於指針的方式排序,也就是說,所有的數據移動和比較都是此用指針的方式實現,因此排序後的迭代器一直保持有效(vector中sort後的迭代器會失效).
其實不然,即使你不關心效率,如果你選擇合適的排序函數,你會讓你的代碼更容易讓人明白,你會讓你的代碼更有擴充性,逐漸養成一個良好的習慣,很重要吧 。
如果你以前有用過C語言中的qsort, 想知道qsort和他們的比較,那我告訴你,qsort和sort是一樣的,因為他們采用的都是快速排序。從效率上看,以下幾種sort算法的是一個排序,效率由高到低(耗時由小變大):