《啊哈！算法》
零零散散花了一周的時間閱讀了《啊哈！算法》。這本書内容相對基礎，适合初學者時閱讀（當然，大神也可以溫故而知新）。《啊哈！算法》這本書中的算法舉例貼近生活，語言诙諧幽默，不會讓人産生枯燥感，并配有很多幽默的插圖。算法講解通俗易懂，并配有詳細C語言代碼和注釋，是一本初學者不易錯過的好書。注：書作者偶爾會在書中賣萌的。已掌握的知識點在下面不在贅述，隻記錄覺得需要記憶整理的東西，作為自己的讀書筆記。包括一些小技巧、新概念、生疏算法等。内容仍比較雜亂，需要進一步細化整理。
來兩張配圖
快排：
冒泡排序：
《啊哈！算法》中涉及的資料結構有棧、隊列、連結清單、樹、并查集、堆和圖等；涉及的算法有排序、枚舉、深度和廣度優先搜尋、圖的周遊，當然還有圖論中不可以缺少的四種最短路徑算法、兩種最小生成樹算法、割點與割邊算法、二分圖的最大比對算法等。
第一章 排序
桶排序、冒泡排序、快速排序
1.當需要對5個人的名字和分數排序：
| 名字 | Huhu | Haha | Hengheng | Gaoshou | Xixi |
| 分數 | 5 | 3 | 5 | 2 | 8 |
使用簡單的桶排序隻能對分數進行排序，如何找分數對應的人呢？
可以使用”結構體+排序算法”解決
struct student{
char name[21];
Int score;
}
2.快速排序中
待排矩陣為A[]：
| 6 | 1 | 2 | 7 | 9 | 3 | 4 | 5 | 10 | 8 |
如果設定基準數是最左邊的數，最左邊的哨兵為i，最右邊的那麼需要哨兵j先走。因為這樣才能保證最後哨兵i和j相遇的時候，A[i]=A[j]>=A[1]。這樣與A[j]與A[1]交換後才滿足快排算法分組要求，哨兵左邊的數小于等于哨兵，右邊的數大于等于哨兵。
3.數列去重并排序（隻保留不同的數，并從小到大排序）
方法1：先去重，後排序
例：桶排序
去重代碼：
%init
for(i=1;i<=n;i++){
scanf(“%d”,&t);
a[t]=1;//标記出現過的數
}
%printf
方法2:先排序，後去重
例：冒泡排序
去重代碼：
%sort
for(i=2;i<=n;i++){
if(a[i] != a[i-1])/如果目前這個數是第一次出現就輸出
Printf(“%d”,a[i]);
}
第二章 棧、隊列、連結清單
1.隊列的隊首head和隊尾的下一個位置tail
問題：為什麼tail不直接記錄隊尾？
答：隊首和隊尾重合時會帶來一些麻煩。我們規定隊首和隊尾重合時，隊列為空。（其實也可以直接記錄隊尾，依據自己情況而定）
2.棧解密回文很友善
3.連結清單
連結清單的另一種表現形式（不用指針，數組形式實作）
模拟連結清單：數組data存儲序列中的每一個數，數組right存放序列中每一個數右邊的數是誰
如果要表示連結清單2->3->4->8->9->10->18->26->32
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Data | 2 | 3 | 4 | 8 | 9 | 10 | 18 | 26 | 32 |
| Right | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
如果在8 的前面插入 6 ， 2->3->4-> 6->8->9->10->18->26->32 那麼數組修改 : 注：right[0] 表示右邊沒有元素
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| Data | 2 | 3 | 4 | 8 | 9 | 10 | 18 | 26 | 32 | 6 |
| Right | 2 | 3 | 10 | 5 | 6 | 7 | 8 | 9 | 4 |
第三章 枚舉
1.暴力枚舉問題
可以思考是否可以采用深度優先搜尋（DFS）和廣度優先搜尋（BFS）代替，進而簡化算法。
第四章 搜尋
深度優先搜尋和廣度優先搜尋
1.深度優先搜尋基本模型
Void dfs(int step)
{
判斷邊界//邊界中注意ruturn
嘗試每一種可能 for(i=1;i<=n;i++)
{
繼續下一步 dsf(step+1);
}
傳回
}
2.Floodfill漫水填充法（也稱種子填充法）
3.DFS與BFS時間複雜度都是O(|V| + |E|)，其中|V|是節點的數目,而|E|是圖中邊的數目。
第五章 圖
1圖是一種比線性表和樹更為複雜的資料結構
線性表:元素之間是線性關系，即表中元素最多一個直接前驅和一個直接後繼。
樹：元素之間是層次關系。除根外，元素隻有唯一直接前驅，但可以有若幹個直接後繼。
圖：任意的兩個元素都可能相關，即圖中任一進制素可以有若幹個直接前驅和直接後繼，屬于網狀結構類型。
注意:實際上，樹是圖的特列---有向無環圖
2.圖的鄰接矩陣存儲法和鄰接表存儲法
第六章 最短路徑
最短路徑算法對比分析
| Floyd | Dijkstra | Bellman-Ford | 隊列優化的Bellman-Ford | |
| 空間複雜度 | O(N^2) | O(M) | O(M) | O(M) |
| 時間複雜度 | O(N^3) | O((M+N)logN) | O(NM) | 最壞是O(NM) |
| 适用情況 | 1.稠密圖 2.和頂點關系密切 | 1.稠密圖 2.和頂點關系密切 | 1.稀疏圖 2.和邊關系密切 | 1.稀疏圖 2.和邊關系密切 |
| 負權 | 可以解決負權 | 不能解決負權 | 可以解決負權 | 可以解決負權 |
注：其中N表示點數，M表示邊數
Floyd算法雖然總體時間複雜度，但是可以解決負權邊(不能解決負權環，實際上這幾種都無法解決負權回路，因為一直循環下去總能找到更小的路徑)，并且均攤到每一點對上，在所有的算法中還是比較好的. Floyd算法代碼複雜度小也是一大優勢. Dijkstra算法最大的弊端就是無法适應有負權邊的圖，但Dijkstra具有很好的可擴充性，另外在Dijkstra算法在選擇剩餘不在最短路徑頂點的集合中選擇最小值是可以堆優化，這樣算法的時間複雜度可以達到O(MlogN). 當圖中含有負邊時，使用Bellman-Ford或者隊列優化的Bellman-Ford算法.
第七章 樹
1.樹其實就是不含回路的無向圖
2.堆是一種特殊的特殊的完全二叉樹
3.優先隊列：支援插入元素和尋找最大（小）值元素的資料結構。
如果使用普通隊列來實作這個兩個功能，那麼尋找最大元素需要枚舉整個隊列，這樣的時間複雜度比較高。如果已排序好的數組，那麼插入一個元素則需要移動很多元素，時間複雜度依舊很高。而堆就是一種優先隊列的實作，可以很好的解決這兩種操作。
4.堆還經常被用來求一個數列中第K大的數。隻需要建立一個大小為K的最小堆，堆頂就是第K大的數。如果求一個數列中第K小的數，隻最需要建立一個大小為K的最大堆，堆頂就是第K小的數，這種方法的時間複雜度是O(NlogK)。當然你也可以用堆來求前K大的數和前K小的數。
5.并查集是一種樹型的資料結構，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。常常在使用中以森林來表示。
第八章 更多精彩算法
1.最小生成樹
Kruskal算法是一步步地将森林中的樹進行合并，而Prim算法則是通過每次增加一條邊來建立一棵樹
Kruskal算法适用于稀疏圖，沒有使用堆優化的Prim算法适用于稠密圖，使用了堆優化Prim算法則适用于稀疏圖。
2.圖的割點與割邊
3.二分圖最大比對
第九章 還能更好嗎——微軟亞洲研究院面試