本書是《漫畫算法：小灰的算法之旅》的續(xù)作，通過主人公小灰的心路歷程，用漫畫的形式講述了多個(gè)數(shù)據(jù)結(jié)構(gòu)、算法及復(fù)雜多變的算法面試題目。 第1章介紹了幾種典型的排序算法，包括選擇排序、插入排序、希爾排序、歸并排序、基數(shù)排序。 第2章介紹了"樹”結(jié)構(gòu)的高級應(yīng)用，包括二叉查找樹、AVL樹、紅黑樹、B樹和B+樹。 第3章介紹了"圖”結(jié)構(gòu)的概念，以及深度優(yōu)先遍歷、廣度遍歷、單源最短路徑、多源最短路徑算法。 第4章介紹了"查找”相關(guān)的算法和數(shù)據(jù)結(jié)構(gòu)，包括二分查找算法、RK算法，KMP算法，以及"跳表”這種用于高效查找的數(shù)據(jù)結(jié)構(gòu)。 第5章介紹了多種職場上流行的算法面試題目及詳細(xì)的解題思路。例如螺旋遍歷二維數(shù)組、尋找數(shù)組中第k大元素、求股票交易的最大收益等等。
微信公眾號程序員小灰的作者，多年的軟件行業(yè)從業(yè)經(jīng)驗(yàn)，先后在京東金融和摩拜科技從事算法和研發(fā)相關(guān)工作，對算法有著深入的研究。
第1章 排序算法進(jìn)階 / 1
1.1 新的開始 / 1
1.2 什么是選擇排序 / 3
1.2.1 如何減少比較次數(shù) / 3
1.2.2 選擇排序的實(shí)現(xiàn) / 8
1.3 什么是插入排序 / 10
1.3.1 撲克牌中的排序算法 / 10
1.3.2 插入排序的優(yōu)化 / 14
1.4 什么是希爾排序 / 16
1.4.1 插入排序的升級 / 16
1.4.2 希爾排序的優(yōu)化 / 20
1.5 什么是歸并排序 / 22
1.5.1 擂臺(tái)上的排序算法 / 22
1.5.2 歸并排序的具體操作 / 25
1.6 什么是基數(shù)排序 / 29
1.6.1 另一種線性排序算法 / 29
1.6.2 解決對齊問題 / 33
1.7 小結(jié) / 35
第2章 樹的進(jìn)階 / 37
2.1 什么是二叉查找樹 / 37
2.1.1 二叉樹查找樹的特性 / 37
2.1.2 二叉查找樹的插入和刪除 / 40
2.1.3 二叉查找樹的缺陷 / 45
2.2 什么是平衡二叉樹 / 47
2.2.1 平衡因子和旋轉(zhuǎn) / 47
2.2.2 平衡二叉樹的插入和刪除 / 53
2.3 什么是紅黑樹 / 58
2.3.1 另一種自平衡方式 / 58
2.3.2 紅黑樹的插入 / 62
2.3.3 紅黑樹的刪除 / 68
2.3.4 紅黑樹的實(shí)踐和應(yīng)用場景 / 76
2.4 什么是B樹和B+樹 / 79
2.4.1 數(shù)據(jù)庫的索引 / 79
2.4.2 什么是B樹 / 81
2.4.3 什么是B+樹 / 88
2.5 小結(jié) / 90
第3章 圖 / 91
3.1 什么是圖 / 91
3.1.1 圖的基本概念 / 91
3.1.2 圖的存儲(chǔ)方式 / 95
3.2 圖的遍歷 / 97
3.2.1 深度優(yōu)先和廣度優(yōu)先 / 97
3.2.2 遍歷的具體實(shí)現(xiàn) / 101
3.3 圖的最短路徑 / 107
3.3.1 什么是迪杰斯特拉算法 / 107
3.3.2 迪杰斯特拉算法的原理 / 111
3.3.3 如何得到完整路徑 / 116
3.4 圖的多源最短路徑 / 125
3.5 小結(jié) / 132
第4章 查找算法 / 133
4.1 引言 / 133
4.2 什么是二分查找 / 135
4.2.1 一個(gè)特殊的游戲 / 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 樸素字符串匹配的改進(jìn) / 158
4.5 什么是KMP算法 / 164
4.5.1 無謂的字符比較 / 164
4.5.2 KMP算法的原理 / 166
4.6 小結(jié) / 176
第5章 面試中的算法 / 177
5.1 躊躇滿志的小灰 / 177
5.2 如何螺旋遍歷二維數(shù)組 / 179
5.2.1 第一次交鋒 / 179
5.2.2 解題思路 / 181
5.3 兩數(shù)之和與三數(shù)之和 / 187
5.3.1 再接再厲 / 187
5.3.2 解題思路 / 189
5.3.3 問題的擴(kuò)展 / 194
5.4 數(shù)組中的第k個(gè)最大元素 / 201
5.4.1 一道數(shù)組相關(guān)的題目 / 201
5.4.2 解題思路 / 204
5.5 鏈表的倒數(shù)第k個(gè)節(jié)點(diǎn) / 210
5.5.1 一道鏈表相關(guān)的題目 / 210
5.5.2 解題思路 / 212
5.6 千變?nèi)f化的股票交易問題 / 216
5.6.1 如何獲得最大收益 / 216
5.6.2 解題思路 / 218
5.6.3 題目變形：買賣次數(shù)不限 / 220
5.6.4 題目再變形：2次買賣 / 221
5.6.5 最后的勝利 / 233
5.7 結(jié)束也是開始 / 235
書單推薦
