Table of Contents:

《数据结构与算法之美》专栏的实现代码（C++）& 笔记 https://github.com/saber/algorithm

数据结构和算法必知必会的50个代码实现 https://github.com/wangzheng0822/algo

00 | 开篇词丨从今天起，跨过“数据结构与算法”这道坎

人生路上，我们会遇到很多的坎。跨过去，你就可以成长，跨不过去就是困难和停滞。而在后面很长的一段时间里，你都需要为这个困难买单。既然数据结构和算法是这个坎，我们总归是要跨过去，为什么不是现在呢？

01 | 为什么要学习数据结构和算法？

02 | 如何抓住重点，系统高效地学习数据结构与算法？

为什么大部分书都把这两个东西放到一块儿来讲呢？
这是因为，数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。
数据结构和算法课程确实会涉及一些数学方面的推理、证明，尤其是在分析某个算法的时间、空间复杂度的时候，但是这个你完全不需要担心。

学习的重点在什么地方？

  1. 首先要掌握一个数据结构与算法中最重要的概念——复杂度分析。
  2. 结合我自己的学习心得，还有这些年的面试、开发经验，我总结了20 个最常用的、最基础数据结构与算法，不管是应付面试还是工作需要，只要集中精力逐一攻克这 20 个知识点就足够了。

03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。

第一个例子中的 T(n) = O(2n+2)，第二个例子中的 T(n) = O(2n^2+2n+3)。这就是大 O 时间复杂度表示法。大 O 时间复杂度是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n^2)。
总的时间复杂度就等于量级最大的那段代码的时间复杂度。

几种常见时间复杂度实例分析

O(1) 常量级时间复杂度
O(logn) 对数级 O(log3n) = O(C * log2n) 其他底的都可以转换成以2为底的

O(n) 线性级
O(nlogn) 线性 对数 级

O(n^2 ) 平方，立方，k次方级

O(2^n ) 指数级

O(n! ) 阶乘级

04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度

之所以引入这几个复杂度概念，是因为，同一段代码，在不同输入的情况下，复杂度量级有可能是不一样的。

最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，我们需要引入另一个概念：平均情况时间复杂度
平均时间复杂度往往等于 最坏情况时间复杂度

05 | 数组：为什么很多编程语言中数组都从0开始编号？

线性表就是数据排成像一条线一样的结构。每个 线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结 构。
而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非 线性表中，数据之间并不是简单的前后关系。
数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

删除操作

和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；
如果删除开头的 数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n)
实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次
删除操作集中在一起执行，删除的效率是不是会提高很多呢？
每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存
储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬 移。
如果你了解 JVM，你会发现，这不就是 JVM 标记清除垃圾回收算法的核心思想吗？没错，
数据结构和算法的魅力就在于此， 要学习它背后的思想和处理技巧，这些东西才是最有价值的。

警惕数组的访问越界问题

数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。
因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可 用的，那么程序就可能不会报任何错误。
这种情况下，一般都会出现莫名其妙的逻辑错误(越界后可能会操作其他的局部变量) 。而且，很多计算机病毒也正是利用到了代码中的数组越界可以访问非法地址 的漏洞，来攻击系统。

容器能否完全替代数组？何时用数组

  1. Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而
    Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基
    本类型，就可以选用数组。
  2. 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方
    法，也可以直接使用数组。
  3. 还有一个是我个人的喜好，当要表示多维数组时，用数组往往会更加直观。比如
    Object[][] array；而用容器的话则需要这样定义：ArrayList<ArrayList > array。
  4. 对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完
    全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性
    能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

数组为何从 0 开始编号

下标”最确切的定义应该是偏移（offset)。 ，如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就 表示偏移 k 个 type_size 的位置，所以计算 a[k] 的内存地址只需要用这个公式：
a[k]_address = base_address + k * type_size
但是，如果数组从 1 开始计数，那我们计算数组元素 a[k] 的内存地址就会变为：
a[k]_address = base_address + (k-1)*type_size

下标从1开始的多了一次减法运 算，对于 CPU 来说，就是多了一次减法指令，故选第一种。
C语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语 言

