“

這是整個架構師連載系列，分為9大步驟，我們現在還在第一個步驟：程序設計和開發->數據結構與算法。

我們今天講解重點講解算法。

算法思想

1 貪心思想

顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。如單源最短路經問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優解，其最終結果卻是最優解的很好近似。在面臨選擇時，貪心算法都作出對眼前來講最有利的選擇，不考慮對將來的不良影響，每個選擇一旦做出，不可更改，不允許回溯，根據不同的貪心策略，貪心算法就不同，貪心解的質量也不同，所以貪心策略很重要。可以看出，此算法思想很簡單，具有高效性，但不一定得出最優解。

2 分治法

當我們求解某些問題時，由于這些問題要處理的數據相當多，或求解過程相當復雜，使得直接求解法在時間上相當長，或者根本無法直接求出。對于這類問題，我們往往先把它分解成幾個子問題，找到求出這幾個子問題的解法后，再找到合適的方法，把它們組合成求整個問題的解法。如果這些子問題還較大，難以解決，可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。

3 動態規劃

動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。

4 搜索法

搜索法包含窮舉搜索，深度優先搜索，廣度優先搜索，回溯法，分支限界法，其實這些算法的基礎就是窮舉搜索，只是加上一定的原則來優化過程，就形成了后面的幾種算法，回溯法就是在深度優先搜索的基礎上允許回溯，分支限界法是在廣度優先搜索基礎上允許剪枝，學習時主要學習思想，這些算法名字不要太在意。

5 新近出現的部分算法簡介

①　遺傳算法

從達爾文的生物進化論中得到啟發，借鑒自然選擇和進化的原理，模擬生物在自然界的進化過程所形成的一種優化求解方法，遺傳算法從代表問題的可能潛在解集的一個種群出發，一個種群有一定數量的個體組成，每個個體實際上是染色體帶有特征的實體，每一代根據個體的適應度大小挑選個體，并借助遺傳算子進行交叉和變異，得到近似最優解。

②　模擬退火算法

他的出發點是物理中固體的退火過程與一般組合優化之間的相似性，固態物質退火時，通常先加溫，使其中的粒子自由游動，然后逐漸降低溫度，粒子也逐漸形成低能態的晶格，最終形成最低能量的基態。所以他從某一較高初溫開始，伴隨溫度參數的不斷下降重復抽樣，最終得到全局最優解，他是基于概率的。

③　蟻群算法

蟻群算法是模擬自然界螞蟻覓食過程的一種分布式，啟發式群體智能算法，用于求解復雜的組合優化問題，如TSP,JSSP,GCP等問題。

6 遞歸法

所謂遞歸，就是指如果需要求解當前狀態就需要求解其依賴的遷移狀態。

一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

采用遞歸描述的算法通常有這樣的特征：

1）為求解規模為N的問題，設法將它分解成規模較小的問題；

2）然后從這些小問題的解方便地構造出大問題的解，并且這些規模較小的問題也能采用同樣的分解和綜合方法，分解成規模更小的問題，并從這些更小問題的解構造出規模較大問題的解。

3）這樣的分解方法具有收斂性。即存在一個遞歸返回狀態。

7 迭代法

也稱輾轉法，是一種不斷用變量的舊值遞推新值的過程。

最常見的迭代法是牛頓法。其他還包括最速下降法、共軛迭代法、變尺度迭代法、最小二乘法、線性規劃、非線性規劃、單純型法、懲罰函數法、斜率投影法、遺傳算法、模擬退火等等。

利用迭代算法解決問題，需要做好以下三個方面的工作：

1）迭代變量：在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。

2）迭代關系：指如何從變量的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。

3）迭代過程：迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對于前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對于后一種情況，需要進一步分析出用來結束迭代過程的條件。

迭代法都可以轉為遞歸法。迭代法可以理解為具有遞歸性質的非遞歸解法。當然，非遞歸解法還可利用棧的思想。

經典算法

排序算法

排序大的分類可以分為兩種：內排序和外排序。在排序過程中，全部記錄存放在內存，則稱為內排序，如果排序過程中需要使用外存，則稱為外排序。下面講的排序都是屬于內排序。

內排序有可以分為以下幾類：

（1）、插入排序：直接插入排序、二分法插入排序、希爾排序。

（2）、選擇排序：簡單選擇排序、堆排序。

（3）、交換排序：冒泡排序、快速排序。

（4）、歸并排序

（5）、基數排序

查找算法

1. 順序查找

2. 二分查找

3. 插值查找

4. 斐波那契查找

5. 樹表查找

6. 分塊查找

7. 哈希查找

查找是在大量的信息中尋找一個特定的信息元素，在計算機應用中，查找是常用的基本運算，例如編譯程序中符號表的查找。以上是常見的七種查找算法，說是七種，其實二分查找、插值查找以及斐波那契查找都可以歸為一類——插值查找。插值查找和斐波那契查找是在二分查找的基礎上的優化查找算法。

后續再詳細介紹具體的數據結構。

你可能也喜歡:

java架構師進階之獨孤九劍：數據結構以及書籍推薦

java架構師進階獨孤九劍系列（一）：數據結構與算法

---

總結

以上是生活随笔為你收集整理的java架构师进阶之独孤九剑(一)-算法思想与经典算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。