漫畫算法2：小灰的算法進階

魏夢舒（@程序員小灰）：微信公眾號“程序員小灰”的作者，多年軟件行業從業經驗，先後在京東金融和摩拜科技從事研發工作，對算法有一定的興趣和經驗。

第1章排序算法進階/ 1
1.1 新的開始/ 1
1.2 什麼是選擇排序/ 3
1.2.1 如何減少比較次數/ 3
1.2.2 選擇排序的實現/ 8
1.3 什麼是插入排序/ 10
1.3.1 撲克牌中的排序算法/ 10
1.3.2 插入排序的優化/ 14
1.4 什麼是希爾排序/ 16
1.4.1 插入排序的升級/ 16
1.4.2 希爾排序的優化/ 20
1.5 什麼是歸併排序/ 22
1.5.1 擂台上的排序算法/ 22
1.5.2 歸併排序的具體操作/ 25
1.6 什麼是基數排序/ 29
1.6.1 另一種線性排序算法/ 29
1.6.2 解決對齊問題/ 33
1.7 小結/ 35

第2章樹的進階/ 37
2.1 什麼是二叉查找樹/ 37
2.1.1 二叉樹查找樹的特性/ 37
2.1.2 二叉查找樹的插入和刪除/ 40
2.1.3 二叉查找樹的缺陷/ 45
2.2 什麼是平衡二叉樹/ 47
2.2.1 平衡因子和旋轉/ 47
2.2.2 平衡二叉樹的插入和刪除/ 53
2.3 什麼是紅黑樹/ 58
2.3.1 另一種自平衡方式/ 58
2.3.2 紅黑樹的插入/ 62
2.3.3 紅黑樹的刪除/ 68
2.3.4 紅黑樹的實踐和應用場景/ 76
2.4 什麼是B樹和B+樹/ 79
2.4.1 數據庫的索引/ 79
2.4.2 什麼是B樹/ 81
2.4.3 什麼是B+樹/ 88
2.5 小結/ 90

第3章圖/ 91
3.1 什麼是圖/ 91
3.1.1 圖的基本概念/ 91
3.1.2 圖的存儲方式/ 95
3.2 圖的遍歷/ 97
3.2.1 深度優先和廣度優先/ 97
3.2.2 遍歷的具體實現/ 101
3.3 圖的最短路徑/ 107
3.3.1 什麼是迪傑斯特拉算法/ 107
3.3.2 迪傑斯特拉算法的原理/ 111
3.3.3 如何得到完整路徑/ 116
3.4 圖的多源最短路徑/ 125
3.5 小結/ 132

第4章查找算法/ 133
4.1 引言/ 133
4.2 什麼是二分查找/ 135
4.2.1 一個特殊的遊戲/ 135
4.2.2 二分查找的原理/ 138
4.3 什麼是跳表/ 141
4.3.1 鍊錶能做二分查找嗎/ 141
4.3.2 跳表的插入與刪除/ 146
4.4 什麼是字符串匹配算法/ 155
4.4.1 樸素的字符串匹配/ 155
4.4.2 樸素字符串匹配的改進/ 158
4.5 什麼是KMP算法/ 164
4.5.1 無謂的字符比較/ 164
4.5.2 KMP算法的原理/ 166
4.6 小結/ 176

第5章面試中的算法/ 177
5.1 躊躇滿志的小灰/ 177
5.2 如何螺旋遍歷二維數組/ 179
5.2.1 第一次交鋒/ 179
5.2.2 解題思路/ 181
5.3 兩數之和與三數之和/ 187
5.3.1 再接再厲/ 187
5.3.2 解題思路/ 189
5.3.3 問題的擴展/ 194
5.4 數組中的第k個最大元素/ 201
5.4.1 一道數組相關的題目/ 201
5.4.2 解題思路/ 204
5.5 鍊錶的倒數第k個節點/ 210
5.5.1 一道鍊錶相關的題目/ 210
5.5.2 解題思路/ 212
5.6 千變萬化的股票交易問題/ 216
5.6.1 如何獲得最大收益/ 216
5.6.2 解題思路/ 218
5.6.3 題目變形：買賣次數不限/ 220
5.6.4 題目再變形：2次買賣/ 221
5.6.5 最後的勝利/ 233
5.7 結束也是開始/ 235