從廣義上講，很多算法解決問題的思路是相同的。因此，為了方便，通常按照算法采用的方法和思路來給它們分類。這樣給算法分類的一個原因是：如果我們理解了它采用的一般思路我們常常就能夠對該算法獲得一些深入的了解。在解決一些沒有現成算法求解，但與現有問題類似的問題時，我們從中可以得到一些啟發和靈感。當然，有些算法有悖于分類原則，而另一些則是多種方法相結合的產物。這一節將介紹一些常用的方法。

1 隨機法

隨機法依賴于隨機數的統計特性。一個應用隨機法的例子是快速排序。

快速排序按如下方式工作：設想要對一堆作廢的支票排序，首先將無序的一整堆分成兩部分。其中一堆里使所有的支票號碼都小于等于所設定的一個中間值，另一堆里保證所有的支票號碼都大于這個中間值。一旦有了這樣的兩堆支票后，就再以同樣的方式對這兩堆支票重復剛才的劃分過程，直到每一堆里都只有一張支票為止。這個時候所有的支票就都排好序了。

為了獲得較高的性能，快速排序依賴于每一次要如何劃分支票，我們需要讓劃分出的兩堆支票數量幾乎相同。為了實現這一步，理想的方法是在劃分支票之前首先找到支票號碼的中間值。可是為了確定這個中間值需要遍歷所有的支票，因此我們并不打算這么做。作為替代的方法，隨機選擇一個支票號碼作為劃分的依據。快速排序的平均性能很不錯，因為隨機數的正態分布使得劃分的結果是相對平衡的。

2 分治法

分治法包含3個步驟：分解、求解與合并。在分解階段，將數據分解為更小、更容易管理的部分。在求解階段，對每個分解出的部分進行處理。在合并階段，將每部分處理的結果進行合并。一個分治法的例子是歸并排序。

歸并排序按照如下方式工作。如前所述，同樣假設要排序一堆作廢的支票。首先將無序的一整堆分成兩半，下一步分別將兩堆支票再各自分成兩半，一直持續這個步驟直到每一堆中都只有一張支票為止。一旦所有堆中都只有一張支票時，就將其兩兩合并且保證每一個合并后的新堆都是有序的。一直做兩兩合并直到重新得到一大堆，此時所有的支票就都已經排好序了。

在所有的分治算法中都有相同的三個步驟。歸并排序能以以下方式來描述，首先，在分解階段將數據劃分為兩份。接下來，按照遞歸的方式對分解出的兩部分應用歸并排序。最后，在合并階段將兩部分合并成一個排好序的集合。

3 動態規劃

動態規劃同分治法類似，都是將較大的問題分解為子問題最后再將結果合并。然而，它們處理問題的方式與子問題之間的關系有關。在分治法中，每一個子問題都是獨立的。為此，我們以遞歸（見第3章）的方式解決每一個子問題，然后將結果與其他子問題的結果合并。在動態規劃中，子問題之間并不是獨立的。換句話說，子問題之間可能有關聯。這類問題采用動態規劃法比分治法更合適。因為若用分治法來解決這類問題會多做很多不必要的工作，有些子問題會重復計算多次。盡管動態規劃法是一種重要的思想且很多算法都利用了這種思想，但本書介紹的算法中都沒有使用到它。

4 貪心法

貪心法在求解問題時總能夠做出在當前的最佳選擇。換句話說，不是從整體最優上考慮，而僅僅是在某種意義上的局部最優解。遺憾的是，當前的最優解長遠來看卻未必是最優的。因此，貪心法并不會一直產生最優結果。然而，在某些方面來說，貪心法確是最佳選擇。一個采用貪心法的例子是霍夫曼編碼（見第14章），這是一個數據壓縮算法。

霍夫曼編碼中最重要的部分是構建一棵霍夫曼樹（又稱最優二叉樹）。為了構建一棵霍夫曼樹，從它的葉子節點自底向上處理。將每個要壓縮的符號和它們在數據中出現的次數（頻率）一起作為二叉樹的根節點保存。接下來，選擇兩棵擁有最小頻率值的根節點作為左右子樹節點，構造一棵新的二叉樹，且保證新的二叉樹根節點的頻率值為左右子樹節點的頻率值之和。然后重復這個步驟，直到得到唯一的一棵樹，這就是最終的霍夫曼樹。霍夫曼樹的根節點包含數據中符號的總數，葉子節點包含原始的符號以及它們出現的頻率。霍夫曼編碼是一種貪心算法，因為每次它都會挑選出當前最合適的兩棵樹來合并。

5 近似法

并不計算出最優解，相反，它只計算出“足夠好”的解。通常利用近似法解決那些計算成本很高又因為其本身十分有價值而不愿放棄的問題。推銷員問題（見第16章）是一個通常會用近似法去解決的問題。

設想一位推銷員需要設計一條去往好幾個城市工作的路線。推銷員問題的目的是找到最短的可能路徑，以便推銷員能夠在回到出發點前恰好每座城市都只去過一次。由于推銷員問題可能存在一種最優的策略，但計算的代價很高，因此可以采用啟發式的方法得到一個近似解。當最優策略行不通時，啟發式的方法是我們能夠接受的一種比最優策略稍遜一些的策略。

推銷員問題可以用圖表的方式來描繪。把推銷員必須前往的城市在格子中用點標記出來。然后按照如下啟發式的方法來尋找這些點之間的最短路徑。從推銷員出發的位置開始只有一個點，將這個點涂黑。所有其他的點在加入路線圖之前都是白色的，當它們加入時也同樣涂黑。接下來，對于每一個還沒有加入到路線圖中的點v，計算最后一個加入到路線圖中的點u和v之間的距離。通過這種方法，選擇離u最近的那個點，將其涂黑并加入路線圖中。重復這個過程直到所有的點都已經涂黑。最后，再次將出發點加入路線圖使其閉合，這樣就完成了整個路線圖。