轻松学算法

本书共分为12个章节，首先介绍了一些基础的数据结构，以及常用的排序算法和查找算法；其次介绍了两个稍微复杂一些的数据结构――树和图，还介绍了每种数据结构和算法的适用场景，之后是一些在工作与面试中的实际应用，以字符串、数组、查找等为例介绍了一些常见的互联网面试题及分析思路，便于读者了解这些思路，顺利地通过互联网公司的面试；很后介绍了一些常见的算法思想，便于读者对今后遇到的算法问题更轻易地想出解决方案。本书的讲解轻松有趣，易于读者把烦琐、枯燥的算法学习变为有趣、愉快的学习，把被动学习变为主动学习。本书也介绍了一些会在工作面试中用到的算法。对于一些正在学习算法的人来说，本书保证是可以帮你轻松掌握算法的辅助资料；对于已经了解算法的人来说，可以从本书中了解到这些算法是如何在实际工作中使用的。本书适合即将毕业的学生、初入职场的工程师及想补充基础算法知识的人学习，也适合作为一本互联网公司面试的参考书，更是一本的便于读者时常补习算法知识的收藏宝典。

赵烨，Java不错研发工程师，现就职于优酷土豆的来疯直播团队，主要关注高并发、高可用、系统性能优化等内容。乐于学习、乐于分享。