06 | 链表（上）：如何实现LRU缓存淘汰算法?

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比
如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就
需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First
Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
用链表可以这样实现：
我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
如果此时缓存未满，则将此结点直接插入到链表的头部；
如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

链表结构五花八门，常见的有：单链表、双 向链表和循环链表。
头结点用来记录链表的基地址

尾结 点指向一个空地址 NULL，表示这是链表 上最后一个结点。
链表要想随机访问第 k 个元素,需要挨个遍历知道找到第k个元素。

双向链表优势

从链表中删除一个数据的两种情况：
1.删除结点中“值等于某个给定值”的结点，此时链表需要遍历才能找到。
2.删除给定指针指向的结点，单链表此时就有劣势了。
单链表：删除某个节点需要遍历才能知道其前驱节点，故：遍历+删除 O(n) + O(1)
双链表：因知道其前驱节点，故：删除 O(1)

对于一个有序链表，双向链表的按值查询的效率也要比单
链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p
的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

双向链表尽管比较费内存，但还是比单链表的应用更加广泛。这里有一个更加重要的知识点需要你掌握，那就是用空间换时间的设计思想。当内 存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较 高、但时间复杂度相对很低的算法或者数据结构。
缓存实际上就是利用了空间换时间的设计思想。

和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。

07 | 链表（下）：如何轻松写出正确的链表代码？

针对链表的插入、删除操作，需要对插入第一个结 点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且 也容易因为考虑不全而出错。

我经常用来检查链表代码是否正确的边界条件有这样几个：
如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

写链表代码是最考验逻辑思维能力的。因为，链表代码到处都是指针的操作、边界
条件的处理，稍有不慎就容易产生 Bug。链表代码写得好坏，可以看出一个人写代码是否
够细心，考虑问题是否全面，思维是否缜密。所以，这也是很多面试官喜欢让人手写链表代
码的原因。

08 | 栈：如何实现浏览器的前进和后退功能？

从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特 定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时 就比较不可控，自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出的特性，我们 就应该首选“栈”这种数据结构。

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序 栈，用链表实现的栈，我们叫作链式栈。

如果要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就
可以了。当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。

栈的应用场景

比如：34+13*9+44- 12/3
使用两个栈，其中一个保存操作数的栈，另一个是保存运算符 的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符， 就与运算符栈的栈顶元素进行比较，然后决定是计算还是继续入栈
* 括号匹配
* 浏览 器前进、后退功能
需要两个栈，一个放访问过的，一个是放回退时push的，用于保留前进的页面

09 | 队列：队列在线程池等有限资源池中的应用

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用
链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作
链式队列。
对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指
针，指向队头；一个是 tail 指针，指向队尾。

循环队列

阻塞队列和并发队列

阻塞队列其实就是在队列基础上增加了阻塞操作。如果队列为空的时候，从队 头取数据会被阻塞。如果队列已 经满了，那么插入数据的操作就会被阻塞。 上述的定义就是一个“生产者 - 消费者模型”
基于阻塞队列，我们还可以通过动态调整“生产者”和“消费者”的个数，来提 高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应对一个“生产 者”。

前面我们讲了阻塞队列，在多线程情况下，会有多个线程同时操作队列，这个时候就会存在
线程安全问题，那如何实现一个线程安全的队列呢？
线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、
dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操
作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。
这也是循环队列比链式队列应用更加广泛的原因。

10 | 递归：如何用三行代码找到“最终推荐人”？

利:是递归代码的表达力很强，写起来非常简洁；
弊:就是空间 复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。

上台阶问题

有n个台阶，每次你可以跨1个或者2个台阶，请问走这 n个台阶有多少种走法？
n的问题规模可以通过子问题来求解
递推公式：f(n) = f(n-1) + f(n-2)
递归基：f(1) = 1; f(2) = 2; 因为问题规模被划分成两个，这两个都的解出才有结果

