数据结构和算法大全（上）

我一直认为，数据结构和算法是程序员的灵魂，哪怕换了n多的框架，甚至是换了语言，当然也有人说设计模式是程序员的血肉，这个我也赞同、

1、复杂度分析

数据结构和算法本身是为了解决块和省的问题，代码如何运行的更快，如何让代码更省存储空间，执行效率是算法一个非常重要的考量指标。

大O复杂度表示法

T(n) = O (f(n))

T(n)代表代码执行的总时间，n代表的数据量，f(n)代表的是每行代码执行的次数总和。

大O复杂度表示方法只是一种变化趋势，通常我们会忽略掉公式中的常量，低阶，系数，只需要几类一个最大阶的量级就可以了。

如何分析一段程序的复杂度，一般有三种比较实用的方法

只关注循环执行次数最多的一段代码
加法法则，总的复杂度等于量级最大的那段代码的复杂度。
乘法法则，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

常见的时间复杂度大概有以下几种，常量阶O(1),对数阶O(logn),线性阶O(n),线性对数阶O(nlogn),平方节O(n2)等

空间复杂度比时间复杂度要简单很多，大概有以下几种，O(1),O(n),O(n2)。

最好，最坏情况时间复杂度分析，就是分析程序的极端场景，最好场景是复杂度是多少，最坏场景复杂度是多少。

平均情况时间复杂度分析，就是每种情况乘以发生概念相加之后再除以情况总数。

均摊时间复杂度，其实就是在程序中，如果出现两个操作执行数量一致，一个耗时多，一个耗时少，两者可以均摊来计算时间复杂度。

2、数据结构

2.1、数组

定义，数组是一种线性表数据结构，用一组连续的内存空间，存储一组具有相同类型的数据。

数据由于线性表和连续的内存空间要求，让它具备了随机访问的特性，但是对于删除，插入则效率就会低很多。

提到数据不得不提到java语言的容器 ArrayList，是否可以完全替代数据，ArrayList的底层实现就是数据，但是ArrayList在上层做了动态扩容，扩容比例是1.5,扩容的时候涉及到了内存申请和数据搬移，就会比较浪费时间。

数组和容器最大的一个使用区别在于，数据可以存放基本类型，但是容器只能存储基本类型对应的包装类，在自动拆箱和装箱这个过程中，比较耗费时间。

2.2、链表

定义，链表通过指针（引用）将一组零散的内存块串联到一起，每一个内存块称之为节点，每个节点上不仅要存储数据，还有记录下一个节点的地址。

链表有很多中表现形式，比如单向链表，双向链表，循环链表，双向循环链表等。

和数组比较起来，链表由于特殊的数据结构，在插入，删除方面的性能很高，只需要修改指针即可，垃圾回收交给GC。

但是查找，遍历就会很麻烦，这块可能会有一个考虑的点，数据和链表都是遍历的话，都是从头结点到查找的那个点，时间不应该一样么？其实是不一样的，现代计算机为了弥补cpu和内存之间的速度差异，每次从内存中获取数据，取得不是一个点，而是一个块，也就是我要取值得前后都会直接缓存起来，数组是连续的，所以可能每十个点才去内存中去一次，但是链表可能就是每次都去，所以，数组遍历的耗时要比链表少得多。

如何实现LUR缓存淘汰算法

首先，都知道缓存是一种提高数据读取的技术，往往web服务的性能瓶颈在数据库这块，缓存使用的是内存，内存是很宝贵的，当缓存空间满的时候，哪些数据应该清理，就需要指定缓存策略，常见的策略有三种，先进先出策略（FIFO），最少使用策略（LFU），最近最少使用策略（LUR）。

链表如何实现呢，比如我们维护一个有序的单链表，越靠近链表尾部是越早放完的，当一个新的数据被访问的时候，我们从链表头开始顺序遍历链表，有两种情况

数据存在，找到这个数据，删除，插入到头部。
数据不存在，链表已满，删除尾部节点，将数据插入头部节点，链表未满，将数据直接插入头部。

其实还有点问题，比如，缓存访问的时间复杂度是O(n)，必须把缓存访问的时间复杂度降级，可以引入散列表来记录缓存位置，就可以降低访问复杂度了。

2.3、栈

定义，关于“栈”，我有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”。

