手把手教你5大基礎(chǔ)實(shí)用算法,趕緊mark下來(lái)吧摄凡!

人類社會(huì)文明之所以能快速進(jìn)步续徽,是因?yàn)槲覀兌脤⒅R(shí)一代一代傳授下去。在共享經(jīng)濟(jì)時(shí)代亲澡,大圣眾包威客平臺(tái)(www.dashengzb.cn)手把手教你5大基礎(chǔ)實(shí)用算法并講解钦扭,趕緊mark下來(lái)吧!

歸并排序算法

【概念解析】:

歸并排序(Mergesort床绪,也譯作“合并排序”)客情,是建立在歸并操作上的一種有效的排序算法。

【算法優(yōu)勢(shì)】:

作為采用分治法(DivideandConquer)的一個(gè)應(yīng)用癞己,歸并排序非常典型膀斋。

【算法步驟】:

1.申請(qǐng)空間,使其大小為兩個(gè)已經(jīng)排序序列之和痹雅,該空間用來(lái)存放合并后的序列仰担;

2.設(shè)定兩個(gè)指針,最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置绩社;

3.比較兩個(gè)指針?biāo)赶虻脑厮だ叮x擇相對(duì)小的元素放入到合并空間,并移動(dòng)指針到下一位置愉耙;

4.重復(fù)步驟3直到某一指針達(dá)到序列尾贮尉;

5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

2.BFPRT(線性查找算法)

【概念解析】:

BFPRT算法解決的問(wèn)題十分經(jīng)典朴沿,即從某n個(gè)元素的序列中選出第k大(第k胁卵琛)的元素。它的思想與快速排序思想相似悯仙,當(dāng)然龄毡,為使得算法在最壞情況下吠卷,依然能達(dá)到o(n)的時(shí)間復(fù)雜度锡垄,五位算法作者做了精妙的處理。

【算法優(yōu)勢(shì)】:

基于巧妙的分析祭隔,BFPRT可以保證在最壞情況下仍為線性時(shí)間復(fù)雜度货岭。

【算法步驟】:

1.將n個(gè)元素每5個(gè)一組路操,分成n/5(上界)組;

2.取出每一組的中位數(shù)千贯,以任意排序方法排序屯仗,比如插入排序;

3.遞歸地調(diào)用selection算法搔谴,查找上一步中所有中位數(shù)的中位數(shù)魁袜,設(shè)為x,偶數(shù)個(gè)中位數(shù)的情況下設(shè)定為選取中間小的一個(gè)敦第;

4.用x來(lái)分割數(shù)組峰弹,設(shè)小于等于x的個(gè)數(shù)為k,大于x的個(gè)數(shù)即為n-k芜果;

5.若i=k鞠呈,返回x;若ik右钾,在大于x的元素中遞歸查找第i-k小的元素蚁吝。終止條件:n=1時(shí),返回的即是i小元素舀射。

3.快速排序算法

【概念解析】:

快速排序使用分治法(Divideandconquer)策略來(lái)把一個(gè)串行(list)分為兩個(gè)子串行(sub-lists)窘茁。在平均狀況下,排序n個(gè)項(xiàng)目要Ο(nlogn)次比較后控。在最壞狀況下則需要Ο(n2)次比較庙曙,但這種狀況并不常見。它是由東尼·霍爾所發(fā)展的一種排序算法浩淘。

【算法優(yōu)勢(shì)】:

因?yàn)榭焖倥判虻膬?nèi)部循環(huán)(innerloop)可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)捌朴,所以,通痴懦快速排序明顯比其他Ο(nlogn)算法更快砂蔽。

【算法步驟】:

1.從數(shù)列中挑出一個(gè)元素,稱為“基準(zhǔn)”(pivot)署惯;

2.重新排序數(shù)列左驾,所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面,所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)极谊。在這個(gè)分區(qū)退出之后诡右,該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)(partition)操作轻猖;

3.遞歸(recursive)地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序帆吻。

遞歸的最底部情形,是數(shù)列的大小是零或一咙边,也就是永遠(yuǎn)都已經(jīng)被排序好了猜煮。雖然一直遞歸下去次员,但是這個(gè)算法總會(huì)退出,因?yàn)樵诿看蔚牡╥teration)中王带,它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去淑蔚。

4.動(dòng)態(tài)規(guī)劃算法

【概念解析】:

動(dòng)態(tài)規(guī)劃(Dynamicprogramming)是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的愕撰,通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方法刹衫。

理論上,若要解一個(gè)給定問(wèn)題搞挣,我們需要解其不同部分(即子問(wèn)題)绪妹,再合并子問(wèn)題的解以得出原問(wèn)題的解。通常許多子問(wèn)題非常相似柿究,為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問(wèn)題一次邮旷,從而減少計(jì)算量:一旦某個(gè)給定子問(wèn)題的解已經(jīng)算出,則將其記憶化存儲(chǔ)蝇摸,以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接查表婶肩。所以說(shuō),動(dòng)態(tài)規(guī)劃背后的基本思想非常簡(jiǎn)單貌夕。

【算法優(yōu)勢(shì)】:

動(dòng)態(tài)規(guī)劃常常適用于有重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題律歼,這種方法所耗時(shí)間往往遠(yuǎn)少于樸素解法。動(dòng)態(tài)規(guī)劃算法在重復(fù)子問(wèn)題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長(zhǎng)時(shí)啡专,特別有用险毁。