关键步骤:

  1. 找到如何将大问题分解为小问题的规律，比如：n规模的问题能不能通过n-1的规模(子问题)或多个n-x的规模之和来解决。
  2. 并且基于此写出递推式
  3. 然后再推敲终止条件，终止条件可以有好几个，这个是需要注意的，对应于上面的多个n-x的规模之和
  4. 用几个小规模的问题验证一下有没有问题
  5. 最后将递推公式和终止条件翻译成代码

误区：

对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很
多时候，我们理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。
如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解
决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层
之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间
的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
因此，编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一
层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归代码要警惕堆栈溢出

函数栈的空间是有限的，如果递归深度过大的话，会造成stackoverflow。
我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定
深度（比如 1000）之后，我们就不继续往下再递归了，直接返回报错。
但是这解决不了根本问题，解决只能换成循环

递归代码要警惕重复计算

使用递归时还会出现重复计算的问题，这种往往出现在分解成多个子问题的时候。

为了避免重复计算，我们可以通过一个表来保存已经求解过的 f(k),有则直接取，没有则存。
比如之前上台阶的问题：

public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    // hasSolvedList 可以理解成一个 Map，key 是 n，value 是 f(n)
    if (hasSolvedList.containsKey(n)) {
        return hasSovledList.get(n);
    }
    int ret = f(n-1) + f(n-2);
    hasSovledList.put(n, ret);
    return ret;
}

考虑时间空间复杂度

在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成
一个可观的时间成本。在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数
据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销。

怎么将递归代码改写为非递归代码？

调试递归:

1.打印日志发现，递归值。
2.结合条件断点进行调试

11 | 排序（上）：为什么插入排序比冒泡排序更受欢迎？

如何分析一个“排序算法”？

1.最好情况、最坏情况、平均情况时间复杂度

2.时间复杂度的系数、常数 、低阶

3.比较次数和交换（或移动）次数

特定算法是依赖特定的数据结构的。我们今天讲的几种排序算法，都是基于数组
实现的。如果数据存储在链表中，这三种排序算法有的可能就不能运行了。

12 | 排序（下）：如何用快排思想在O(n)内查找第K大元素？

归并排序

归并排序使用的就是分治思想。分治，就是分而治之，将一个大问题分解成小的 子问题来解决。小的子问题解决了，大问题也就解决了。
分治思想跟我们前面讲的递归思想很像。分治算 法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两 者并不冲突。

递推公式：

merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：

p >= r 不用再继续分解

第一，归并排序是稳定的排序算法吗？

是。是不是看对两个相同的元素会不会调换顺序。

第二，归并排序的时间复杂度是多少？

在递归那一节我们讲过，递归的适用场景是，一个问题 a 可以分解为多个子问题 b、c，那
求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后，我们再把 b、c 的结果合
并成 a 的结果。
如果我们定义求解问题 a 的时间是 T(a)，求解问题 b、c 的时间分别是 T(b) 和 T( c)，那我
们就可以得到这样的递推关系式：

T(a) = T(b) + T(c) + K

其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。
从刚刚的分析，我们可以得到一个重要的结论：不仅递归求解的问题可以写成递推公式，计算递
归代码的时间复杂度也可以写成递推公式。
通过这个公式，如何来求解 T(n) 呢？还不够直观？那我们再进一步分解一下计算过程。

T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n
......

通过这样一步一步分解推导，我们可以得到 T(n) = 2kT(n/2k)+kn。当 T(n/2^k)=T(1)
时，也就是 n/2^k=1，我们得到 k=log n 。我们将 k 值代入上面的公式，得到
T(n)=Cn+nlog n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归
并排序的时间复杂度是 O(nlogn)。
从我们的原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度
无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间
复杂度都是 O(nlogn)。

第三，归并排序的空间复杂度是多少？

归并排序的时间复杂度任何情况下都是 O(nlogn),但归并排序不是原地排 序算法。
总共需要O(nlogn)的内存空间，但是实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。 那就是，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟
的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临
时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)

快速排序

快排是一种原地、不稳定的排序算法。

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相
反，它的处理过程是由上到下的，先分区，然后再处理子问题。