栈的底层可以用数组，也可以用链表，它隐藏了很多操作，只对外提供了头部访问的方式，时间复杂度，空间复杂度都是很低。

栈的应用场景

浏览器的前进后退，就可以用栈实现，维护了两个栈。
比如括号校验，使用栈来做。
比如算法表达式的操作系统内部实现。

内存中的堆栈和这个栈不是一个概念，内存中是实实在在存在存储，物理区，存储着运行方法的形参，局部变量，返回值等。

2.4、队列

队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”，队列经常和栈做比较，我们知道，栈只支持两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

跟栈不一样的地方在于，队列是先进先出的，所以，在存储这块就会出现，站位后移的情况，如果用数组的话就可以使用数据搬移，设计的时候，其实可以做成当空间满的时候，在进行搬移，空间不满直接用就可以了。

换一种，换一个思路，如果采用循环链表呢，就省去了搬移的过程，但是需要加上判断条件，队列空的条件头等于尾，队列满的条件，尾加上1 除以总个数取余等于头。

队列的使用场景

阻塞队列和并发队列，阻塞队列就是在队列的基础上加了阻塞操作，队列为空的时候，对头取数据就会阻塞，队列满的时候，插入数据会阻塞。

并发队列最简单的操作，在进入队列，和出队列的时候增加同步锁，就可以实现，但是效率会很多，其实大部分项目中采用的是CAS原子操作。

入队前获取tail位置，入队比较尾部位置是否变化，没有变化则入队，否则不入队，出队则是获取头部位置，就行cas。

2.5、跳表

对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是O(n)。

对链表建立一级“索引”，查找起来是不是就会更快一些呢？每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引或索引层。

建立更多的索引层，指导可以快速检索到相应位置的值即可。

空间复杂度是o(n),查找的时间复杂度则是 o(logn)，用空间换时间的做法。

redis中的有序集合的底层实现之一就是使用的跳表。

跳表比别的数据结构很大的优势在于，可以使用区间查找。

2.6、散列表

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

散列函数设计的三个原则

散列函数计算得到的散列值是一个非负整数；
如果key1 = key2，那hash(key1) == hash(key2)；
如果key1 ≠ key2，那hash(key1) ≠ hash(key2) .

如何解决散列冲突问题

1、开发寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？我先讲一个比较简单的探测方法，线性探测（Linear Probing）。

2、链表法

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。在散列表中，每个“桶（bucket） ”或者“槽（slot） ”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

求得hash值，找到索引位置之后，对应的是一个链表。java中hashmap采用的就是这个思想，在javaz8之后，一定长度的散列表会转换成红黑色来实现，效率更高，但那样，也意味着hash冲突很多了。

散列表的用法：

1、 word中的单词拼接检索，将所有的单词放入散列表中，拼写一个单词，生成hash值到散列表中求值，如果找不到则认为拼写错误。

2、LUR缓存淘汰算法，单纯使用链表的话，淘汰算法的时间复杂度是O(n)，但是如果加上散列表的加持，时间复杂度就可以降低到O(1).

2.7、二叉树

“树”这种数据结构真的很像我们现实生活中的“树”，这里面每个元素我们叫作“节点”；用来连线相邻节点之间的关系，我们叫作“父子关系”。

树中的其他三个概念

节点的高度，节点到叶子节点的长度。
节点的深度，根节点到这个节点所经历的边的个数。
节点的层数，节点的深度+1
树的高度，根节点的高度。

二叉树的概念，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

满二叉树，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

完全二叉树，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

二叉树的遍历，共有三种方法

前序遍历，先打印当前节点，在打印左节点，在打印右节点
中序遍历，先打印左节点，再打印中间节点，再打印右节点
后续遍历，先打印左节点，再打印右节点，最后打印中间节点。

2.8、二叉查找树

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。

这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉树的查找操作：

我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

二叉树的插入操作：

新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

二叉树的删除操作：

第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为null。比如图中的删除节点55。

第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。

第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。

2.9、红黑树

平衡二叉树定义：二叉树中任意一个节点的左右子树的高度相差不能大于1。

红黑树的定义：

根节点是黑色的；
每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

2.10、递归树

递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作递归树。

2.11、堆

堆是一种特殊的树。我们现在就来看看，什么样的树才是堆。我罗列了两点要求，只要满足这两点，它就是一个堆。

堆是一个完全二叉树；
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。

3、操作

