1. 所有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è)條件的元素放在前面

2. 比較函數(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>() );

sort 中的其他比較函數(shù)

equal_to 相等

not_equal_to 不相等

less 小于

greater 大于

less_equal 小于等于

greater_equal 大于等于

上述例子中系統(tǒng) 自己為sort提供了less仿函數(shù)。在STL中還提供了其他仿函 數(shù)，以下是仿函數(shù)列表: 不能直接寫(xiě)入仿 函數(shù)的名字，而是要寫(xiě)其重載的()函數(shù)： less<int>();

當(dāng)你的容器中元 素時(shí)一些標(biāo)準(zhǔn)類(lèi)型（int float char)或者string時(shí)，你可以直 接使用這些函數(shù)模板。但如果你時(shí)自己定義的類(lèi)型或者你需要按照其他方式排序，你可以有兩種方法來(lái)達(dá)到效果：一種是自己寫(xiě)比較函數(shù)。另一種是重載類(lèi)型的'<'操作賦。

3. 全排序：

全排序即把所給定范圍所有的元素按照大小關(guān)系順序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已經(jīng)不是采用簡(jiǎn)單的快速排序，而是結(jié)合內(nèi)插排序算法)。復(fù)雜度為n*log(n)。stable_sort采用的是"歸并排序"，分派足夠內(nèi)存時(shí)，其算法復(fù)雜度為n*log(n), 否則 其復(fù)雜度為n*log(n)*log(n)，其優(yōu)點(diǎn)是會(huì)保持相等元素之間的相對(duì)位置在排序前后保持一致。

用于全排序的函 數(shù)有：

1.void sort(RandomAccessIterator first, RandomAccessIterator last);

2.void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);

3.void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

4.void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

4. 局部排序：

partial_sort采用的堆排序（heapsort），它在任何情況下的復(fù)雜度都是n*log(n)。

局部排序其實(shí)是為了減少不必要的操作而提供的排序方式。

其函數(shù)原型為：

4.1 void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);

4.2 void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last, StrictWeakOrdering comp);

4.3 RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last);

4.4 RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last, Compare comp);

例如：班上有1000個(gè)學(xué)生，我想知道分?jǐn)?shù)最低的5名是哪些人。

partial_sort(vect.begin(),vect.begin()+5,vect.end(),less<student>());

5. nth_element 指定元素排序

5.1 void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

5.2 void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last,

StrictWeakOrdering comp);

例如：班上有1000個(gè)學(xué)生，我想知道分?jǐn)?shù)排在倒數(shù)第4名的學(xué)生。

nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

6. partition 和stable_partition

partition就是把一個(gè)區(qū)間中的元素按照某個(gè)條件分成兩類(lèi)，并沒(méi)有排序。

其函數(shù)原型為：

6.1 ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)

6.2 ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);

例如：班上10個(gè)學(xué)生，計(jì)算所有沒(méi)有及格（低于60分）的學(xué)生：

student exam("pass", 60);

stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

7. 效率由高到低（耗時(shí)由小變大）：

partion

stable_partition

nth_element

partial_sort

sort

stable_sort

8. Effective STL對(duì)如何選擇排序函數(shù)總結(jié)的很好：

8.1 若需對(duì)vector, string, deque, 或array容器進(jìn)行全排序，你可選擇sort或stable_sort；

8.2 若只需對(duì)vector, string, deque, 或array容器中取得top n的元素，部分排序partial_sort是首選.

8.3 若對(duì)于vector, string, deque, 或array容器，你需要找到第n個(gè)位置的元素或者你需要得到top n且不關(guān)系top n中的內(nèi)部 順序，nth_element是最 理想的；

8.4 若你需要從標(biāo)準(zhǔn)序列容器或者array中把滿足某個(gè)條件 或者不滿足某個(gè)條件的元素分開(kāi)，你最好使用partition或stable_partition；

8.5 若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排 序。

最新評(píng)論