有哪些好的c/c++演算法的書？

01-12

看完學校的教科書，自己再去獨立敲代碼的時候有點力不從心，本來敲的就是很短的代碼，到最後還可能需要百度一下。所以想請問一下有什麼好的演算法書籍？
哦，對了我是嵌入式系統專業的

若是演算法的話，我個人認為是不應該局限於C/C++的，只是目前很多書籍會以演算法 ---- XXXX 語言實現來作為講解，其中一個原因是目標讀者熟悉這種語言。而在推薦書籍前，我想給你我認為一種學習演算法的方式，然後你再看書籍時按照這樣的方法學，或許會好一點點。不過這是我的一言，若你覺得適合你就採用，若覺得不好，也可以再摸索出適合自己的方式，適合自己的才是最好的。

我認為我們若初學演算法，可以分為兩步，第一步，思考清楚演算法，你可以使用自己最舒服的表達方式來記錄你的思考流程。我舉一個例子，如 bubble sort ，你不必最開始就想著如何用 C/C++來寫，你可以考慮清楚bubble sort到底是什麼，然後流程方法是什麼，然後記錄下來。那麼，我來回答這個問題會是類似這樣，bubble sort是一種排序的方法，它可以把給入的元素序列進行排序。它的流程方法是從頭遍歷到尾，挨著比較相鄰的元素，如果它們的大小順序是相反的，就交換它們的位置，並一直重複這個流程，直到給入的元素序列排好序。

那麼，我們如何進行這樣的思路整理呢？第一步，是給入的元素序列，我們可以直接用A來表示就好，為了方便你後面知道這是什麼，你可以注釋這是一個元素序列。

A // Input elements

或者，你更正式一點，可以是 A : type of list, A[]等方式，只要你知道是什麼就好。

那麼我們是處理 bubble sort，接受給入的元素序列，然後進行排序。所以，我會把 bubble sort 作為一個函數處理，然後處理輸入的數據，結果是排好序的元素序列。

A ----&> function bubble_sort ----&> sorted A

// A: Input elements, typically list. function bubble_sort(A)

接下來，我們要做的就是bubble sort的核心工作：從頭遍歷到尾，挨著比較相鄰的元素，如果它們的大小順序是相反的，就交換它們的位置，並一直重複這個流程，直到給入的元素序列排好序。

那麼，我們在最開始思考時，可以更簡單一些，先完成第一步：從頭遍歷到尾，挨著比較相鄰的元素，如果它們的大小順序是相反的，就交換它們的位置。從頭遍歷到尾，我們其實就是從輸入序列的第一個元素開始，然後一直開始遍歷到最後，並且在遍歷的途中，比較兩兩挨著的元素，若大小相反就交換。

// A: Input elements, typically list. function bubble_sort(A): for i := 0 to A.length - 2: if A[i] &> A[i + 1]: swap(A[i], A[i + 1])

那麼，我們這裡需要的起始元素坐標是0，最後一個元素坐標是A.length - 2 (A.length表示輸入序列A的長度). 也就是說，若我現在的輸入元素序列是

5 3 6 7 1

那麼A.length 則為5. 每個元素坐標是：

5 3 6 7 1 Index: 0 1 2 3 4 0 A.length - 1

所以 A.length - 2 是坐標 3，元素是7。由於我們會比 A[i] &> A[i + 1] ，所以我們最後一次比較是

A[A.length - 2] &> A[A.length - 2 + 1] ===&> A[A.length -2] &> A[A.length - 1] ，而這一次完成以後，我們就訪問完了，不需要再比較下去了。

那麼，經過這一次比較以後會是什麼過程呢？首先是5 與 3比較，發現應該3在前，於是交換

5 3 6 7 1 ====&> 3 5 6 7 1 i

i此時變為 1，然後訪問A[i] 與 A[i + 1]，於是5 &> 6嗎？不是，那麼不動，i遞增

3 5 6 7 1 ====&> 3 5 6 7 1 i

6 大於 7 嗎？不是，不動，i遞增

3 5 6 7 1 ====&> 3 5 6 7 1 i

7 大於 1 嗎？是，交換，i 遞增

3 5 6 7 1 ====&> 3 5 6 1 7 i

i此時的值為A.length - 1，大於了A.length - 2，於是此時退出for循環。

那麼這就是我們簡化的第一步了。經過這一步，我們也發現了一個有趣的事實，那就是我們已經把最大的置到最底下了，也就是把最大的泡弄到鍋底了。

接下來，我們來完成：並一直重複這個流程，直到給入的元素序列排好序。

而這一步，其實思想記錄時，你可以很簡單的記錄說，repeat...until A is sorted，如：

// A: Input elements, typically list. function bubble_sort(A): repeat for i := 0 to A.length - 2: if A[i] &> A[i + 1]: swap(A[i], A[i + 1]) until A is sorted

但是，顯然這樣是不好的，因為這樣你無法很直觀的，很清晰的轉換成代碼，我們最好更清晰的轉換成更好的偽代碼描述。讓我們想想，我們每遍歷一次，都會把最大的元素放入到末尾？也就是我們觀察到的一樣。所以，我們最多需要多少次呢？那就是A的元素長度這麼多次。所以，我們可以如何來表示呢？for idx := 0 to A.length - 1，對吧？於是，可以如此：