3.1、递归操作

递归是一种应用非常广泛的算法（或者编程技巧）。之后我们要讲的很多数据结构和算法的编码实现都要用到递归，比如DFS深度优先搜索、前中后序二叉树遍历等等。所以，搞懂递归非常重要，否则，后面复杂一些的数据结构和算法学起来就会比较吃力。

递归是一个很标准的求解分解过程，去的过程就是递，回来的过程就是归，基本上，所有的递归都可以使用递推公式来表示。

递归需要满足三个条件

一个问题的解可以分解成几个子问题的解
这个问题和分解之后的子问题，除了数据规模不同，求解思路完全一样。
存在递归终止条件、

4、排序算法

4.1、冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡操作，所以最坏情况时间复杂度为O(n2)。

4.2、插入排序

一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，我们只要遍历数组，找到数据应该插入的位置将其插入即可。

我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个原地排序算法。

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为O(n)。注意，这里是从尾到头遍历已经有序的数据。

4.3、选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

选择排序空间复杂度为O(1)，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n2)。

选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性，稳定性指的是就是相同元素在经过排序之后顺序不变。

4.4、归并排序

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

归并排序最好的解决思路就是使用递归的方式，写递归重要的就在于推导出递归公式，找到终止条件。

递归公式是：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件，当p > r 的时候就终止。

merge_sort(p…r)表示，给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问题， merge_sort(p…q)和merge_sort(q+1…r)，其中下标q等于p和r的中间位置，也就是(p+r)/2。当下标从p到q和从q+1到r这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从p到r之间的数据就也排好序了。

4.5、快速排序

快排的思想是这样的：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。

根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。

推导公式：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)

终止条件：p >= r

4.6、桶排序

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

如果要排序的数据有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)。

4.7、计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

比如高考分数，几十万人但是之后750分，就可以分为750个桶，排名就出来了。

4.8、基数排序

假设要比较两个手机号码a， b的大小，如果在前面几位中， a手机号码已经比b手机号码大了，那后面的几位就不用看了。

先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过11次排序之后，手机号码就都有序了。

5、查找算法

5.1、二分查找

二分查找是一种非常简单易懂的快速查找算法，生活中到处可见。比如说，我们现在来做一个猜字游戏。我随机写一个0到99之间的数字，然后你来猜我写的是什么。猜的过程中，你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。

O(logn)惊人的查找速度，前提这个数组必须是有序的，否则二分查找无法使用。

二分查找的限制

依赖的必须是数组，因为数组有随机访问，链表则不行。
二分查找的前提是必须是有序的数组。

二分查找的一些变形问题

查找第一个值等于给定值的元素
查找最后一个值等于给定值的元素
查找第一个大于等于给定值的元素
查找最后一个小于等于给定值的元素

解题思路和二分查找一样，只不过在找到之后，往前或者往后进行判断，终止条件是前面的或者后面的这个元素小于或者大于给定值即可。

6、算法

6.1、hash算法

哈希算法的定义和原理非常简单，基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

哈希算法应该有以下特点

从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同；
散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

hash算法的应用场景

安全加密，最常用于加密的哈希算法是MD5（MD5 Message-Digest Algorithm， MD5消息摘要算法）和SHA（Secure Hash Algorithm，安全散列算法）。
唯一标示，如果要在海量的图库中，搜索一张图是否存在，我们不能单纯地用图片的元信息（比如图片名称）来比对，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取100个字节，从中间取100个字节，从最后再取100个字节，然后将这300个字节放到一块，通过哈希算法（比如MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。
数据校验，我们通过哈希算法，对100个文件块分别取哈希值，并且保存在种子文件中。我们在前面讲过，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。
散列函数，散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过，相对哈希算法的其他应用，散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，我们都可以通过开放寻址法或者链表法解决。
负载均衡，负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。我们可以通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这样，我们就可以把同一个IP过来的所有请求，都路由到同一个后端服务器上。
数据分片，为了提高处理的速度，我们用n台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟n取模，最终得到的值，就是应该被分配到的机器编号。这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。
分布式存储，将数据分布到多台缓存服务器上，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。

一致性hash算法

假设我们有k个机器，数据的哈希值的范围是[0, MAX]。我们将整个范围划分成m个小区间（m远大于k），每个机器负责m/k个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。

希罗卡

数据结构与算法大全（上）