大學要學會這8種算法程序員
程序員8條程序算法必須掌握
算法壹: 快速排序算法
快速排序是由東尼·霍爾所發展的壹種排序算法。在平均狀況下，排序n個項目要O(nlogn)次比較。在最壞狀況下則需要O(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他O(nlogn)算法更快，因為它的內部循環 (innerloop)可以在大部分的架構上很有效率地被實現出來。快速排序使用分治法(Divideandconquer)策略來把壹個串行(list)分為兩個子串行(sub-lists)。
算法二: 堆排序算法
堆排序(Heapsort)是指利用堆這種數據結構所設計的壹種排序算法。堆積是壹個近似完全二叉樹的結構，並同時滿足堆積的性質:即子結點的鍵值或索引總是小幹(或者大幹)它的父節點。堆排序的平均時間復雜度為O(nlogn)。
算法步驟:
1.創建壹個堆H[0.n-1]
2.把堆首(最大值)和堆尾互換
3.把堆的尺寸縮小1，並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置4.重復步驟2，直到堆的尺寸為1
算法三: 歸並排序
歸並排序(Mergesort，臺灣譯作: 合並排序)是建立在歸並操作上的壹種有效的排序算法。該算法是采用分治法(DivideandConquer)的壹個非常典型的應用。
算法步驟:
1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3.比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下壹位置4.重復步驟3直到某壹指針達到序列尾5.將另壹序列剩下的所有元素直接復制到合並序列尾
算法四: 二分查找算法二分查找算法
是壹種在有序數組中查找某壹特定元素的搜索算法。
搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束:如果某壹特定元素大幹或者小幹中間元素，則在數組大於或小千中間元素的那壹半中查找，而且跟開始壹樣從中間元素開始比較。如果在某壹步驟數組為空，則代表找不到。這種搜索算法每壹次比較都使搜索範圍縮小壹半。折半搜索每次把搜索區域減少壹半，時間復雜度為O(logn)
如果在某壹步驟數組為空，則代表找不到。這種搜索算法每壹次比較都使搜索範圍縮小壹半。折半搜索每次把搜索區域減少壹半，時間復雜度為O(logn) 。
算法五: BFPRT(線性查找算法）
BFPRT算法解決的問題十分經典，即從某n個元素的序列中選出第k大(第k小)的元素，通過巧妙的分析BFPRT可以保證在最壞情況下仍為線性時間復雜度該算法的思想與快速排序思想相似，當然，為使得算法在最壞情況下，依然能達到o(n)的時間復雜度，五位算法作者做了精妙的處理。
算法六: DFS(深度優先搜索）
深度優先搜索算法(Depth-First-Search)，是搜索算法的壹種。它沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這壹過程壹直進行到已發現從源節點可達的所有節點為止。
如果還存在未被發現的節點，則選擇其中壹個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。DFS屬於盲目搜索。深度優先搜索是圖論中的經典算法，利用深度優先搜索算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。壹般用堆數據結構來輔助實現DFS算法。
算法七: BFS廣度優先搜索算法
(Breadth-First-Search)，是壹種圖形搜索算法。簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則算法中止BFS同樣屬幹盲目搜索。壹般用隊列數據結構來輔助實現BFS算法。
算法步驟:
1.首先將根節點放入隊列中。
2.從隊列中取出第壹個節點，並檢驗它是否為目標。如果找到目標，則結束搜尋並回傳結果。否則將它所有尚未檢驗過的直接子節點加入隊列中。
3.若隊列為空，表示整張圖都檢查過了壹壹亦即圖中沒有欲搜尋的目標。結束搜尋並回傳“找不到目標”4.重復步驟2。
算法八: 動態規劃算法
動態規劃(Dynamicprogramming)是壹種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。動態規劃常常適用幹有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。
動態規劃背後的基本思想非常簡單。大致上，若要解壹個給定問題，我們需要解其不同部分(即子問題)，再合並子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題壹次，從而減少計算量:壹旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同壹個子問題解之時直接查表。