// A: Input elements, typically list. function bubble_sort(A): for idx := 0 to A.length - 1: for i := 0 to A.length - 2: if A[i] &> A[i + 1]: swap(A[i], A[i + 1]) // end bubble_sort

這樣的話，在完成我們剛才的第一遍遍歷 3 5 6 1 7 以後，idx 就從0變為了1，1 &< 4 (A.length - 1)，於是開始新一輪的循環。

於是從

5 3 6 7 1 -&> 3 5 6 1 7 -&> 3 5 1 6 7 -&> 3 1 5 6 7 -&> 1 3 5 6 7 -&> done.

那麼，這個時候你就可以作為初學演算法的第二步：轉為實際可運行的代碼，如C++代碼（你也可以轉為C代碼）。

那麼，如這裡的輸入元素A，你可以是一個數組，並且另外一個參數為數組長度，當然在C++，你可以是一個std::vector，而元素的類型，我們這裡認為是int，這裡我們以引用傳遞，代表著我們會改變傳入進來的vector，於是，我們不再返回一個新的vector。

// A: Input elements, typically list. function bubble_sort(std::vector& A): for idx := 0 to A.length - 1: for i := 0 to A.length - 2: if A[i] &> A[i + 1]: swap(A[i], A[i + 1]) // end bubble_sort

由於，我們不再返回新的vector，所以，我們的function，可以直接替換為void.

// A: Input elements, typically list. void bubble_sort(std::vector& A): for idx := 0 to A.length - 1: for i := 0 to A.length - 2: if A[i] &> A[i + 1]: swap(A[i], A[i + 1]) // end bubble_sort

接下來，替換for循環，以及A.length, swap, :等，都比較簡單且易對應到C++表達。

// A: Input elements, typically list. void bubble_sort(std::vector& A) { for(int idx = 0; idx &<= A.size() - 1; idx++) { for(int i = 0; i &<= A.size() - 2; i++) { if(A[i] &> A[i + 1]) { std::swap(A[i], A[i + 1]); } } } } // end bubble_sort

隨後，我們可以寫main函數，添加相關的頭文件等，並且構造我們偽代碼的例子進行測試。

#include & #include & #include & // std::swap


// A: Input elements, typically list.

void bubble_sort(std::vector& A) {

    for(int idx = 0; idx &<= A.size() - 1; idx++) {
        for(int i = 0; i &<= A.size() - 2; i++) {
            if(A[i] &> A[i + 1]) {

                std::swap(A[i], A[i + 1]);

             }

          }

     }

}

// end bubble_sort

int main() { std::vector& A {5, 3, 6, 7, 1}; // C++11 syntax bubble_sort(A); std::cout &<&< "after bubble sort..." &<&< std::endl; // C++11 range-based for loop for(const auto elem : A) { std::cout &<&< elem &<&< " "; } std::cout &<&< std::endl; }

那麼，在完成這一步以後，我們初步完成了冒泡演算法的實現。接下來，我們就可以思考，我們是不是可以把冒泡演算法實現的更好？因為我們目前的做法是我們很直白，很淺顯的思考。如最外層的循環，一定需要A.size()這麼多次嗎？(最後那一次是否有意義) 內層循環一定是A.size() - 1 這麼多次嗎？(我們能注意到，當走完第一次以後，7已經在最後一位了，第二次，6在倒數第二位.....)

接下來，我們要做的則是什麼呢？理解冒泡演算法的複雜度，與各種排序演算法的比較，以及更深層次的嚴格證明冒泡演算法是可以工作的等等。

那麼，能推薦的書籍：

演算法導論（原書第3版） (豆瓣) 這一本書的思路和我很類似，都是以偽代碼的思路展開，但是與我相比，欠缺的是如何轉為實際代碼。

演算法（第4版） (豆瓣) 這一本書各種圖例，很淺顯易懂，但是是Java。

數據結構與程序設計 (豆瓣) C++語言編寫，我以前的大學教材，習題很值得一做。

Data Structures Algorithm Analysis in C++ (9780132847377): Mark A. Weiss: Books C++11編寫，若你想要C++11編寫的數據結構教材，可以參看這本書。

HackerRank 練習Data Structures 與 Algorithms版塊，題目難度循循漸進。

寫完發現好長，不過希望對你和閱讀者都有所幫助。

(似乎應該發到專欄去...)

《C語言介面與實現:創建可重用軟體的技術》

雖然這本書不是直接講演算法的，但是裡面有數據結構與常用演算法！

我推薦《STL源碼剖析》

劉汝佳的演算法競賽入門經典第二版不錯

為什麼要局限在C++？比較不錯的兩本書《演算法導論》是類Python的偽代碼，《演算法》是Java，如果一定要C++的話，我想到的是別人整理的Leetcode習題集哈哈哈...

《演算法導論》，經典書籍，不用多說。

演算法（第4版） (豆瓣)