《啊哈！算法》是一本充滿智慧和趣味的算法入門書。沒有枯燥的描述，沒有難懂的公式，一切以實際應用為出發點，通過幽默的語言配以可愛的插圖來講解算法。你更像是在閱讀一個個輕松的小故事或是在玩一把趣味解謎游戲，在輕松愉悅中便掌握算法精髓，感受算法之美。
《啊哈！算法》中涉及的數據結構有棧、隊列、鏈表、樹、并查集、堆和圖等；涉及的算法有排序、枚舉、深度和廣度優先搜索、圖的遍歷，當然還有圖論中不可以缺少的四種最短路徑算法、兩種最小生成樹算法、割點與割邊算法、二分圖的最大匹配算法等。
啊哈！去中科院玩單片機
呦吼！在微軟亞洲研究院寫爬蟲
噠噠！寫一本開開心心的算法書
你一定能看懂的算法書！
作為本書的策劃編輯，我很榮幸。
《啊哈！算法》是我讀過的有趣且是我唯一能看懂的一本算法書。
我最初是因為啊哈磊寫的另外一本書《啊哈！C》而認識啊哈磊的。啊哈磊還有個網站，也叫啊哈磊，這個啊哈磊網站中有個論壇，叫啊哈論壇。論壇建立短短一年半時間，就聚集了15000多個啊哈小伙伴，都是萌物。我對他的寫作風格很欣賞，那是一種因熱愛和探究而產生的純粹的快樂，因此，當啊哈磊率領著他的一大波萌物開開心心地攻城略地，浩浩蕩蕩地兵臨城下，跟我說他想寫一本通俗易懂的算法書，不知是否能出版時，我的回答是：“必須出版！”
這本書出版意向的達成就是這么簡單。
但創作的過程一點不輕松。因為任何一本拿得出手的書的創作都是作者大量時間和精力付出的結果。是毅力的累積。
幾個月之后，我拿到了這本書的初稿。我高高興興地開始讀。這部分寫得通俗易懂，我看得津津有味。但讀了一些之后，我發現我高興不起來了，我遇到了困難，有些篇章寫得太簡略了，只是把算法的基本思路說了一下，然后就直接給出了以該算法實現的某個示例的完整代碼。
這樣不行，看不懂啊。原理很簡單，但實現起來時，看代碼就感覺對應不起來了。或許比我聰明的人能看懂，但我希望像我這種在算法方面毫無造詣的普通選手讀起來也不吃力，于是我讓啊哈磊完善它。我是這么交代的——你得寫得讓我能看懂才行。這要求非常的簡單，但也非常的暗黑。
經過比我想象的要長的時間，啊哈磊給了我第二版。
我繼續閱讀，很多之前看不懂的地方現在能看懂了，或者至少我認為我看懂了（請允許我使用這種讓人生氣的措辭），但還有少部分欠點勁兒。啊哈磊向我投來困惑又略帶鄙視的目光，我用堅定又癡癡呆呆的目光把他的目光給頂了回去。
于是啊哈磊繼續埋頭苦干。
終于，我完全可以看懂的版本誕生了。
對于一本技術書，一個編輯可能犯下的最有價值的“錯誤”就是試圖去完全讀懂它。
在最后，我還要特別強調一點，這本書不僅寫得通俗易懂，而且還在一個非常重要的方方面超越了其他技術書，那就是這本書中還配了可愛的漫畫，萌萌的畫風，生動的場景，與文字渾然一體。
我想寫一本通俗易懂的算法書很久了，因為對于多數人而言，“算法”給他的第一印象就是很難懂，其實我也是這樣。還記得我第一次學習圖論的“割點割邊”算法時，看過不下于四五本書，其中不乏一些算法經典書籍，還百度了一堆材料，才勉強將其看懂并實現成代碼。其實這個算法并不難，核心代碼不超過20行，但是很多算法書都是草草敘述，不同的書籍給出的參考代碼也是五花八門，有的甚至都不稀罕給你代碼，這大大增加了學習的難度。我是花了整整一個晚上才搞定的，當然這其中不排除智商因素。第二印象就是算法是枯燥無趣的，并且好像沒什么作用。其實在我們的日常生活之中到處都可見到算法的影子，只不過它通常隱匿在事物的背后，不太容易被發現。但是它每天都在默默地為我們服務著。在本書中我將帶你一步步揭開算法的奧秘，帶它走近你的身邊。
由于算法的內容確實是太多了，要想全部寫清楚恐怕幾本書都不夠，本書將介紹一些最常用的算法。此外算法的實現通常需要依附一些數據結構，因此在必要的時候對于需要用到的數據結構我也會進行講解。本書中涉及的數據結構有棧、隊列、樹、并查集、堆和圖等；算法有各種排序、枚舉、深度和廣度優先搜索、圖上的遍歷，當然還有圖論中不可以缺少的四種最短路徑算法、兩種最小生成樹算法、割點與割邊算法、二分圖的最大匹配算法等。
盡管我不敢保證我寫的算法你一定可以看懂（但憑著一股強大的自信，我認為初中以上文化程度的應該沒問題^_^），但我會以一個故事或者一個你在生活中可能遇到的問題開始對一個算法進行講解，并盡量用通俗易懂的語言配合有趣的插圖讓你在閱讀本書的時候更像是在品讀一篇篇輕松的短篇小說或是在玩一把趣味解謎游戲，在輕松愉悅中掌握算法精髓，感受算法之美。
致 謝
本書能得以面世，首先要感謝圖靈的陳冰先生。感謝你主動聯系我，給予我信心去完成本書的全部，并且提出了很多寶貴的建議。更加令我吃驚的是你竟然能讀懂本書的全部算法（包括每一行代碼），還發現了很多隱藏得很深的錯誤，真是一位非常棒的圖書出版人。
在書稿創作的過程中，有幸和很多優秀的學生共同學習和探討，是他們為本書的創作提供了靈感，感謝他們的傾聽、交流和建議。他們是武漢二中的呂凱風同學、武漢外國語學校的李嘉浩、熊子健、陳雨禾、郭明達和李丁等同學。
本書之所以變得這么有趣，還必須要感謝我的美女插畫師鄭佳茜，你靈感涌現的插圖功不可沒。
感謝我的好友張知嚴，無私地幫助我搭建了“添柴”編程在線學習系統（tianchai.org），為本書讀者提供了更好的學習交流平臺。
感謝我的學生胡夢清，感謝你排除萬難來參加你人生中的最后一場NOIP競賽。是你用行動、青春路上追求夢想的精神，告訴我們18歲就應該可愛、執著、不畏懼，敢于朝著夢想前行。
特別感謝我的未婚妻Snowin，是你放棄了近一年來所有的周末和節假日，陪我在書桌旁、咖啡廳里、旅途中……共同完成了本書的每一個字、每一幅圖、每一段代碼。
最后要感謝我的父母，你們把我拉扯大太不容易了，我愛你們！
啊哈磊
2014年5月6日
紀磊，網名啊哈磊。
曾在中科院玩過單片機。武漢大學歷史上第一位以本科生身份加入MSRA（微軟亞洲研究院）的小伙伴，在機器學習組從事搜索引擎方面的研究。
發表國際會議論文一篇（IEEE）。
全國青少年信息學奧林匹克金牌教練。
超萌超簡潔的C語言編譯器——“啊哈C編譯器”作者。
2013年，我的第一部著作，有趣的編程科普書《啊哈C！》出版。
非常喜歡小朋友，每天都過得都非常開心。
至于為什么叫“啊哈磊”，因為我覺得這是一個很喜慶的名字。
第1章 一大波數正在靠近——排序 1
第1節 最快最簡單的排序——桶排序 2
第2節 鄰居好說話——冒泡排序 7
第3節 最常用的排序——快速排序 12
第4節 小哼買書 20
第2章 棧、隊列、鏈表 25
第1節 解密QQ號——隊列 26
第2節 解密回文——棧 32
第3節 紙牌游戲——小貓釣魚 35
第4節 鏈表 44
第5節 模擬鏈表 54
第3章 枚舉！很暴力 57
第1節 坑爹的奧數 58
第2節 炸彈人 61
第3節 火柴棍等式 67
第4節 數的全排列 70
第4章 萬能的搜索 72
第1節 不撞南墻不回頭——深度優先搜索 73
第2節 解救小哈 81
第3節 層層遞進——廣度優先搜索 88
第4節 再解炸彈人 95
第5節 寶島探險 106
第6節 水管工游戲 117
第5章 圖的遍歷 128
第1節 深度和廣度優先究竟是指啥 129
第2節 城市地圖——圖的深度優先遍歷 136
第3節 最少轉機——圖的廣度優先遍歷 142
第6章 最短路徑 147
第1節 只有五行的算法——Floyd-Warshall 148
第2節 Dijkstra算法——通過邊實現松弛 155
第3節 Bellman-Ford——解決負權邊 163
第4節 Bellman-Ford的隊列優化 171
第5節 最短路徑算法對比分析 177
第7章 神奇的樹 178
第1節 開啟“樹”之旅 179
第2節 二叉樹 183
第3節 堆——神奇的優先隊列 185
第4節 擒賊先擒王——并查集 200
第8章 更多精彩算法 211
第1節 鏢局運鏢——圖的最小生成樹 212
第2節 再談最小生成樹 219
第3節 重要城市——圖的割點 229
第4節 關鍵道路——圖的割邊 234
第5節 我要做月老——二分圖最大匹配 237
第9章 還能更好嗎——微軟亞洲研究院面試 243
第1節 最快最簡單的排序——桶排序
在我們生活的這個世界中到處都是被排序過的東東。站隊的時候會按照身高排序，考試的名次需要按照分數排序，網上購物的時候會按照價格排序，電子郵箱中的郵件按照時間排序……總之很多東東都需要排序，可以說排序是無處不在。現在我們舉個具體的例子來介紹一下排序算法。
首先出場的是我們的主人公小哼，上面這個可愛的娃就是啦。期末考試完了老師要將同學們的分數按照從高到低排序。小哼的班上只有5個同學，這5個同學分別考了5分、3分、5分、2分和8分，哎，考得真是慘不忍睹（滿分是10分）。接下來將分數進行從大到小排序，排序后是8 5 5 3 2。你有沒有什么好方法編寫一段程序，讓計算機隨機讀入5個數然后將這5個數從大到小輸出？請先想一想，至少想15分鐘再往下看吧（*^__^*）。
我們這里只需借助一個一維數組就可以解決這個問題。請確定你真的仔細想過再往下看哦。
首先我們需要申請一個大小為11的數組int a[11]。OK，現在你已經有了11個變量，編號從a[0]~a[10]。剛開始的時候，我們將a[0]~a[10]都初始化為0，表示這些分數還都沒有人得過。例如a[0]等于0就表示目前還沒有人得過0分，同理a[1]等于0就表示目前還沒有人得過1分……a[10]等于0就表示目前還沒有人得過10分。
下面開始處理每一個人的分數，第一個人的分數是5分，我們就將相對應的a[5]的值在原來的基礎增加1，即將a[5]的值從0改為1，表示5分出現過了一次。
第二個人的分數是3分，我們就把相對應的a[3]的值在原來的基礎上增加1，即將a[3]的值從0改為1，表示3分出現過了一次。
注意啦！第三個人的分數也是5分，所以a[5]的值需要在此基礎上再增加1，即將a[5]的值從1改為2，表示5分出現過了兩次。
按照剛才的方法處理第四個和第五個人的分數。最終結果就是下面這個圖啦。
你發現沒有，a[0]~a[10]中的數值其實就是0分到10分每個分數出現的次數。接下來，我們只需要將出現過的分數打印出來就可以了，出現幾次就打印幾次，具體如下。
a[0]為0，表示“0”沒有出現過，不打印。
a[1]為0，表示“1”沒有出現過，不打印。
a[2]為1，表示“2”出現過1次，打印2。
a[3]為1，表示“3”出現過1次，打印3。
a[4]為0，表示“4”沒有出現過，不打印。
a[5]為2，表示“5”出現過2次，打印5 5。
a[6]為0，表示“6”沒有出現過，不打印。
a[7]為0，表示“7”沒有出現過，不打印。
a[8]為1，表示“8”出現過1次，打印8。
a[9]為0，表示“9”沒有出現過，不打印。
a[10]為0，表示“10”沒有出現過，不打印。
最終屏幕輸出“2 3 5 5 8”，完整的代碼如下。
#include
int main()
{
int a[11],i,j,t;
for(i=0;i<=10;i++)
a[i]=0; //初始化為0
for(i=1;i<=5;i++) //循環讀入5個數
{
scanf("%d",&t); //把每一個數讀到變量t中
a[t]++; //進行計數
}
for(i=0;i<=10;i++) //依次判斷a[0]~a[10]
for(j=1;j<=a[i];j++) //出現了幾次就打印幾次
printf("%d ",i);
getchar();getchar();
//這里的getchar();用來暫停程序，以便查看程序輸出的內容
//也可以用system("pause");等來代替
return 0;
}
輸入數據為：
5 3 5 2 8
仔細觀察的同學會發現，剛才實現的是從小到大排序。但是我們要求是從大到小排序，這該怎么辦呢？還是先自己想一想再往下看哦。
其實很簡單。只需要將for(i=0;i<=10;i++)改為for(i=10;i>=0;i--)就OK啦，快去試一試吧。
這種排序方法我們暫且叫它“桶排序”。因為其實真正的桶排序要比這個復雜一些，以后再詳細討論，目前此算法已經能夠滿足我們的需求了。
這個算法就好比有11個桶，編號從0~10。每出現一個數，就在對應編號的桶中放一個小旗子，最后只要數數每個桶中有幾個小旗子就OK了。例如2號桶中有1個小旗子，表示2出現了一次；3號桶中有1個小旗子，表示3出現了一次；5號桶中有2個小旗子，表示5出現了兩次；8號桶中有1個小旗子，表示8出現了一次。
現在你可以嘗試一下輸入n個0~1000之間的整數，將它們從大到小排序。提醒一下，如果需要對數據范圍在0~1000的整數進行排序，我們需要1001個桶，來表示0~1000之間每一個數出現的次數，這一點一定要注意。另外，此處的每一個桶的作用其實就是“標記”每個數出現的次數，因此我喜歡將之前的數組a換個更貼切的名字book（book這個單詞有記錄、標記的意思），代碼實現如下。
#include
int main()
{
int book[1001],i,j,t,n;
for(i=0;i<=1000;i++)
book[i]=0;
scanf("%d",&n);//輸入一個數n，表示接下來有n個數
for(i=1;i<=n;i++)//循環讀入n個數，并進行桶排序
{
scanf("%d",&t); //把每一個數讀到變量t中
book[t]++; //進行計數，對編號為t的桶放一個小旗子
}
for(i=1000;i>=0;i--) //依次判斷編號1000~0的桶
for(j=1;j<=book[i];j++) //出現了幾次就將桶的編號打印幾次
printf("%d ",i);
getchar();getchar();
return 0;
}
可以輸入以下數據進行驗證。
10
8 100 50 22 15 6 1 1000 999 0
運行結果是：
1000 999 100 50 22 15 8 6 1 0
最后來說下時間復雜度的問題。代碼中第6行的循環一共循環了m次（m為桶的個數），第9行的代碼循環了n次（n為待排序數的個數），第14行和第15行一共循環了m+n次。所以整個排序算法一共執行了m+n+m+n次。我們用大寫字母O來表示時間復雜度，因此該算法的時間復雜度是O(m+n+m+n)即O(2*(m+n))。我們在說時間復雜度的時候可以忽略較小的常數，最終桶排序的時間復雜度為O(m+n)。還有一點，在表示時間復雜度的時候，n和m通常用大寫字母即O(M+N)。
這是一個非常快的排序算法。桶排序從1956年就開始被使用，該算法的基本思想是由E.J. Issac和R.C. Singleton提出來的。之前我說過，其實這并不是真正的桶排序算法，真正的桶排序算法要比這個更加復雜。但是考慮到此處是算法講解的第一篇，我想還是越簡單易懂越好，真正的桶排序留在以后再聊吧。需要說明一點的是：我們目前學習的簡化版桶排序算法，其本質上還不能算是一個真正意義上的排序算法。為什么呢？例如遇到下面這個例子就沒轍了。
現在分別有5個人的名字和分數：huhu 5分、haha 3分、xixi 5分、hengheng 2分和gaoshou 8分。請按照分數從高到低，輸出他們的名字。即應該輸出gaoshou、huhu、xixi、haha、hengheng。發現問題了沒有？如果使用我們剛才簡化版的桶排序算法僅僅是把分數進行了排序。最終輸出的也僅僅是分數，但沒有對人本身進行排序。也就是說，我們現在并不知道排序后的分數原本對應著哪一個人！這該怎么辦呢？不要著急，請看下節——冒泡排序。
……
新書資訊