【算法步驟】:

1.最優(yōu)子結(jié)構(gòu)性質(zhì):如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的,我們就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)(即滿足最優(yōu)化原理)们童。最優(yōu)子結(jié)構(gòu)性質(zhì)為動(dòng)態(tài)規(guī)劃算法解決問(wèn)題提供了重要線索畔况。

2.子問(wèn)題重疊性質(zhì):子問(wèn)題重疊性質(zhì)是指在用遞歸算法自頂向下對(duì)問(wèn)題進(jìn)行求解時(shí),每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題慧库,有些子問(wèn)題會(huì)被重復(fù)計(jì)算多次跷跪。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì),對(duì)每一個(gè)子問(wèn)題只計(jì)算一次齐板,然后將其計(jì)算結(jié)果保存在一個(gè)表格中吵瞻,當(dāng)再次需要計(jì)算已經(jīng)計(jì)算過(guò)的子問(wèn)題時(shí),只是在表格中簡(jiǎn)單地查看一下結(jié)果甘磨,便能獲得較高的效率橡羞。

5.BFS(廣度優(yōu)先搜索算法)

【概念解析】:

廣度優(yōu)先搜索算法(Breadth-First-Search),是一種圖形搜索算法济舆。簡(jiǎn)單地說(shuō)卿泽,BFS是從根節(jié)點(diǎn)開始,沿著樹(圖)的寬度遍歷樹(圖)的節(jié)點(diǎn)吗冤。如果所有節(jié)點(diǎn)均被訪問(wèn)又厉,則算法中止。一般用隊(duì)列數(shù)據(jù)結(jié)構(gòu)來(lái)輔助實(shí)現(xiàn)BFS算法椎瘟。

【算法優(yōu)勢(shì)】:

BFS屬于盲目搜索覆致,即這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。

【算法步驟】:

1.首先將根節(jié)點(diǎn)放入隊(duì)列中肺蔚;

2.從隊(duì)列中取出第一個(gè)節(jié)點(diǎn)煌妈,并檢驗(yàn)它是否為目標(biāo)——如果找到目標(biāo),則結(jié)束搜尋并回傳結(jié)果宣羊;否則將它所有尚未檢驗(yàn)過(guò)的直接子節(jié)點(diǎn)加入隊(duì)列中璧诵;

3.若隊(duì)列為空,表示整張圖都檢查過(guò)了——亦即圖中沒(méi)有欲搜尋的目標(biāo)仇冯,那么之宿,結(jié)束搜尋并回傳“找不到目標(biāo)”;

4.重復(fù)步驟2苛坚。

希望以上基礎(chǔ)實(shí)用的算法講解比被,能夠?qū)δ愕膶W(xué)習(xí)與工作有實(shí)際的教導(dǎo)意義。

(更多大數(shù)據(jù)與商業(yè)智能領(lǐng)域干貨泼舱、兼職機(jī)會(huì)請(qǐng)關(guān)注大圣眾包平臺(tái)等缀,或添加大圣花花個(gè)人微信號(hào)(dashenghuaer),拉你入bigdata&BI交流群330648564娇昙。)

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末尺迂,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子冒掌,更是在濱河造成了極大的恐慌噪裕,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,946評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件股毫,死亡現(xiàn)場(chǎng)離奇詭異州疾,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)皇拣,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門严蓖,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人氧急,你說(shuō)我怎么就攤上這事颗胡。” “怎么了吩坝?”我有些...
    開封第一講書人閱讀 169,716評(píng)論 0 364
  • 文/不壞的土叔 我叫張陵毒姨,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我钉寝,道長(zhǎng)弧呐,這世上最難降的妖魔是什么闸迷? 我笑而不...
    開封第一講書人閱讀 60,222評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮俘枫,結(jié)果婚禮上腥沽,老公的妹妹穿的比我還像新娘。我一直安慰自己鸠蚪,他們只是感情好今阳,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著茅信,像睡著了一般盾舌。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上蘸鲸,一...
    開封第一講書人閱讀 52,807評(píng)論 1 314
  • 那天妖谴,我揣著相機(jī)與錄音,去河邊找鬼酌摇。 笑死窖维,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的妙痹。 我是一名探鬼主播铸史,決...
    沈念sama閱讀 41,235評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼怯伊!你這毒婦竟也來(lái)了琳轿?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,189評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤耿芹,失蹤者是張志新(化名)和其女友劉穎崭篡,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體吧秕,經(jīng)...
    沈念sama閱讀 46,712評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡琉闪,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評(píng)論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了砸彬。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片颠毙。...
    茶點(diǎn)故事閱讀 40,926評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖砂碉,靈堂內(nèi)的尸體忽然破棺而出蛀蜜,到底是詐尸還是另有隱情,我是刑警寧澤增蹭,帶...
    沈念sama閱讀 36,580評(píng)論 5 351
  • 正文 年R本政府宣布滴某,位于F島的核電站,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏霎奢。R本人自食惡果不足惜户誓,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望幕侠。 院中可真熱鬧帝美,春花似錦、人聲如沸橙依。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)窗骑。三九已至,卻和暖如春漆枚,著一層夾襖步出監(jiān)牢的瞬間创译,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工墙基, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留软族,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,368評(píng)論 3 379
  • 正文 我出身青樓残制,卻偏偏與公主長(zhǎng)得像立砸,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子初茶,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評(píng)論 2 361

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