快排也是用递归来实现的。对于递归代码的时间复杂度，我前面总结的公式，这里也还是适
用的。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间
复杂度递推求解公式跟归并是相同的。所以，快排的时间复杂度也是 O(nlogn)。但如果特别极端的话复杂度有会上升到O(n^2)

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的
缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此，它也没有
快排应用广泛。
快速排序算法虽然最坏情况下的时间复杂度是 O(n^2 )，但是平均情况下时间复杂度都是
O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 O(n^2 ) 的概率非常小，我们可以通
过合理地选择 pivot 来避免这种情况。
若选最后一个数做pivot的话，那么如 果数据原来就是接近有序的，则复杂度会是O(n^2)

13 | 线性排序：如何根据年龄给100万用户数据排序？

今天，我会讲三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序。因
为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear
sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算
法，都不涉及每个元素之间的比较操作。若进行比较的话，下限就是O(nlogn)

桶排序（Bucket sort）

核心思想是将要排序的数据分 到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数 据按照顺序依次取出，组成的序列就是有序的了。
如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个
元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就
是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。
当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的
时间复杂度接近 O(n)。
缺点：
1. 首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺
序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
2. 其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数
据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端
情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

优点：
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较
大，内存有限，无法将数据全部加载到内存中。

例子：
比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排
序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存 中。
我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单
金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里（标准是这个桶的数据可以加载到内存中），第一个 桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内 的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。

计数排序（Counting sort）

原理就是用数组来把要排序的数字大小统计数量
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据
n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数
据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

基数排序（Radix sort）

典型问题：
假设我们有 10 万个手机号码，希望将这 10 万个手机号码 从小到大排序。
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比
较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较
了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排
序的时间复杂度就无法做到 O(n) 了。

14 | 排序优化：如何实现一个通用的、高性能的排序函数？

不知道你有没有发现，使用归并排序的情况其实并不多。归并排序并不是原地排序算法，空间复杂

度是 O(n)。所以，粗略点、夸张点讲，如果要排序 100MB 的数据，除了数据本身占用的
内存之外，排序算法还要额外再占用 100MB 的内存空间，空间耗费就翻倍了。

如何优化快速排序？

如 果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法
就会变得非常糟糕，时间复杂度就会退化为 O(n )
如何选高效的点：
1. 三数取中法。 首 中 尾

char* mid = lo + (size / 2) * width; 这种方法是为了防止两数直接相加时「 上溢出 」

  1. 随机法

不能保证每 次分区点都选的比较好，但从概率上也不会太差

快速排序是用递归来实现的。我们在递归那一节讲过，递归要警惕堆栈溢出。为
了避免快速排序里，递归过深而堆栈过小，导致堆栈溢出，我们有两种解决办法：第一种是
限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。第二种是通过在
堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小
的限制。

Glibc 中的 qsort() 函数：

15 | 二分查找（上）：如何用最省内存的方式实现快速查找功能？

二分查找既可以递归也可以非递归的实现

二分查找的代码实现比较容易写错。你需要着重掌握它的三个容易出错的地方：循环退出
条件、mid 的取值，low 和 high 的更新。

二分查找应用场景的局限性

如果我们的数据集合有频繁的插入和删除操作，要想用二分查找，要么每次插入、删
除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据
集合，无论哪种方法，维护有序的成本都是很高的。
所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变
化的数据集合，二分查找将不再适用。那针对动态数据集合，如何在其中快速查找某个数据
呢？别急，等到二叉树那一节我会详细讲。
* 最后，数据量太大也不适合二分查找。

二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空
间连续，对内存的要求比较苛刻。比如，我们有 1GB 大小的数据，如果希望用数组来存
储，那就需要 1GB 的连续内存空间。

16 | 二分查找（下）：如何快速定位IP对应的省份地址？

二分查找的变形问题很多

变体一：查找第一个值等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) 
        return mid;
      else 
        high = mid - 1;
    }
  }
  return -1;
}

变体二：查找最后一个值等于给定值的元素

跟上面的类似，只是想等时的判断条件不一样

      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;

变体三：查找第一个大于等于给定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

