【GeekBand】Week05-STL-01

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)行全排序闻丑,你可選擇sortstable_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è)條件的元素分開酸钦,你最好使用partitionstable_partition怪得;
若使用的list容器,你可以直接使用partitionstable_partition算法卑硫,你可以使用list::sort代替sortstable_sort排序徒恋。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市欢伏,隨后出現(xiàn)的幾起案子入挣,更是在濱河造成了極大的恐慌,老刑警劉巖硝拧,帶你破解...
    沈念sama閱讀 218,546評論 6 507
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件径筏,死亡現(xiàn)場離奇詭異,居然都是意外死亡障陶,警方通過查閱死者的電腦和手機(jī)滋恬,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,224評論 3 395
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來抱究,“玉大人恢氯,你說我怎么就攤上這事。” “怎么了勋拟?”我有些...
    開封第一講書人閱讀 164,911評論 0 354
  • 文/不壞的土叔 我叫張陵勋磕,是天一觀的道長。 經(jīng)常有香客問我敢靡,道長挂滓,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,737評論 1 294
  • 正文 為了忘掉前任醋安,我火速辦了婚禮杂彭,結(jié)果婚禮上墓毒,老公的妹妹穿的比我還像新娘吓揪。我一直安慰自己,他們只是感情好所计,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,753評論 6 392
  • 文/花漫 我一把揭開白布柠辞。 她就那樣靜靜地躺著,像睡著了一般主胧。 火紅的嫁衣襯著肌膚如雪叭首。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,598評論 1 305
  • 那天踪栋,我揣著相機(jī)與錄音焙格,去河邊找鬼。 笑死夷都,一個(gè)胖子當(dāng)著我的面吹牛眷唉,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播囤官,決...
    沈念sama閱讀 40,338評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼冬阳,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了党饮?” 一聲冷哼從身側(cè)響起肝陪,我...
    開封第一講書人閱讀 39,249評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎刑顺,沒想到半個(gè)月后氯窍,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,696評論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡蹲堂,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,888評論 3 336
  • 正文 我和宋清朗相戀三年狼讨,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片贯城。...
    茶點(diǎn)故事閱讀 40,013評論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡熊楼,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情鲫骗,我是刑警寧澤犬耻,帶...
    沈念sama閱讀 35,731評論 5 346
  • 正文 年R本政府宣布,位于F島的核電站执泰,受9級特大地震影響枕磁,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜术吝,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,348評論 3 330
  • 文/蒙蒙 一计济、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧排苍,春花似錦沦寂、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,929評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至彤守,卻和暖如春毯侦,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背具垫。 一陣腳步聲響...
    開封第一講書人閱讀 33,048評論 1 270
  • 我被黑心中介騙來泰國打工侈离, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人筝蚕。 一個(gè)月前我還...
    沈念sama閱讀 48,203評論 3 370
  • 正文 我出身青樓卦碾,卻偏偏與公主長得像,于是被迫代替她去往敵國和親饰及。 傳聞我的和親對象是個(gè)殘疾皇子蔗坯,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,960評論 2 355

推薦閱讀更多精彩內(nèi)容

  • 排序算法 按照是否將元素放入到內(nèi)存中,排序分為內(nèi)部排序和外部排序燎含。內(nèi)部排序適合元素不多的文件宾濒,按照元素的排序原則,...
    DevKyle閱讀 1,156評論 0 49
  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗(yàn)屏箍。 張土汪:刷leetcod...
    土汪閱讀 12,745評論 0 33
  • sort(s.begin(),s.end(),less) 第三個(gè)參數(shù)可以不寫绘梦,默認(rèn)是升序。也可以用函數(shù)指針或者函數(shù)...
    元素周期表的十七君閱讀 510評論 0 0
  • 算法 頭文件 (STL算法部分主要由頭文件,,組成赴魁。要使用STL中的算法函數(shù)必須包含頭文件卸奉,對于數(shù)值算法須包含,中...
    Wancho閱讀 425評論 0 1
  • 今天是二十四節(jié)氣中的小雪,北方降雪,冷空氣南下疹鳄,廈門氣象臺(tái)發(fā)布了降溫預(yù)警拧略,迎來降溫降雨刮風(fēng)模式,我好像聞到了空氣中...
    上官燕玲112閱讀 477評論 0 3