店铺推荐
【作者】
\\\"程杰，一个被读者誉为很适合写IT技术书的家伙。
？？？ 著有 《大话设计模式》（简体版销量破25万册、繁体版印刷12次，开创了一种适合国人阅读的趣味讲解IT知识的风格与模式）。
？？？ 作者参与过政府、证券、游戏、交通等多种行业的软件开发及项目管理工作，也曾做过软件培训的教师，目前从事教育类APP/微信小程序的开发与运营。因为有过两年半高中数学教学的独特经历，使得其书作当中处处以初学者视角考虑和分析问题，成为了当前很受欢迎的IT技术图书作者之一。\\\"
【内容】
本书以一个计算机教师的教学过程为场景，讲解数据结构和相关算法的知识。
全书以趣味方式来叙述，大量引用各种各样的生活知识来类比，并充分运用全彩色图形语言来解读抽象内容，对数据结构所涉及的一些经典算法做出逐行分析、多算法比较。与同类图书相比，本书内容有趣易读，算法讲解细致深入，是一本 适合自学的读物。对于学习数据结构来说，难点之一是对相关算法的理解。本书创新性地采用全彩印刷，图表、流程、代码等内容结合色彩来重新进行约定和归纳，使得对一些难以理解的知识点的解析 加清晰顺畅，极大提升了阅读体验。
本书主要内容包含：数据结构介绍、算法推导大O阶的方法；顺序结构与链式结构差异、栈与队列的应用；串的朴素模式匹配、KMP模式匹配算法；二叉树前中后序遍历、哈夫曼树及应用；图的深度、广度遍历； 小生成树两种算法、 短路径两种算法；拓扑排序与关键路径算法；折半查找、插值查找、斐波那契查找等静态查找；稠密索引、分块索引、倒排索引等索引技术；二叉排序树、平衡二叉树等动态查找；B树、B+树技术，散列表技术；冒泡、选择、插入等简单排序；希尔、堆、归并、快速等改进排序。
本书适合学过一门编程语言的各类读者，包括在读的大中专计算机专业学生、想转行做开发的非专业人员、欲考计算机专业研究生的应届生或在职人员，以及工作后需要补学或温习数据结构和算法的程序员等。
全书以趣味方式来叙述，大量引用各种各样的生活知识来类比，并充分运用全彩色图形语言来解读抽象内容，对数据结构所涉及的一些经典算法做出逐行分析、多算法比较。与同类图书相比，本书内容有趣易读，算法讲解细致深入，是一本 适合自学的读物。对于学习数据结构来说，难点之一是对相关算法的理解。本书创新性地采用全彩印刷，图表、流程、代码等内容结合色彩来重新进行约定和归纳，使得对一些难以理解的知识点的解析 加清晰顺畅，极大提升了阅读体验。
本书主要内容包含：数据结构介绍、算法推导大O阶的方法；顺序结构与链式结构差异、栈与队列的应用；串的朴素模式匹配、KMP模式匹配算法；二叉树前中后序遍历、哈夫曼树及应用；图的深度、广度遍历； 小生成树两种算法、 短路径两种算法；拓扑排序与关键路径算法；折半查找、插值查找、斐波那契查找等静态查找；稠密索引、分块索引、倒排索引等索引技术；二叉排序树、平衡二叉树等动态查找；B树、B+树技术，散列表技术；冒泡、选择、插入等简单排序；希尔、堆、归并、快速等改进排序。
本书适合学过一门编程语言的各类读者，包括在读的大中专计算机专业学生、想转行做开发的非专业人员、欲考计算机专业研究生的应届生或在职人员，以及工作后需要补学或温习数据结构和算法的程序员等。
【目录】
目?录
第1章?数据结构绪论1
1.1 开场白2
如果你交给某人一个程序，你将折磨他一整天；如果你教某人如何编写程序，你将折磨他一辈子。
1.2 你数据结构怎么学的3
他完成开发并测试通过后，得意地提交了代码。项目经理看完代码后拍着桌子对他说：“你数据结构是怎么学的？”
1.3 数据结构起源4
1.4 基本概念和术语5
正所谓“巧妇难为无米之炊”，再强大的计算机，也要有“米”下锅才可以干活，否则就是一堆破铜烂铁。这个“米”就是数据。
1.4.1?数据5
1.4.2?数据元素6
1.4.3?数据项7
1.4.4?数据对象7
1.4.5?数据结构7
1.5 逻辑结构与物理结构8
1.5.1?逻辑结构8
1.5.2?物理结构9
1.6 数据类型11
大家都需要房子住，但显然没钱考虑大房子是没有意义的。于是商品房就出现了各种各样的户型，有几百平米的别墅，也有仅两平米的胶囊公寓……
1.6.1?数据类型定义11
1.6.2?抽象数据类型12
1.7 总结回顾13
1.8 结尾语14
终的结果一定是，你对着别人很牛地说“数据结构——就那么回事。”
第2章 算法15
2.1 开场白16
2.2 数据结构与算法的关系16
计算机界的前辈们，是一帮很牛很牛的人，他们使得很多看似没法解决或者很难解决的问题，处理得如此美妙和神奇。
2.3 两种算法的比较17
高斯在上小学的 ，老师要求每个学生都计算1+2+…+100的结果，谁先算出来谁先回家……
2.4 算法定义18
现实世界中的算法千变万化，没有通用算法可以解决所有问题。甚至一个小问题，某个解决此类问题很 的算法却未必就适合它。
2.5 算法的特性19
2.5.1?输入输出19
2.5.2?有穷性19
2.5.3?确定性20
2.5.4?可行性20
2.6 算法设计的要求20
求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有 大的差异，我们自然追求高效率和低存储的算法来解决问题。
2.6.1?正确性21
2.6.2?可读性21
2.6.3?健壮性21
2.6.4?时间效率高和存储量低22
2.7 算法效率的度量方法22
随着n值越来越大，它们在时间效率上的差异也就越来越大。好比有些人每天都在学习，而有些人，打打游戏、睡睡大觉，毕业后前者名企争着要，后者求职处处无门。
2.7.1?事后统计方法22
2.7.2?事前分析估算方法23
2.8 函数的渐近增长25
2.9 算法时间复杂度27
理解大O阶推导不算难，难的其实是对数列的一些相关运算，这考查的 多是数学知识和能力。
2.9.1?算法时间复杂度定义27
2.9.2?推导大O阶方法28
2.9.3?常数阶28
2.9.4?线性阶29
2.9.5?对数阶29
2.9.6?平方阶29
2.10 常见的时间复杂度31
有些时候，告诉你某些东西不可以去尝试，也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以招惹吧。
2.11 坏情况与平均情况32
2.12 算法空间复杂度33
事先建立一个有2050个元素的数组，然后把所有年份按下标数字对应，如果是闰年，此数组项的值就是1，如果不是就是0。这样，所谓的判断某一年是否是闰年就变成了查找这个数组的某一项的值是多少的问题。
2.13 总结回顾34
2.14 结尾语35
愚公移山固然可敬，但发明和推土机，可能 加实在和聪明。
第3章 线性表37
3.1 开场白38
门外家长都挤在大门口与门里的小孩子的井然有序，形成了鲜明对比。哎，有时大人的所作所为，其实还不如孩子。
3.2 线性表的定义39
有时我们想知道某个小朋友（比如麦兜）是否是班级的同学，老师会告诉我说，没有，麦兜是在春田花花幼儿园里。这种查找某个元素是否存在的操作很常用。
3.3 线性表的抽象数据类型41
3.4 线性表的顺序存储结构43
他每次一吃完早饭就冲着去了图书馆，挑一个好地儿，把他书包里的书，一本一本地按座位放好，长长一排，九个座硬是被他占了。
3.4.1?顺序存储定义43
3.4.2?顺序存储方式43
3.4.3?数据长度与线性表长度的区别44
3.4.4?地址计算方法45
3.5 顺序存储结构的插入与删除46
春运时去买火车票，大家都排着队好好的，这时来了一个美女：“可否让我排在你前面？”这可不得了，后面的人像蠕虫一样，全部都得退后一步。
3.5.1?获得元素操作46
3.5.2?插入操作46
3.5.3?删除操作47
3.5.4?线性表顺序存储结构的优缺点49
3.6 线性表的链式存储结构49
反正也是要让相邻元素间留有足够余地，那干脆所有元素都不要考虑相邻位置了，哪有空位就到哪里。而只是让每个元素知道它下一个元素的位置在哪里。
3.6.1?顺序存储结构不足的解决办法49
3.6.2?线性表链式存储结构定义50
3.6.3?头指针与头结点的异同52
3.6.4?线性表链式存储结构代码描述52
3.7 单链表的读取53
3.8 单链表的插入与删除54
本来是爸爸左手牵着妈 手、右手牵着宝宝的手在马路边散步。突然迎面走来一美女，爸爸失神般地望着，此情景被妈妈逮个正着，于是扯开父子俩，拉起宝宝的左手就快步朝前走去。
3.8.1?单链表的插入54
3.8.2?单链表的删除56
3.9 单链表的整表创建58
3.10 单链表的整表删除60
3.11 单链表结构与顺序存储结构的优缺点61
3.12 静态链表62
对于一些语言，如Basic、Fortran等早期的编程 语言，由于没有指针，这链表结构，按照前面我们的讲法，它就没法实现了。怎么办呢？
3.12.1?静态链表的插入操作64
3.12.2?静态链表的删除操作65
3.12.3?静态链表的优缺点67
3.13 循环链表67
这个轮回的思想很有意思。它强调了不管你今生是穷是富，如果持续行善积德，下辈子就会好过，反之就会遭到报应。
3.14 双向链表70
就像每个人的人生一样，欲收获就得付出代价。双向链表既然是比单链表多了如可以反向遍历查找等的数据结构，那么也就需要付出一些小的代价。
3.15 总结回顾72
3.16 结尾语73
如果你觉得上学读书是受罪，假设你可以活到80岁，其实你 多也就吃了20年苦。用人生四分之一的时间来换取其余时间的幸福生活，这点苦不算啥。
第4章 栈与队列75
4.1 开场白76
想想看，在你准备用的时候，突然这手明明有却打不出来，这不是要命吗。
4.2 栈的定义76
类似的很多软件，比如Word、Photoshop等，都有撤销（undo）的操作，也是用栈这种思想方式来实现的。
4.2.1?栈的定义76
4.2.2?进栈出栈变化形式78
4.3 栈的抽象数据类型78
4.4 栈的顺序存储结构及实现79
4.4.1?栈的顺序存储结构79
4.4.2?栈的顺序存储结构——进栈操作80
4.4.3?栈的顺序存储结构——出栈操作81
4.5 两栈共享空间81
两个大学室友毕业同时到北京工作，他们都希望租房时能找到独自住的一室或一室一厅，可找来找去发现，价格实在是承受不起。
4.6 栈的链式存储结构及实现83
4.6.1?栈的链式存储结构83
4.6.2?栈的链式存储结构——进栈操作84
4.6.3?栈的链式存储结构——出栈操作85
4.7 栈的作用85
4.8 栈的应用——递归86
当你往镜子前面一站，镜子里面就有一个你的图像。但你试过两面镜子一起照吗？如果A、B两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”。
4.8.1?斐波那契数列的实现86
4.8.2?递归的定义88
4.9 栈的应用——四则运算表达式求值89
4.9.1?后缀（逆波兰）表示法的定义89
4.9.2?后缀表达式的计算结果90
4.9.3?中缀表达式转后缀表达式92
4.10 队列的定义93
电脑有时会处于疑似死机的状态。就当你失去耐心，打算Reset时，突然它像酒醒了一样，把你刚才单击的所有操作全部都按顺序执行了一遍。
4.11 队列的抽象数据类型94
4.12 循环队列95
你上了公交车发现前排有两个空座位，而后排所有座位都已经坐满，你会怎么做？立马下车，并对自己说，后面没座了，我等下一辆？没这么笨的人，前面有座位，当然也是可以坐的。
4.12.1?队列顺序存储的不足95
4.12.2?循环队列的定义96
4.13 队列的链式存储结构及实现99
4.13.1?队列的链式存储结构——入队
操作100
4.13.2?队列的链式存储结构——出队
操作100
4.14 总结回顾101
4.15 结尾语102
人生，需要有队列精神的体现。南极到北极，不过是南纬90°到北纬90°的队列，如果你中途犹豫，临时转向，也许你就只能和企鹅相伴永远。可事实上，无论哪个方向，只要你坚持到底，你都可以到达终点。
第5章 串103
5.1 开场白104
“枯眼望遥山隔水，往来曾见几心知？壶空怕酌一杯酒，笔下难成和韵诗。途路阻人离别久，讯音无雁寄回迟。孤灯夜守长寥寂，夫忆妻兮父忆儿。”……可再仔细一读发现，这首诗竟然可以倒过来读。
5.2 串的定义104
我所提到的over、end、lie其实就是lover、friend、believe这些单词字符串的子串。
5.3 串的比较105
5.4 串的抽象数据类型107
5.5 串的存储结构108
感情上发生了问题，为了向女友解释一下，我准备发一条短信，一共打了75个字。 8个字是“我恨你是不可能的”，点发送。后来得知对方收到的，只有70个字，短信结尾是“……我恨你”。
5.5.1?串的顺序存储结构108
5.5.2?串的链式存储结构109
5.6 朴素的模式匹配算法110
主串为S=“00000000000000000000000000000000000000000000000001”，而要匹配的子串为T=“0000000001”，……在匹配时，每次都得将T中字符循环到 一位才发现，哦，原来它们是不匹配的。
5.7 KMP模式匹配算法113
很多年前我们的科学家觉得像这种有多个0和1重复字符的字符串，却需要挨个遍历的算法，是 糟糕的事情。
5.7.1?KMP模式匹配算法的原理113
5.7.2?next数组值的推导116
5.7.3?KMP模式匹配算法的实现117
5.7.4?KMP模式匹配算法的改进119
5.7.5?nextval数组值的推导120
5.8 总结回顾122
5.9 结尾语122
《璇玑图》共八百四十字，纵横各二十九字，纵、横、斜、交互、正、反读或退一字、迭一字读均可成诗，诗有三、四、五、六、七言不等，目前有人统计可组成七千九百五十八首诗。听清楚哦，是7958首。
第6章 树125
6.1 开场白126
无论多高多大的树，那也是从小到大，由根到叶，一点点成长起来的。俗话说“十年树木，百年树人”，可一棵大树又何止是十年这样容易。
6.2 树的定义126
树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了树的概念，这是比较新的一种定义方法。
6.2.1?结点的分类127
6.2.2?结点间的关系128
6.2.3?树的其他相关概念129
6.3 树的抽象数据类型129
6.4 树的存储结构130
6.4.1?双亲表示法130
6.4.2?孩子表示法133
6.4.3?孩子兄弟表示法136
6.5 二叉树的定义137
苏东坡曾说：“人有悲欢离合，月有阴晴圆缺，此事古难全”。意思就是 是理想，不 才是人生。我们通常举的例子也都是左高右低、参差不齐的二叉树。那是否存在 的二叉树呢？
6.5.1?二叉树的特点139
6.5.2?特殊二叉树140
6.6 二叉树的性质142
6.6.1?二叉树的性质1142
6.6.2?二叉树的性质2143
6.6.3?二叉树的性质3143
6.6.4?二叉树的性质4144
6.6.5?二叉树的性质5144
6.7 二叉树的存储结构145
6.7.1?二叉树的顺序存储结构145
6.7.2?二叉链表146
6.8 遍历二叉树147
你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择，由于选择方式的不同，遍历的次序就 不同。
6.8.1?二叉树的遍历原理147
6.8.2?二叉树的遍历方法148
6.8.3?前序遍历算法150
6.8.4?中序遍历算法153
6.8.5?后序遍历算法156
6.8.6?推导遍历结果156
6.9 二叉树的建立158
6.10 线索二叉树159
我们现在提倡节约型社会，一切都应该节约为本。对待我们的程序当然也不例外，能不浪费的时间或空间，都应该考虑节约。
6.10.1?线索二叉树的原理159
6.10.2?线索二叉树结构的实现162
6.11 树、森林与二叉树的转换165
有个乡镇企业也买了同样的生产线，老板发现这个问题后找了个小工来说：你必须搞定，不然炒你鱿鱼。小工很快想出了办法：他在生产线旁边放了台风扇猛吹，空皂盒自然会被吹走。
6.11.1?树转换为二叉树166
6.11.2?森林转换为二叉树167
6.11.3?二叉树转换为树168
6.11.4?二叉树转换为森林169
6.11.5?树与森林的遍历170
6.12 哈夫曼树及其应用171
压缩而不出错是如何做到的呢？简单地说，就是把我们要压缩的文本进行重新编码，以达到减少不必要的空间的技术。压缩和解压缩技术就是基于哈夫曼的研究之上发展而来，我们应该记住他。
6.12.1?哈夫曼树171
6.12.2?哈夫曼树的定义与原理173
6.12.3?哈夫曼编码176
6.13 总结回顾177
6.14 结尾语178
人受伤时会流下泪水。树受伤时，天将不会哭。希望我们的未来不要仅仅是钢筋水泥建造的高楼，也要有那郁郁葱葱的森林和草地，我们人类才可能与自然和谐共处。
第7章 图181
7.1 开场白182
如果你不善于规划，很有可能就会出现如玩好新疆后到海南，然后再冲向黑龙江这样的荒唐决策。
7.2 图的定义182
现实中，人与人之间的关系 复杂，比如我认识的朋友，可能他们之间也互相认识，这就不是简单的一对一、一对多的关系了，这就是我们 要研究的主题——图。
7.2.1?各种图的定义183
7.2.2?图的顶点与边间的关系185
7.2.3?连通图的相关术语187
7.2.4?图的定义与术语总结189
7.3 图的抽象数据类型190
7.4 图的存储结构191
因为美国的黑夜就是中国的白天，利用互联网，他的员工白天上班就可以监控到美国仓库夜间的实际情况，如果发生了像火灾、偷盗这样的突发事件，及时打电话给美国当地相关人员进行处理。
7.4.1?邻接矩阵192
7.4.2?邻接表195
7.4.3?十字链表198
7.4.4?邻接多重表199
7.4.5?边集数组201
7.5 图的遍历202
我有 早晨准备出门，发现钥匙不见了。一定是我儿子拿着玩，不知道丢到哪个犄角旮旯去了，你们说，我应该如何找？
7.5.1?深度优先遍历203
7.5.2?广度优先遍历205
7.6 小生成树208
如果你加班加点，没日没夜设计出的结果是方案一，我想你离被炒鱿鱼应该是不远了（同学微笑）。因为这个方案比后两个方案一半还多的成本会让老板气晕过去的。
7.6.1?普里姆（Prim）算法209
7.6.2?克鲁斯卡尔（Kruskal）算法213
7.7 短路径218
有人为了省钱，需路程 短，但换乘站间距离长等原因并不省时间；另一些人，他为赶时间， 的需求是总时间要短；还有一类人，他们不想多走路，关键是换乘要少，这样可以在车上好好休息一下。
7.7.1?迪杰斯特拉（Dijkstra）算法220
7.7.2?弗洛伊德（Floyd）算法225
7.8 拓扑排序229
电影制作不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中，场地都没有。这都会导致荒谬的结果。
7.8.1?拓扑排序介绍229
7.8.2?拓扑排序算法230
7.9 关键路径234
假如造一个轮子要0.5天、造一个发动机要3天、造一个车底盘要2天、造一个外壳要2天，造其他零部件2天，全部零部件集中到一处要0.5天，组装成车要2天，请问，在汽车厂造一辆车， 短需要多少天呢？
7.9.1?关键路径算法的原理236
7.9.2?关键路径算法237
7.10 总结回顾242
7.11 结尾语243
世界上 遥远的距离，不是牛A与牛C之间的狭小空隙，而是你们当中，有人在通往牛×的路上一路狂奔，而有人步入大学校园就学会放弃。
第8章 查找245
8.1 开场白246
当你精心写了一篇博文或者上传一组照片到互联网上，来自世界各地的无数“蜘蛛”便会蜂拥而至。所谓蜘蛛就是搜索引擎公司服务器上的软件，它把互联网当成了蜘蛛网，没日没夜地访问上面的各种信息。
8.2 查找概论247
比如网络时代的新名词，如 “蜗居”“蚁族”等，如果需要将它们收录到汉语词典中，显然收录时就需要查找它们是否存在，以及如果不存在时应该收录的位置。
8.3 顺序表查找249
8.3.1?顺序表查找算法249
8.3.2?顺序表查找优化250
8.4 有序表查找251
我在纸上已经写好了一个100以内的正整数请你猜，问几次可以猜出来。当时已经介绍了如何才可以 快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找。
8.4.1?折半查找251
8.4.2?插值查找253
8.4.3?斐波那契查找255
8.5 线性索引查找257
我母亲年纪大了，经常在家里找不到东西，于是她用一小本子，记录了家里所有小东西放置的位置，比如本放在右手床头柜下面抽屉中，钞票放在衣……咳，这个就不提了。
8.5.1?稠密索引258
8.5.2?分块索引258
8.5.3?倒排索引260
8.6 二叉排序树262
后来老虎来了，一人拼命地跑，另一人则急中生智，爬到了树上。而老虎是不会爬树的，结果……。爬树者改变了跑的思想，这一改变何等重要，捡回了自己的一条命。
8.6.1?二叉排序树的查找操作264
8.6.2?二叉排序树的插入操作266
8.6.3?二叉排序树的删除操作267
8.6.4?二叉排序树总结272
8.7 平衡二叉树（AVL树）273
平板就是一个世界，当 降临，人们心中的平衡被打破，世界就会混乱， 留下的只有孤独寂寞失败。这种单调的机械化的社会，禁不住 的侵蚀， 容易被侵蚀的，恰恰是 空虚的心灵。
8.7.1?平衡二叉树的实现原理275
8.7.2?平衡二叉树的实现算法278
8.8 多路查找树（B树）284
要观察一个公司是否严谨，看他们如何开会就知道了。如果开会时每一个人都只是带一张嘴，即兴发言，这肯定是一家不严谨的公司。
8.8.1?2-3树285
8.8.2?2-3-4树289
8.8.3?B树290
8.8.4?B+树292
8.9 散列表查找（哈希表）概述294
你很想学太极拳，听说学校有个叫张三丰的人打得特别好，于是到学校学生处找人，工作人员拿出学生名单， 终告诉你，学校没这个人，并说张三丰几百年前就已经在武当山作古了。
8.9.1?散列表查找定义294
8.9.2?散列表查找步骤295
8.10 散列函数的构造方法296
8.10.1?直接定址法297
8.10.2?数字分析法297
8.10.3?平方取中法298
8.10.4?折叠法298
8.10.5?除留余数法298
8.10.6?随机数法299
8.11 处理散列冲突的方法300
我们每个人都希望身体健康，虽然疾病可以预防，但不可避免，没有任何人可以说，生下来到现在没有生过一次病。
8.11.1?开放定址法300
8.11.2?再散列函数法302
8.11.3?链地址法302
8.11.4?公共溢出区法302
8.12 散列表查找的实现303
8.12.1?散列表查找的算法实现303
8.12.2?散列表查找的性能分析305
8.13 总结回顾305
如果我是个喜欢汽车的人，时常搜汽车信息。那么当我在搜索框中输入“甲壳虫”“美洲虎”等关键词时，不要让动物和人物成为搜索的头条。
8.14 结尾语306
第9章 排序309
9.1 开场白310
假如我想买一台iPhone 4的手机，于是上了某电子商务网站去搜索。可搜索后发现，有8863个相关的物品，如此之多，这叫我如何选择。我其实是想买便宜一点的，但是又怕遇到骗子，想找信誉好的商家，如何做？
9.2 排序的基本概念与分类310
比如我们某些大学为了选拔在主科上 的学生，要求对所有学生的所有科目总分倒序排名，并且在同样总分的情况下将语数外总分做倒序排名。这就是对总分和语数外总分两个次关键字的组合排序。
9.2.1?排序的稳定性311
9.2.2?内排序与外排序312
9.2.3?排序用到的结构与函数313
9.3 冒泡排序314
无论你学习哪种编程语言，在学到循环和数组时，通常都会介绍一种排序算法，而这个算法一般就是冒泡排序。并不是它的名称很好听，而是说这个算法的思路 简单， 容易理解。
9.3.1? 简单排序的实现314
9.3.2?冒泡排序算法315
9.3.3?冒泡排序优化316
9.3.4?冒泡排序复杂度分析317
9.4 简单选择排序318
还有一种做股票的人，他们很少出手，只是在不断观察和判断，等时机一到，果断买进或卖出。他们因为冷静和沉着，以及交易的次数少，而 终收益颇丰。
9.4.1?简单选择排序算法318
9.4.2?简单选择排序复杂度分析319
9.5 直接插入排序320
哪怕你是 次玩扑克牌，只要认识这些数字，理牌的方法都是不用教的。将3和4移动到5的左侧，再将2移动到 左侧，顺序就算是理好了。这里，我们的理牌方法，就是直接插入排序法。
9.5.1?直接插入排序算法320
9.5.2?直接插入排序复杂度分析322
9.6 希尔排序323
不管怎么说，希尔排序算法的发明，使得我们终于突破了慢速排序的时代（ 了时间复杂度为O(n2)），之后， 为高效的排序算法也就相继出现了。
9.6.1?希尔排序原理324
9.6.2?希尔排序算法325
9.6.3?希尔排序复杂度分析328
9.7 堆排序329
什么叫堆结构呢？回忆一下我们小时候，特别是男同学，基本都玩过叠罗汉的恶作剧。通常都是先把某个要整的人按倒在地，然后大家就一拥而上扑了上去……后果？后果当然就是一笑了之。
9.7.1?堆排序算法331
9.7.2?堆排序复杂度分析337
9.8 归并排序337
即使你是你们班级 、甚至年级 名，如果你没有上分数线，则说明你的成绩排不到全省前1万名，你也就基本失去了当年上本科的机会了。
9.8.1?归并排序算法338
9.8.2?归并排序复杂度分析343
9.8.3?非递归实现归并排序343
9.9 快速排序346
终于我们的高手要登场了，将来你工作后，你的老板让你写个排序算法，而你会的算法中竟然没有快速排序，我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑，这样至少你不至于被大伙儿取笑。
9.9.1?快速排序算法346
9.9.2?快速排序复杂度分析349
9.9.3?快速排序优化350
9.10 总结回顾354
目前还没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。
9.11 结尾语357
如果你有梦想的话，就要去捍卫它。当别人做不到的时候，他们就想要告诉你，你也不能。如果你想要些什么，就得去努力争取。就这样！
第1章?数据结构绪论1
1.1 开场白2
如果你交给某人一个程序，你将折磨他一整天；如果你教某人如何编写程序，你将折磨他一辈子。
1.2 你数据结构怎么学的3
他完成开发并测试通过后，得意地提交了代码。项目经理看完代码后拍着桌子对他说：“你数据结构是怎么学的？”
1.3 数据结构起源4
1.4 基本概念和术语5
正所谓“巧妇难为无米之炊”，再强大的计算机，也要有“米”下锅才可以干活，否则就是一堆破铜烂铁。这个“米”就是数据。
1.4.1?数据5
1.4.2?数据元素6
1.4.3?数据项7
1.4.4?数据对象7
1.4.5?数据结构7
1.5 逻辑结构与物理结构8
1.5.1?逻辑结构8
1.5.2?物理结构9
1.6 数据类型11
大家都需要房子住，但显然没钱考虑大房子是没有意义的。于是商品房就出现了各种各样的户型，有几百平米的别墅，也有仅两平米的胶囊公寓……
1.6.1?数据类型定义11
1.6.2?抽象数据类型12
1.7 总结回顾13
1.8 结尾语14
终的结果一定是，你对着别人很牛地说“数据结构——就那么回事。”
第2章 算法15
2.1 开场白16
2.2 数据结构与算法的关系16
计算机界的前辈们，是一帮很牛很牛的人，他们使得很多看似没法解决或者很难解决的问题，处理得如此美妙和神奇。
2.3 两种算法的比较17
高斯在上小学的 ，老师要求每个学生都计算1+2+…+100的结果，谁先算出来谁先回家……
2.4 算法定义18
现实世界中的算法千变万化，没有通用算法可以解决所有问题。甚至一个小问题，某个解决此类问题很 的算法却未必就适合它。
2.5 算法的特性19
2.5.1?输入输出19
2.5.2?有穷性19
2.5.3?确定性20
2.5.4?可行性20
2.6 算法设计的要求20
求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有 大的差异，我们自然追求高效率和低存储的算法来解决问题。
2.6.1?正确性21
2.6.2?可读性21
2.6.3?健壮性21
2.6.4?时间效率高和存储量低22
2.7 算法效率的度量方法22
随着n值越来越大，它们在时间效率上的差异也就越来越大。好比有些人每天都在学习，而有些人，打打游戏、睡睡大觉，毕业后前者名企争着要，后者求职处处无门。
2.7.1?事后统计方法22
2.7.2?事前分析估算方法23
2.8 函数的渐近增长25
2.9 算法时间复杂度27
理解大O阶推导不算难，难的其实是对数列的一些相关运算，这考查的 多是数学知识和能力。
2.9.1?算法时间复杂度定义27
2.9.2?推导大O阶方法28
2.9.3?常数阶28
2.9.4?线性阶29
2.9.5?对数阶29
2.9.6?平方阶29
2.10 常见的时间复杂度31
有些时候，告诉你某些东西不可以去尝试，也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以招惹吧。
2.11 坏情况与平均情况32
2.12 算法空间复杂度33
事先建立一个有2050个元素的数组，然后把所有年份按下标数字对应，如果是闰年，此数组项的值就是1，如果不是就是0。这样，所谓的判断某一年是否是闰年就变成了查找这个数组的某一项的值是多少的问题。
2.13 总结回顾34
2.14 结尾语35
愚公移山固然可敬，但发明和推土机，可能 加实在和聪明。
第3章 线性表37
3.1 开场白38
门外家长都挤在大门口与门里的小孩子的井然有序，形成了鲜明对比。哎，有时大人的所作所为，其实还不如孩子。
3.2 线性表的定义39
有时我们想知道某个小朋友（比如麦兜）是否是班级的同学，老师会告诉我说，没有，麦兜是在春田花花幼儿园里。这种查找某个元素是否存在的操作很常用。
3.3 线性表的抽象数据类型41
3.4 线性表的顺序存储结构43
他每次一吃完早饭就冲着去了图书馆，挑一个好地儿，把他书包里的书，一本一本地按座位放好，长长一排，九个座硬是被他占了。
3.4.1?顺序存储定义43
3.4.2?顺序存储方式43
3.4.3?数据长度与线性表长度的区别44
3.4.4?地址计算方法45
3.5 顺序存储结构的插入与删除46
春运时去买火车票，大家都排着队好好的，这时来了一个美女：“可否让我排在你前面？”这可不得了，后面的人像蠕虫一样，全部都得退后一步。
3.5.1?获得元素操作46
3.5.2?插入操作46
3.5.3?删除操作47
3.5.4?线性表顺序存储结构的优缺点49
3.6 线性表的链式存储结构49
反正也是要让相邻元素间留有足够余地，那干脆所有元素都不要考虑相邻位置了，哪有空位就到哪里。而只是让每个元素知道它下一个元素的位置在哪里。
3.6.1?顺序存储结构不足的解决办法49
3.6.2?线性表链式存储结构定义50
3.6.3?头指针与头结点的异同52
3.6.4?线性表链式存储结构代码描述52
3.7 单链表的读取53
3.8 单链表的插入与删除54
本来是爸爸左手牵着妈 手、右手牵着宝宝的手在马路边散步。突然迎面走来一美女，爸爸失神般地望着，此情景被妈妈逮个正着，于是扯开父子俩，拉起宝宝的左手就快步朝前走去。
3.8.1?单链表的插入54
3.8.2?单链表的删除56
3.9 单链表的整表创建58
3.10 单链表的整表删除60
3.11 单链表结构与顺序存储结构的优缺点61
3.12 静态链表62
对于一些语言，如Basic、Fortran等早期的编程 语言，由于没有指针，这链表结构，按照前面我们的讲法，它就没法实现了。怎么办呢？
3.12.1?静态链表的插入操作64
3.12.2?静态链表的删除操作65
3.12.3?静态链表的优缺点67
3.13 循环链表67
这个轮回的思想很有意思。它强调了不管你今生是穷是富，如果持续行善积德，下辈子就会好过，反之就会遭到报应。
3.14 双向链表70
就像每个人的人生一样，欲收获就得付出代价。双向链表既然是比单链表多了如可以反向遍历查找等的数据结构，那么也就需要付出一些小的代价。
3.15 总结回顾72
3.16 结尾语73
如果你觉得上学读书是受罪，假设你可以活到80岁，其实你 多也就吃了20年苦。用人生四分之一的时间来换取其余时间的幸福生活，这点苦不算啥。
第4章 栈与队列75
4.1 开场白76
想想看，在你准备用的时候，突然这手明明有却打不出来，这不是要命吗。
4.2 栈的定义76
类似的很多软件，比如Word、Photoshop等，都有撤销（undo）的操作，也是用栈这种思想方式来实现的。
4.2.1?栈的定义76
4.2.2?进栈出栈变化形式78
4.3 栈的抽象数据类型78
4.4 栈的顺序存储结构及实现79
4.4.1?栈的顺序存储结构79
4.4.2?栈的顺序存储结构——进栈操作80
4.4.3?栈的顺序存储结构——出栈操作81
4.5 两栈共享空间81
两个大学室友毕业同时到北京工作，他们都希望租房时能找到独自住的一室或一室一厅，可找来找去发现，价格实在是承受不起。
4.6 栈的链式存储结构及实现83
4.6.1?栈的链式存储结构83
4.6.2?栈的链式存储结构——进栈操作84
4.6.3?栈的链式存储结构——出栈操作85
4.7 栈的作用85
4.8 栈的应用——递归86
当你往镜子前面一站，镜子里面就有一个你的图像。但你试过两面镜子一起照吗？如果A、B两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”。
4.8.1?斐波那契数列的实现86
4.8.2?递归的定义88
4.9 栈的应用——四则运算表达式求值89
4.9.1?后缀（逆波兰）表示法的定义89
4.9.2?后缀表达式的计算结果90
4.9.3?中缀表达式转后缀表达式92
4.10 队列的定义93
电脑有时会处于疑似死机的状态。就当你失去耐心，打算Reset时，突然它像酒醒了一样，把你刚才单击的所有操作全部都按顺序执行了一遍。
4.11 队列的抽象数据类型94
4.12 循环队列95
你上了公交车发现前排有两个空座位，而后排所有座位都已经坐满，你会怎么做？立马下车，并对自己说，后面没座了，我等下一辆？没这么笨的人，前面有座位，当然也是可以坐的。
4.12.1?队列顺序存储的不足95
4.12.2?循环队列的定义96
4.13 队列的链式存储结构及实现99
4.13.1?队列的链式存储结构——入队
操作100
4.13.2?队列的链式存储结构——出队
操作100
4.14 总结回顾101
4.15 结尾语102
人生，需要有队列精神的体现。南极到北极，不过是南纬90°到北纬90°的队列，如果你中途犹豫，临时转向，也许你就只能和企鹅相伴永远。可事实上，无论哪个方向，只要你坚持到底，你都可以到达终点。
第5章 串103
5.1 开场白104
“枯眼望遥山隔水，往来曾见几心知？壶空怕酌一杯酒，笔下难成和韵诗。途路阻人离别久，讯音无雁寄回迟。孤灯夜守长寥寂，夫忆妻兮父忆儿。”……可再仔细一读发现，这首诗竟然可以倒过来读。
5.2 串的定义104
我所提到的over、end、lie其实就是lover、friend、believe这些单词字符串的子串。
5.3 串的比较105
5.4 串的抽象数据类型107
5.5 串的存储结构108
感情上发生了问题，为了向女友解释一下，我准备发一条短信，一共打了75个字。 8个字是“我恨你是不可能的”，点发送。后来得知对方收到的，只有70个字，短信结尾是“……我恨你”。
5.5.1?串的顺序存储结构108
5.5.2?串的链式存储结构109
5.6 朴素的模式匹配算法110
主串为S=“00000000000000000000000000000000000000000000000001”，而要匹配的子串为T=“0000000001”，……在匹配时，每次都得将T中字符循环到 一位才发现，哦，原来它们是不匹配的。
5.7 KMP模式匹配算法113
很多年前我们的科学家觉得像这种有多个0和1重复字符的字符串，却需要挨个遍历的算法，是 糟糕的事情。
5.7.1?KMP模式匹配算法的原理113
5.7.2?next数组值的推导116
5.7.3?KMP模式匹配算法的实现117
5.7.4?KMP模式匹配算法的改进119
5.7.5?nextval数组值的推导120
5.8 总结回顾122
5.9 结尾语122
《璇玑图》共八百四十字，纵横各二十九字，纵、横、斜、交互、正、反读或退一字、迭一字读均可成诗，诗有三、四、五、六、七言不等，目前有人统计可组成七千九百五十八首诗。听清楚哦，是7958首。
第6章 树125
6.1 开场白126
无论多高多大的树，那也是从小到大，由根到叶，一点点成长起来的。俗话说“十年树木，百年树人”，可一棵大树又何止是十年这样容易。
6.2 树的定义126
树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了树的概念，这是比较新的一种定义方法。
6.2.1?结点的分类127
6.2.2?结点间的关系128
6.2.3?树的其他相关概念129
6.3 树的抽象数据类型129
6.4 树的存储结构130
6.4.1?双亲表示法130
6.4.2?孩子表示法133
6.4.3?孩子兄弟表示法136
6.5 二叉树的定义137
苏东坡曾说：“人有悲欢离合，月有阴晴圆缺，此事古难全”。意思就是 是理想，不 才是人生。我们通常举的例子也都是左高右低、参差不齐的二叉树。那是否存在 的二叉树呢？
6.5.1?二叉树的特点139
6.5.2?特殊二叉树140
6.6 二叉树的性质142
6.6.1?二叉树的性质1142
6.6.2?二叉树的性质2143
6.6.3?二叉树的性质3143
6.6.4?二叉树的性质4144
6.6.5?二叉树的性质5144
6.7 二叉树的存储结构145
6.7.1?二叉树的顺序存储结构145
6.7.2?二叉链表146
6.8 遍历二叉树147
你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择，由于选择方式的不同，遍历的次序就 不同。
6.8.1?二叉树的遍历原理147
6.8.2?二叉树的遍历方法148
6.8.3?前序遍历算法150
6.8.4?中序遍历算法153
6.8.5?后序遍历算法156
6.8.6?推导遍历结果156
6.9 二叉树的建立158
6.10 线索二叉树159
我们现在提倡节约型社会，一切都应该节约为本。对待我们的程序当然也不例外，能不浪费的时间或空间，都应该考虑节约。
6.10.1?线索二叉树的原理159
6.10.2?线索二叉树结构的实现162
6.11 树、森林与二叉树的转换165
有个乡镇企业也买了同样的生产线，老板发现这个问题后找了个小工来说：你必须搞定，不然炒你鱿鱼。小工很快想出了办法：他在生产线旁边放了台风扇猛吹，空皂盒自然会被吹走。
6.11.1?树转换为二叉树166
6.11.2?森林转换为二叉树167
6.11.3?二叉树转换为树168
6.11.4?二叉树转换为森林169
6.11.5?树与森林的遍历170
6.12 哈夫曼树及其应用171
压缩而不出错是如何做到的呢？简单地说，就是把我们要压缩的文本进行重新编码，以达到减少不必要的空间的技术。压缩和解压缩技术就是基于哈夫曼的研究之上发展而来，我们应该记住他。
6.12.1?哈夫曼树171
6.12.2?哈夫曼树的定义与原理173
6.12.3?哈夫曼编码176
6.13 总结回顾177
6.14 结尾语178
人受伤时会流下泪水。树受伤时，天将不会哭。希望我们的未来不要仅仅是钢筋水泥建造的高楼，也要有那郁郁葱葱的森林和草地，我们人类才可能与自然和谐共处。
第7章 图181
7.1 开场白182
如果你不善于规划，很有可能就会出现如玩好新疆后到海南，然后再冲向黑龙江这样的荒唐决策。
7.2 图的定义182
现实中，人与人之间的关系 复杂，比如我认识的朋友，可能他们之间也互相认识，这就不是简单的一对一、一对多的关系了，这就是我们 要研究的主题——图。
7.2.1?各种图的定义183
7.2.2?图的顶点与边间的关系185
7.2.3?连通图的相关术语187
7.2.4?图的定义与术语总结189
7.3 图的抽象数据类型190
7.4 图的存储结构191
因为美国的黑夜就是中国的白天，利用互联网，他的员工白天上班就可以监控到美国仓库夜间的实际情况，如果发生了像火灾、偷盗这样的突发事件，及时打电话给美国当地相关人员进行处理。
7.4.1?邻接矩阵192
7.4.2?邻接表195
7.4.3?十字链表198
7.4.4?邻接多重表199
7.4.5?边集数组201
7.5 图的遍历202
我有 早晨准备出门，发现钥匙不见了。一定是我儿子拿着玩，不知道丢到哪个犄角旮旯去了，你们说，我应该如何找？
7.5.1?深度优先遍历203
7.5.2?广度优先遍历205
7.6 小生成树208
如果你加班加点，没日没夜设计出的结果是方案一，我想你离被炒鱿鱼应该是不远了（同学微笑）。因为这个方案比后两个方案一半还多的成本会让老板气晕过去的。
7.6.1?普里姆（Prim）算法209
7.6.2?克鲁斯卡尔（Kruskal）算法213
7.7 短路径218
有人为了省钱，需路程 短，但换乘站间距离长等原因并不省时间；另一些人，他为赶时间， 的需求是总时间要短；还有一类人，他们不想多走路，关键是换乘要少，这样可以在车上好好休息一下。
7.7.1?迪杰斯特拉（Dijkstra）算法220
7.7.2?弗洛伊德（Floyd）算法225
7.8 拓扑排序229
电影制作不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中，场地都没有。这都会导致荒谬的结果。
7.8.1?拓扑排序介绍229
7.8.2?拓扑排序算法230
7.9 关键路径234
假如造一个轮子要0.5天、造一个发动机要3天、造一个车底盘要2天、造一个外壳要2天，造其他零部件2天，全部零部件集中到一处要0.5天，组装成车要2天，请问，在汽车厂造一辆车， 短需要多少天呢？
7.9.1?关键路径算法的原理236
7.9.2?关键路径算法237
7.10 总结回顾242
7.11 结尾语243
世界上 遥远的距离，不是牛A与牛C之间的狭小空隙，而是你们当中，有人在通往牛×的路上一路狂奔，而有人步入大学校园就学会放弃。
第8章 查找245
8.1 开场白246
当你精心写了一篇博文或者上传一组照片到互联网上，来自世界各地的无数“蜘蛛”便会蜂拥而至。所谓蜘蛛就是搜索引擎公司服务器上的软件，它把互联网当成了蜘蛛网，没日没夜地访问上面的各种信息。
8.2 查找概论247
比如网络时代的新名词，如 “蜗居”“蚁族”等，如果需要将它们收录到汉语词典中，显然收录时就需要查找它们是否存在，以及如果不存在时应该收录的位置。
8.3 顺序表查找249
8.3.1?顺序表查找算法249
8.3.2?顺序表查找优化250
8.4 有序表查找251
我在纸上已经写好了一个100以内的正整数请你猜，问几次可以猜出来。当时已经介绍了如何才可以 快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找。
8.4.1?折半查找251
8.4.2?插值查找253
8.4.3?斐波那契查找255
8.5 线性索引查找257
我母亲年纪大了，经常在家里找不到东西，于是她用一小本子，记录了家里所有小东西放置的位置，比如本放在右手床头柜下面抽屉中，钞票放在衣……咳，这个就不提了。
8.5.1?稠密索引258
8.5.2?分块索引258
8.5.3?倒排索引260
8.6 二叉排序树262
后来老虎来了，一人拼命地跑，另一人则急中生智，爬到了树上。而老虎是不会爬树的，结果……。爬树者改变了跑的思想，这一改变何等重要，捡回了自己的一条命。
8.6.1?二叉排序树的查找操作264
8.6.2?二叉排序树的插入操作266
8.6.3?二叉排序树的删除操作267
8.6.4?二叉排序树总结272
8.7 平衡二叉树（AVL树）273
平板就是一个世界，当 降临，人们心中的平衡被打破，世界就会混乱， 留下的只有孤独寂寞失败。这种单调的机械化的社会，禁不住 的侵蚀， 容易被侵蚀的，恰恰是 空虚的心灵。
8.7.1?平衡二叉树的实现原理275
8.7.2?平衡二叉树的实现算法278
8.8 多路查找树（B树）284
要观察一个公司是否严谨，看他们如何开会就知道了。如果开会时每一个人都只是带一张嘴，即兴发言，这肯定是一家不严谨的公司。
8.8.1?2-3树285
8.8.2?2-3-4树289
8.8.3?B树290
8.8.4?B+树292
8.9 散列表查找（哈希表）概述294
你很想学太极拳，听说学校有个叫张三丰的人打得特别好，于是到学校学生处找人，工作人员拿出学生名单， 终告诉你，学校没这个人，并说张三丰几百年前就已经在武当山作古了。
8.9.1?散列表查找定义294
8.9.2?散列表查找步骤295
8.10 散列函数的构造方法296
8.10.1?直接定址法297
8.10.2?数字分析法297
8.10.3?平方取中法298
8.10.4?折叠法298
8.10.5?除留余数法298
8.10.6?随机数法299
8.11 处理散列冲突的方法300
我们每个人都希望身体健康，虽然疾病可以预防，但不可避免，没有任何人可以说，生下来到现在没有生过一次病。
8.11.1?开放定址法300
8.11.2?再散列函数法302
8.11.3?链地址法302
8.11.4?公共溢出区法302
8.12 散列表查找的实现303
8.12.1?散列表查找的算法实现303
8.12.2?散列表查找的性能分析305
8.13 总结回顾305
如果我是个喜欢汽车的人，时常搜汽车信息。那么当我在搜索框中输入“甲壳虫”“美洲虎”等关键词时，不要让动物和人物成为搜索的头条。
8.14 结尾语306
第9章 排序309
9.1 开场白310
假如我想买一台iPhone 4的手机，于是上了某电子商务网站去搜索。可搜索后发现，有8863个相关的物品，如此之多，这叫我如何选择。我其实是想买便宜一点的，但是又怕遇到骗子，想找信誉好的商家，如何做？
9.2 排序的基本概念与分类310
比如我们某些大学为了选拔在主科上 的学生，要求对所有学生的所有科目总分倒序排名，并且在同样总分的情况下将语数外总分做倒序排名。这就是对总分和语数外总分两个次关键字的组合排序。
9.2.1?排序的稳定性311
9.2.2?内排序与外排序312
9.2.3?排序用到的结构与函数313
9.3 冒泡排序314
无论你学习哪种编程语言，在学到循环和数组时，通常都会介绍一种排序算法，而这个算法一般就是冒泡排序。并不是它的名称很好听，而是说这个算法的思路 简单， 容易理解。
9.3.1? 简单排序的实现314
9.3.2?冒泡排序算法315
9.3.3?冒泡排序优化316
9.3.4?冒泡排序复杂度分析317
9.4 简单选择排序318
还有一种做股票的人，他们很少出手，只是在不断观察和判断，等时机一到，果断买进或卖出。他们因为冷静和沉着，以及交易的次数少，而 终收益颇丰。
9.4.1?简单选择排序算法318
9.4.2?简单选择排序复杂度分析319
9.5 直接插入排序320
哪怕你是 次玩扑克牌，只要认识这些数字，理牌的方法都是不用教的。将3和4移动到5的左侧，再将2移动到 左侧，顺序就算是理好了。这里，我们的理牌方法，就是直接插入排序法。
9.5.1?直接插入排序算法320
9.5.2?直接插入排序复杂度分析322
9.6 希尔排序323
不管怎么说，希尔排序算法的发明，使得我们终于突破了慢速排序的时代（ 了时间复杂度为O(n2)），之后， 为高效的排序算法也就相继出现了。
9.6.1?希尔排序原理324
9.6.2?希尔排序算法325
9.6.3?希尔排序复杂度分析328
9.7 堆排序329
什么叫堆结构呢？回忆一下我们小时候，特别是男同学，基本都玩过叠罗汉的恶作剧。通常都是先把某个要整的人按倒在地，然后大家就一拥而上扑了上去……后果？后果当然就是一笑了之。
9.7.1?堆排序算法331
9.7.2?堆排序复杂度分析337
9.8 归并排序337
即使你是你们班级 、甚至年级 名，如果你没有上分数线，则说明你的成绩排不到全省前1万名，你也就基本失去了当年上本科的机会了。
9.8.1?归并排序算法338
9.8.2?归并排序复杂度分析343
9.8.3?非递归实现归并排序343
9.9 快速排序346
终于我们的高手要登场了，将来你工作后，你的老板让你写个排序算法，而你会的算法中竟然没有快速排序，我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑，这样至少你不至于被大伙儿取笑。
9.9.1?快速排序算法346
9.9.2?快速排序复杂度分析349
9.9.3?快速排序优化350
9.10 总结回顾354
目前还没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。
9.11 结尾语357
如果你有梦想的话，就要去捍卫它。当别人做不到的时候，他们就想要告诉你，你也不能。如果你想要些什么，就得去努力争取。就这样！