变体四：查找最后一个小于等于给定值的元素

    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }

上一节讲的求“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如今天讲的这几种变体问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。

变体的二分查找算法写起来非常烧脑，很容易因为细节处理不好而产生 Bug，这些容易出错的细节有：终止条件、区间上下界更新方法、返回值选择。

17 | 跳表：为什么Redis一定要用跳表来实现有序集合？

因为二分查找底层依赖的是数组随机访问的特 性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？
实际上，我们只需要对链表稍加改造，就可以支持类似“二分”的查找算法。我们把改造之 后的数据结构叫作跳表（Skip list）
链表加多级索引的结构，就是跳表.

在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构和算法时，我们习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。

如果你了解红黑树、AVL 树这样平衡二叉树，你就知道它们是通过左右旋的方式保持左右子树的大小平衡，而跳表是通过随机函数来维护前面提到的“平衡性”。

跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。
跳表的空间复杂度是 O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，实现要简单多了。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向用跳表。

18 | 散列表（上）：Word文档中的单词拼写检查功能是如何实现 的？

通过散列函数把元素的键值映射为下标，然后将数 据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将 键值转化数组下标，从对应的数组下标的位置取数据。
三点散列函数设计的基本要求：
1. 散列函数计算得到的散列值是一个非负整数；
2. 如果 key1 = key2，那 hash(key1) == hash(key2)；
3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

第三点理解起来可能会有问题，我着重说一下。这个要求看起来合情合理，但是在真实的情
况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。即
便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因
为数组的存储空间有限，也会加大散列冲突的概率。

散列冲突

散列表来源于数组，它借助散列函数对数组这种数据结构进行扩展，利用的是数组支持按照
下标随机访问元素的特性。散列表两个核心问题是散列函数设计和散列冲突解决。
散列冲突 有两种常用的解决方法，开放寻址法和链表法。
散列函数设计的好坏决定了散列冲突的概 率，也就决定散列表的性能。

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
开放寻址法（open addressing）
线性探测方法（Linear Probing） 线性探测每次探测的步长是 1
二次探测（Quadratic probing） 探测的步长就变成了原来的“二次方”
双重散列（Double hashing） 先用第一个散列函数，若冲突，再用第二个散列函数
链表法（chaining）

19 | 散列表（中）：如何打造一个工业级水平的散列表？

散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函 数、装载因子、散列冲突等都有关系。
散列表碰撞攻击：

在极端情况下，有些恶意的攻击者，还有可能通过精心构造的数据，使得所有的数据经过散
列函数之后，都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法，那这个时
候，散列表就会退化为链表，查询的时间复杂度就从 O(1) 急剧退化为 O(n)。
如果散列表中有 10 万个数据，退化后的散列表查询的效率就下降了 10 万倍。更直接点
说，如果之前运行 100 次查询只需要 0.1 秒，那现在就需要 1 万秒。这样就有可能因为查
询操作消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击
（DoS）的目的。这也就是散列表碰撞攻击的基本原理。

如何设计散列函数？

  1. 散列函数的设计不能太复杂。过于复杂的散列函数，势必会消耗很多计算时间，也就 间接的影响到散列表的性能。
  2. 散列函数生成的值要尽可能随机并且均匀分布，这样才 能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不 会出现某个槽内数据特别多的情况。

装载因子过大了怎么办？

插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，散列表
装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数
据，所以时间复杂度是 O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就 是 O(1)。
* 动态缩 容
对于动态散列表，随着数据的删除，散列表中的数据会越来越少，空闲空间会越来
越多。如果我们对空间消耗非常敏感，我们可以在装载因子小于某个值之后，启动动态缩 容。
当然，如果我们更加在意执行效率，能够容忍多消耗一点内存空间，那就可以不用费劲 来缩容了。

装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很 高，可以降低负载因子的阈值；
相反，如果内存空间紧张，对执行效率要求又不高，可以增 加负载因子的值

如何避免低效地扩容？

