懂算法的程序員

不懂算法的程序員

算法的力量

算法是計(jì)算機(jī)科學(xué)領(lǐng)域最重要的基石之一，但卻受到了一些程序員的冷落。

許多小伙伴看到一些公司在招聘時(shí)要求的編程語(yǔ)言五花八門(mén)就產(chǎn)生了一種誤解，認(rèn)為學(xué)計(jì)算機(jī)就是學(xué)各種編程語(yǔ)言，或者認(rèn)為，學(xué)習(xí)最新的語(yǔ)言、技術(shù)、標(biāo)準(zhǔn)就是最好的鋪路方法。

其實(shí)大家都被這些公司和培訓(xùn)機(jī)構(gòu)誤導(dǎo)了。

編程語(yǔ)言雖然該學(xué)，但是學(xué)習(xí)計(jì)算機(jī)算法和理論更重要，因?yàn)橛?jì)算機(jī)語(yǔ)言和開(kāi)發(fā)平臺(tái)日新月異，但萬(wàn)變不離其宗的是那些算法和理論。

例如數(shù)據(jù)結(jié)構(gòu)、算法、編譯原理、計(jì)算機(jī)體系結(jié)構(gòu)、關(guān)系型數(shù)據(jù)庫(kù)原理等等。

這些基礎(chǔ)課程更可以稱(chēng)之為為“內(nèi)功”，而新的語(yǔ)言、技術(shù)、標(biāo)準(zhǔn)則更像是“外功”。

整天趕時(shí)髦的人最后只懂得招式，沒(méi)有功力，是不可能成為高手的。

“程序員是否必須會(huì)算法”。

這是一個(gè)充滿(mǎn)爭(zhēng)議的問(wèn)題，雖然并不像“生存還是毀滅”之類(lèi)的選擇那樣艱難而沉重，但也絕不是一個(gè)輕松的話(huà)題。

很多人對(duì)算法的理解太片面，很多人覺(jué)得只有名字里包含“XX算法”之類(lèi)的東西才是算法。

而我們認(rèn)為算法的本質(zhì)是解決問(wèn)題，只要是能解決問(wèn)題的代碼就是算法。

初學(xué)

讀書(shū)計(jì)劃的第一步是選擇書(shū)籍，這里首推算法導(dǎo)論，這本書(shū)深入淺出，全面地介紹了計(jì)算機(jī)算法。對(duì)每一個(gè)算法的分析既易于理解又十分有趣，并保持了數(shù)學(xué)嚴(yán)謹(jǐn)性。

程序員需要知道的5大基礎(chǔ)實(shí)用算法

算法一：快速排序

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。

在平均狀況下，排序 n 個(gè)項(xiàng)目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他Ο(n log n) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。

算法二：堆排序算法

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿(mǎn)足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

堆排序的平均時(shí)間復(fù)雜度為Ο(nlogn) 。

算法三：歸并排序

歸并排序（Merge sort，***譯作：合并排序）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

算法四：二分查找算法

二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法。

搜素過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜 素過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。

如果在某一步驟數(shù)組 為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區(qū)域減少一半，時(shí)間復(fù)雜度為Ο(logn) 。

算法五：BFPRT(線(xiàn)性查找算法)

BFPRT算法解決的問(wèn)題十分經(jīng)典，即從某n個(gè)元素的序列中選出第k大（第k小）的元素，通過(guò)巧妙的分 析，BFPRT可以保證在最壞情況下仍為線(xiàn)性時(shí)間復(fù)雜度。該算法的思想與快速排序思想相似，當(dāng)然，為使得算法在最壞情況下，依然能達(dá)到o(n)的時(shí)間復(fù)雜 度，五位算法作者做了精妙的處理。