第1章数组、集合和散列表1
1.1要用就要提前想好的数据结构―数组2
1.1.1什么是数组2
1.1.2数组的存储结构3
1.1.3数组的特点6
1.1.4数组的适用场景7
1.2升级版数组―集合8
1.2.1什么是集合8
1.2.2集合的实现8
1.2.3集合的特点13
1.2.4集合的适用场景13
1.2.5数组与变长数组的性能14
1.3数组的其他应用―散列表14
1.3.1什么是散列表15
1.3.2对散列表函数产生冲突的解决办法16
1.3.3散列表的存储结构17
1.3.4散列表的特点18
1.3.5散列表的适用场景20
1.3.6散列表的性能分析21
1.4小结28
第2章栈、队列、链表29
2.1汉诺塔游戏―栈30
2.1.1什么是汉诺塔30
2.1.2什么是栈31
2.1.3栈的存储结构31
2.1.4栈的特点36
2.1.5栈的适用场景36
2.2火爆的奶茶店―队列37
2.2.1什么是队列37
2.2.2队列的存储结构38
2.2.3队列的特点43
2.2.4队列的适用场景44
2.3用栈实现队列45
2.3.1用两个栈实现队列46
2.3.2两个队列实现栈50
2.4链表53
2.4.1什么是链表54
2.4.2链表的存储结构54
2.4.3链表的操作55
2.4.4链表的特点66
2.4.5链表的适用场景66
2.4.6链表的性能分析67
2.4.7面试举例：如何反转链表68
2.5链表其实也可以用数组模拟69
2.5.1静态链表70
2.5.2静态链表的实现70
2.5.3静态链表的特点80
2.6再谈汉诺塔81
2.6.1汉诺塔的移动原理81
2.6.2汉诺塔的递归实现82
第3章排序算法84
3.1算法基础85
3.1.1时间复杂度85
3.1.2空间复杂度88
3.1.3稳定性88
3.2快而简单的排序―桶排序89
3.2.1举个例子89
3.2.2什么是桶排序90
3.2.3桶排序的实现90
3.2.4桶排序的性能及特点92
3.2.5桶排序的适用场景93
3.3咕嘟咕嘟的冒泡排序94
3.3.1什么是冒泡排序94
3.3.2冒泡排序的原理94
3.3.3冒泡排序的实现96
3.3.4冒泡排序的特点及性能99
3.3.5冒泡排序的适用场景99
3.3.6冒泡排序的改进方案100
3.4最常用的快速排序100
3.4.1什么是快速排序101
3.4.2快速排序的原理101
3.4.3快速排序的实现105
3.4.4快速排序的特点及性能107
3.4.5快速排序的适用场景108
3.4.6快速排序的优化108
3.5简单的插入排序109
3.5.1什么是插入排序110
3.5.2插入排序的原理110
3.5.3插入排序的实现112
3.5.4插入排序的特点及性能114
3.5.5插入排序的适用场景115
3.6直接插入的改进―希尔排序115
3.6.1什么是希尔排序116
3.6.2希尔排序的原理116
3.6.3希尔排序的实现118
3.6.4希尔排序的特点及性能120
3.6.5希尔排序的适用场景121
3.7简单选择排序121
3.7.1什么是选择排序122
3.7.2简单选择排序的原理122
3.7.3简单选择排序的实现123
3.7.4选择排序的特点及性能125
3.7.5简单选择排序的优化125
3.7.6选择排序的适用场景126
3.8小结126
第4章搜索，没那么难128
4.1最先想到的―顺序查找129
4.1.1最先想到的129
4.1.2顺序查找的原理与实现129
4.1.3顺序查找的特点及性能分析131
4.1.4顺序查找的适用场景132
4.2能不能少查点―二分查找133
4.2.1某些特殊情况的查找需求133
4.2.2二分查找的原理及实现133
4.2.3二分查找的优化137
4.2.4二分查找的特点及性能分析138
4.2.5二分查找的适用场景139
4.2.6我是来还债的―之前欠的二分插入排序139
4.3行列递增的矩阵查找―二分查找思维拓展141
4.3.1一道题142
4.3.2几个解法142
4.3.3其他拓展153
4.4分块查找154
4.4.1每次插入元素都要有序吗154
4.4.2什么是分块查找155
4.4.3分块查找的原理及实现155
4.4.4分块查找的特点与性能分析159
4.4.5分块查找的适用场景160
4.5查找算法小结161
4.6搜索引擎与倒排索引162
4.6.1什么是搜索引擎162
4.6.2倒排索引162
4.6.3索引实例163
4.6.4倒排索引的关键字提取164
4.6.5商业索引的其他拓展164
第5章树166
5.1树的定义及存储结构167
5.1.1什么是树167
5.1.2其他相关术语168
5.1.3都有哪些树170
5.1.4树的存储结构及实现170
5.2二叉树173
5.2.1什么是二叉树173
5.2.2还有两种特殊的二叉树173
5.2.3二叉树的实现175
5.2.4二叉树的遍历185
5.2.5完全二叉树187
5.3二叉树的查找算法188
5.3.1二叉查找树188
5.3.2平衡二叉树198
5.4B-树、B+树202
5.4.1什么是B-树203
5.4.2什么是B+树204
5.4.3B-树、B+树的特点及性能分析205
5.5在MySQL数据库中是如何应用B+树的206
5.6哈夫曼树209
5.6.1几个术语209
5.6.2什么是哈夫曼树209
5.6.3哈夫曼树的构造211
5.6.4哈夫曼编码及解码213
5.7堆215
5.7.1什么是堆215
5.7.2堆的基本操作216
5.7.3堆的性能分析221
5.7.4堆排序222
5.8红黑树224
5.8.1什么是红黑树224
5.8.2红黑树的特点与优势224
第6章图226
6.1图的定义及相关术语227
6.1.1什么是图227
6.1.2图的分类227
6.1.3图的相关术语228
6.2图的表示与存储方式229
6.2.1邻接矩阵229
6.2.2邻接表234
6.3更多的图237
6.3.1连通图238
6.3.2强连通图238
6.4深度优先遍历与广度优先遍历238
6.4.1深度优先遍历239
6.4.2广度优先遍历248
6.4.3两种遍历方法的对比253
6.5最短路径254
6.5.1带权图254
6.5.2Dijkstra算法255
6.5.3Floyd算法269
第7章字符串272
7.1字符及字符串简介273
7.1.1什么是字符273
7.1.2什么是字符串273
7.2字符的全排列275
7.2.1问题描述及分析275
7.2.2最先想到的275
7.2.3利用字典序排列278
7.3反转字符串283
7.3.1问题描述及分析283
7.3.2最先想到的283
7.3.3对换反转法285
7.3.4拓展―旋转字符串287
7.4判断回文288
7.4.1问题描述及分析288
7.4.2对半判断289
7.5寻找最大的回文子串290
7.5.1问题描述及分析290
7.5.2遍历实现291
7.6将字符串转换为数字293
7.6.1问题描述及分析293
7.6.2解决293
7.7判断字符串包含的问题297
7.7.1问题描述及分析297
7.7.2非常简单的解决思路297
7.7.3利用排序进行优化299
7.7.4投机取巧的素数方案302
7.7.5用散列表进行实现304
7.7.6用位运算进行实现305
第8章数组还有好多玩法308
8.1从数组中找出其和为指定值的两个数309
8.1.1问题描述及分析309
8.1.2最简单的办法309
8.1.3一切为了速度310
8.1.4排序总是好的选择311
8.1.5还能更好313
8.2找出连加值最大的子数组315
8.2.1问题描述及分析315
8.2.2暴力穷举法316
8.2.3动态规划法319
8.2.4问题拓展321
8.3数组正负值排序323
8.3.1问题描述及分析323
8.3.2最直观的解法324
8.3.3借鉴简单插入排序325
8.3.4借鉴快速排序327
8.3.5拓展329
8.4将数组随机打乱顺序329
8.4.1问题描述及分析329
8.4.2随便糊弄一下330
8.4.3插入排序的思想又来了331
8.5数组赋值333
8.5.1问题描述及分析333
8.5.2分解计算333
8.6寻找旋转数组的拐点335
8.6.1问题描述及分析335
8.6.2最简单的方法336
8.6.3利用“有序”337
8.7荷兰国旗问题339
8.7.1问题描述及分析339
8.7.2排序法340
8.7.3快速排序带给人的灵感340
第9章查找又来了344
9.1出现次数超过一半的数字345
9.1.1问题描述及分析345
9.1.2排序法345
9.1.3散列表347
9.1.4删除法349
9.1.5更优的解法349
9.2寻找缺少的数字352
9.2.1问题描述及分析352
9.2.2借助快速排序352
9.2.3借助散列表实现354
9.2.4投机取巧法355
9.2.5思路拓展357
9.3在10亿个数中找出最大的1万个数357
9.3.1问题描述及分析357
9.3.2拍脑袋想问题358
9.3.3借助快速排序358
9.3.4不想都放入内存358
9.3.5传说中的大顶堆359
9.3.6拓展―找出数组中第k大的数359
第10章更多363
10.1不使用额外的空间交换两个数364
10.1.1问题描述364
10.1.2分析问题364
10.1.3解决问题364
10.2拿乒乓球的问题365
10.2.1问题描述365
10.2.2分析问题365
10.2.3解决问题365
第11章实现一些集合类367
11.1栈（Stack）的实现368
11.1.1实现前的思考368
11.1.2实现栈368
11.1.3参考JDK的实现372
11.2变长数组（ArrayList）的实现372
11.2.1实现前的思考372
11.2.2实现变长数组373
11.2.3参考JDK的实现380
11.3散列表（HashMap）的实现381
11.3.1实现前的思考381
11.3.2实现散列表381
11.3.3参考JDK的实现389
第12章方向390
12.1算法的一些常用思想391
12.1.1分治法391
12.1.2动态规划391
12.1.3贪心算法391
12.1.4回溯法392
12.1.5分支限界法392
12.2新兴算法392
12.2.1加密算法392
12.2.2商业算法393
12.3其他算法393
12.3.1基数估计算法393
12.3.2蚁群算法394