为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批 完成。
1.达到阈值时申请空间
2.插入新数据时插到新空间，并把一部分旧数据搬移到新空间直到旧空间中的搬完
3.查找时先从新散列表中查找，如果没有找到，再去老的散列表中查找。

如何选择冲突解决方法？

开放寻址法和链表法。
这两种冲突解决办 法在实际的软件开发中都非常常用。比如，Java 中 LinkedHashMap 就采用了链表法解决
冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。

1.开放寻址法

优点：
1.散列表中的数据都存储在数组中，可以有效地利 用 CPU 缓存加快查询速度。
2.序列化起来比较简单。链表法 包含指针，序列化起来就没那么容易。
缺点：
删除数据的时候比较麻烦，需要特殊标 记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表
法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能 太大。这也导致这种方法比链表法更浪费内存空间。
适用场景：
当数据量比较小、装载因子小的时候，适合采用开放寻址法。

2. 链表法

优点：
* 链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，
并不需要像开放寻址法那样事先申请好。这一点也是我们前面讲过的链表优于数组 的地方。
* 链表法比起开放寻址法，对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于 1
的情况。接近 1 时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下
降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就
是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

缺点：
* 链表因为要存储指针，所以对于比较小的对象的存 储，是比较消耗内存的
* 链表中的结点是零散分 布在内存中的，不是连续的，所以对 CPU 缓存是不友好的，这方面对于执行效率也有一定 的影响

适用场景：

比较适合存储大对象、大数据量的散列 表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

工业级散列表举例分析

以Java 中的 HashMap为例

  1. 初始大小
    HashMap 默认的初始大小是 16，当然这个默认值是可以设置的

  2. 装载因子和动态扩容
    最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示
    散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。

  3. 散列冲突解决方法
    HashMap 底层采用链表法来解决冲突。而当链表 长度太长（默认超过 8）时，链表就转换为红黑树。
    我们可以利用红黑树快速增删改查的特 点，提高 HashMap 的性能。

  4. 散列函数

int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capitity -1); //capicity 表示散列表的大小
}

20 | 散列表（下）：为什么散列表和链表经常会一起使用？

LRU 缓存淘汰算法

通过散列表和双向链表的组合使用，可以实现了一个高效的、支持 LRU 缓存淘汰算法的缓存系统原型。
其中查找、删除和添加都可以在O(1)的时间完成

Redis 有序集合

Redis 有序集合的操作如下：
添加一个成员对象；
按照键值来删除一个成员对象；
按照键值来查找一个成员对象；
按照分值区间查找数据，比如查找积分在 [100, 356] 之间的成员对象；
按照分值从小到大排序成员变量；

如果我们仅仅按照分值将成员对象组织成跳表的结构，那按照键值来删除、查询成员对象就
会很慢，解决方法与 LRU 缓存淘汰算法的解决方法类似。我们可以再按照键值构建一个散
列表，这样按照 key 来删除、查找一个成员对象的时间复杂度就变成了 O(1)。同时，借助
跳表结构，其他操作也非常高效。

Java LinkedHashMap

LinkedHashMap 是通过双向链表和散列表这两种数据结构 组合实现的。
LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表 法解决散列冲突。

为什么散列表 和链表经常一块使用？
散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据
都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按照某种顺序快速地遍历数
据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，
然后排序，再遍历。
因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散
列表中的数据的时候，都需要先排序，那效率势必会很低。为了解决这个问题，我们将散列
表和链表（或者跳表）结合在一起使用。

21 | 哈希算法（上）：如何防止数据库中的用户信息被脱库？

将任意长度的二进制值串映 射为固定长度的二进制值串，这个映射的规则就是哈希算法
哈希算法的应用非常非常多，我选了最常见的七个，分别是
* 安全加密、
* 唯一标识、
* 数据校验、
* 散列函数、
* 负载均衡、
负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话 粘滞（session sticky）的负载均衡算法呢？
也就是说，我们需要在同一个客户端上，在一 次会话中的所有请求都路由到同一个服务器上。
我们可以通过哈希算法，对客户端IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最
终得到的值就是应该被路由到的服务器编号。 这样，我们就可以把同一个 IP 过来的所有请 求，都路由到同一个后端服务器上
* 数据分片
基本思路是把一个很大的数据量根据机器数量分成多分，然后计算其hash，模上机器数量，再分配到对应的机器上
1.如何统计“搜索关键词”出现的次数？
2.如何快速判断图片是否在图库中？
* 分布式存储
一致性哈希算法,如何把key均匀的分配到分布的不同节点上

