STL中一些算法的總結(jié)
1.函數(shù)的名字列表:
sort
對給定區(qū)間所有元素進(jìn)行排序
stable_sort
對給定區(qū)間所有元素進(jìn)行穩(wěn)定排序
partial_sort
對給定區(qū)間所有元素部分排序
partial_sort_copy
對給定區(qū)間復(fù)制并排序
nth_element
找出給定區(qū)間的某個(gè)位置對應(yīng)的元素
is_sorted
判斷一個(gè)區(qū)間是否已經(jīng)排好序
partition
使得符合某個(gè)條件的元素放在前面
stable_partition
相對穩(wěn)定的使得符合某個(gè)條件的元素放在前面
2. 比較函數(shù):
equal_to
相等
not_equal_to
不相等
less
小于
greater
大于
less_equal
小于等于
greater_equal
大于等于
上述例子中系統(tǒng) 自己為sort
提供了less
仿函數(shù)。在STL中還提供了其他仿函 數(shù)长赞,以下是仿函數(shù)列表: 不能直接寫入仿 函數(shù)的名字蝇狼,而是要寫其重載的()函數(shù): less<int>();
當(dāng)你的容器中元 素時(shí)一些標(biāo)準(zhǔn)類型(int float char
)或者string
時(shí)度硝,你可以直 接使用這些函數(shù)模板。但如果你時(shí)自己定義的類型或者你需要按照其他方式排序购笆,你可以有兩種方法來達(dá)到效果:一種是自己寫比較函數(shù),另一種是重載類型的<
操作符。
3. 全排序:
全排序即把所給定范圍所有的元素按照大小關(guān)系順序排列诉儒。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已經(jīng)不是采用簡單的快速排序,而是結(jié)合內(nèi)插排序算法)亏掀。復(fù)雜度為nlog(n)忱反。stable_sort
采用的是"歸并排序"泛释,分派足夠內(nèi)存時(shí),其算法復(fù)雜度為nlog(n), 否則 其復(fù)雜度為nlog(n)log(n)温算,其優(yōu)點(diǎn)是會(huì)保持相等元素之間的相對位置在排序前后保持一致怜校。
用于全排序的函 數(shù)有:
void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator
last,StrictWeakOrdering comp);
void stable_sort(RandomAccessIterator first, RandomAccessIterator
last);
void stable_sort(RandomAccessIterator first, RandomAccessIterator
last, StrictWeakOrdering comp);
4. 局部排序:
partial_sort
采用的堆排序(heapsort),它在任何情況下的復(fù)雜度都是n*log(n)注竿。
局部排序其實(shí)是為了減少不必要的操作而提供的排序方式茄茁。
其函數(shù)原型為:
void partial_sort(RandomAccessIterator first, RandomAccessIterator
middle,RandomAccessIterator last);
void partial_sort(RandomAccessIterator first,RandomAccessIterator
middle,RandomAccessIterator last, StrictWeakOrdering comp);
RandomAccessIterator partial_sort_copy(InputIterator first,
InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIter
ator result_last);
RandomAccessIterator partial_sort_copy(InputIterator first,
InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIter
ator 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
指定元素排序
void nth_element(RandomAccessIterator first,
RandomAccessIterator nth, RandomAccessIterator last);
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è)條件分成兩類宣谈,并沒有排序愈犹。
其函數(shù)原型為:
ForwardIterator partition(ForwardIterator first, ForwardIterator last,
Predicate pred)
ForwardIterator stable_partition(ForwardIterator first,
ForwardIterator last, Predicate pred);
例如:班上10個(gè)學(xué)生,計(jì)算所有沒有及格(低于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. 如何選擇排序函數(shù):
若需對vector
, string
, deque,
或array
容器進(jìn)行全排序闻丑,你可選擇sort
或stable_sort
漩怎;
若只需對vector
, string
, deque
, 或array
容器中取得top n的元素,部分排序partial_sort
是首選.
若對于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
排序徒恋。