23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储？

前序：
preOrder(r) = print r + preOrder(r->left) + preOrder(r->right)
中序：
inOrder(r) = inOrder(r->left) + print r + inOrder(r->right)
后序：
postOrder(r) = postOrder(r->left) + postOrder(r->right) + print r

24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉 树？

散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。
而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度 才是 O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢？
我认为有下面几个原因：
1. 第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二
叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序 列。
2. 第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能
不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
3. 第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的
存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈
希函数的耗时，也不一定就比平衡二叉查找树的效率高。
4. 第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲
突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题
的解决方案比较成熟、固定。
5. 最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲
突的散列表，不然会浪费一定的存储空间。

25 | 红黑树（上）：为什么工程中都用红黑树这种二叉树？

26 | 红黑树（下）：掌握这些技巧，你也可以实现一个红黑树

27 | 递归树：如何借助树来求解递归算法的时间复杂度？

实战一：分析快速排序的时间复杂度
实战二：分析斐波那契数列的时间复杂度
实战三：分析全排列的时间复杂度

28 | 堆和堆排序：为什么说堆排序没有快速排序快？

第一点，堆排序数据访问的方式没有快速排序友好。比如下面这个例子，对堆顶节点进行堆化，
会依次访问数组下标是 的元素，而不是像快速排序那样，局部顺序访问，所 以，这样对 CPU 缓存是不友好的。
第二点，对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。
比如，对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。

29 | 堆的应用：如何快速获取到Top 10最热门的搜索关键词？

30 | 图的表示：如何存储微博、微信等社交网络中的好友关系？

31 | 深度和广度优先搜索：如何找出社交网络中的三度好友关系？

32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹 配？

33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？

34 | 字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法？

35 | Trie树：如何实现搜索引擎的搜索关键词提示功能？

36 | AC自动机：如何用多模式串匹配实现敏感词过滤功能？

37 | 贪心算法：如何用贪心算法实现Huffman压缩编码？

38 | 分治算法：谈一谈大规模计算框架MapReduce中的分治思想

39 | 回溯算法：从电影《蝴蝶效应》中学习回溯算法的核心思想

40 | 初识动态规划：如何巧妙解决“双十一”购物时的凑单问题？

41 | 动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和 重复子问题

42 | 动态规划实战：如何实现搜索引擎中的拼写纠错功能？

43 | 拓扑排序：如何确定代码源文件的编译依赖关系？

44 | 最短路径：地图软件是如何计算出最优出行路径的？

45 | 位图：如何实现网页爬虫中的URL去重功能？

46 | 概率统计：如何利用朴素贝叶斯算法过滤垃圾短信？

  1. 基于黑名单的过滤器
  2. 基于规则的过滤器
  3. 基于概率统计的过滤器
    这种基于概率统计的过滤方式，基础理论是基于朴素贝叶斯算法。

47 | 向量空间：如何实现一个简单的音乐推荐系统？

实际上，要解决这个问题，并不需要特别高深的理论。解决思路的核心思想非常简单、直
白，用两句话就能总结出来。
* 找到跟你口味偏好相似的用户，把他们爱听的歌曲推荐给你；
* 找出跟你喜爱的歌曲特征相似的歌曲，把这些歌曲推荐给你。

  1. 基于相似用户做推荐
    用欧几里得距离是用来计算两个向量 之间的距离的。
  2. 基于相似歌曲做推荐

48 | B+树：MySQL数据库索引是如何实现的？

49 | 搜索：如何用A*搜索算法实现游戏中的寻路功能？

50 | 索引：如何在海量数据中快速查找某个数据？

51 | 并行算法：如何利用并行处理提高算法的执行效率？