1 基本概念
1.1 定义
程序=数据结构+算法
数据结构=结构定义+结构操作
算法是以简单概念的形式对如何解决问题的一种精确描述。
1.2 算法复杂度
1.2.1 时间复杂度
（1）大O符号表示法
公式为 T(n) = O( f(n) )，全称是：算法的渐进时间复杂度。 其中： T表示代码执行的时间； n表示数据规模的大小; f(n) 表示每行代码执行次数之和; O 表示代码的执行时间T(n)与f(n)表达式成正比。
使用大O符号表示法分享下面代码
int cal(int n) {int sum = 0;int i = 1;int j = 1;for (; i <= n; ++i) {j = 1;for (; j <= n; ++j) {sum = sum + i * j;}}}
假设每行代码执行的时间都一样，为unit_time。那第2、3、4行代码，每行都需要1个unit_time的执行时间，第5、6行代码循环执行了n遍，需要2nunit_time的执行时间，第7、8行代码循环执行了n2遍，所以需 要2n2 unit_time的执行时间。所以，整段代码总的执行时间T(n) = (2n2+2n+3)*unit_time。带入公式就是T(n) = O(2n2+2n+3)。当n很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。替换成大O符号表示法为T(n) = O(n2)。
（2）时间复杂度分析
分析方法
- 只关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
最好、最坏、平均、均摊时间复杂度
- 最好情况时间复杂度
- 最坏情况时间复杂度
- 平均情况时间复杂度
- 均摊时间复杂度
（3）时间复杂度量级
O(1) 常量阶
1.2.2 空间复杂度
void print(int n) {
int i = 0;
int[] a = new int[n];
...
}
第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。
常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。
2 数据结构
2.1 数组
结构定义
数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
结构操作
数组拥有连续的内存空间、相同的数据，所以数组可以随机访问，但对数组进行删除插入，为了保证数组的连续性，就要做大量的数据搬移工作
（1）插入/删除
插入在末尾最好O(1) ，在开始最坏O(n) ，平均O(n)
数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把新的元素，插入到第k个位置，此处复杂度为O(1)。
删除在末尾最好O(1) ，在开始最坏O(n) ，平均O(n)
多次删除集中在一起，提高删除效率；记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。
（2）查询
根据下标随机访问数组元素。寻址公式：a[i]_address = base_address + i * data_type_size
代码实现练习
（1）一个支持动态扩容的数组
- 根据数据结构和操作定义数组属性和方法（还可以根据需要添加其余方法，如根据元素返回下标等），即 ```java private int size;//数组大小 private T[] data;//数据存放
public void add(int index, T e) //添加 public T remove(int index)//移除 public void set(int index,T e) //添加修改 public T get(int index) //查询
2. 数组实现后补充扩容方法
数据的扩容就是创建新的数组据把原来数组的数据复制到新数组中<br />核心方法 ：public static void **arraycopy**(Object src,int srcPos,Object dest,int destPos, int length)<br />其中：src表示源数组，srcPos表示源数组要复制的起始位置，desc表示目标数组，length表示要复制的长度。
3. [完整实现代码](https://gitee.com/baozikun/data-structure-and-algorithm/blob/master/src/main/java/com/baozikun/datastructureandalgorithm/datastructure/ch01_array/DynamicExpansionArray.java)
（2）一个支持动态扩容的数组
1. 根据数据结构和操作定义属性和方法（按题目要求只实现了增加和删除）
1. [完整实现代码](https://gitee.com/baozikun/data-structure-and-algorithm/blob/master/src/main/java/com/baozikun/datastructureandalgorithm/datastructure/ch01_array/OrderArray.java)
（3）两个有序数组合并为一个有序数组
1. 实现思路
- 将 nums2 中的元素全部插入到 nums1 的尾部，然后对处理之后的 nums1 进行排序。
- **双指针法**，先开辟一个新数组，长度为两个数组的长度之和，然后让两个指针分别指向两个数组的头部，比较这个两个指针指向的数组元素的值，将数值较小的放到新数组的头部，再将指向的数值较小的指针右移，继续比较，直到遍历完其中一个数组即可。
2. [完整实现代码](https://gitee.com/baozikun/data-structure-and-algorithm/blob/master/src/main/java/com/baozikun/datastructureandalgorithm/datastructure/ch01_array/MergeOrderArray.java)
<a name="VVhsR"></a>
### 2.2 链表
**结构定义**<br />链表是一种**线性表**数据结构。存储结构是非连续、非顺序的，链表的**结点**间通过指针相连，每个结点只对应有一个前驱结点和一个后继结点。
- 单链表，尾节点后继指针指向null。
- 循环链表，尾节点后继指针指向头结点，适合处理具有环型结构的数据，如约瑟夫问题。
- 双向链表，每个结点不止有一个后继指针next指向后面的结 点还有一个前驱指针pre指向前面的结点，比起单链表更加高效但消耗的资源也更多。
**结构操作**<br />（1）插入/删除<br />针对链表的插入和删除操作，只需要考虑相邻结点的指针改变，所以对应的时间复杂度是O(1)。<br />（2）查询<br />因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过 寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点，需要O(n)的时间复杂度。<br />**代码实现练习**
> 技巧：
> 1.理解指针或引用的含义
> 2.警惕指针丢失和内存泄漏（java无需考虑） ：一般先操作后结点在处理前结点
> 3.利用哨兵简化实现难度：有哨兵结点的链表叫带头链表
> 4.重点留意边界条件处理 ：（链表为空，包含一个结点，表只包含两个结点，在处理头结点和尾结点）
（1）实现单链表
1. 根据数据结构和操作定义带头结点链表的属性和方法(添加、删除、反转等)
```java
public class SinglyLinkedList<T> {
private final Node<T> head = new Node<>(null, null);
public int size;
public void add(T e){}
public void remove(T e){}
public Node<T> findByValue(T value)
...
public static class Node<T>{
private final T data;
private Node<T> next;
...
}
}
- 思路
- 定义一个头结点head作为单链表的头不存放数据
- 通过辅助结点temp来帮助遍历链表，如果结点中的next不为空即未到达链尾
- 注意点：
- 添加需要把链尾结点的next指向新节点；
- 删除因为单向链表只能单向遍历，而且切断引用不能使用当前结点判断。所以要从前一个结点判断，当temp.next结点为要删除结点的时候，更改temp的next指向temp.next的next，即temp.next=temp.next.next。一定要注意要有删除标记boolean flag = false;
- 翻转（非递归法）
- 初始化pre和cur指针分别指向头节点和头节点的下一个节点
- 使用三指针法(带头节点链表要四指针)反转链表主题部分
- 将头节点的指针指向nulll
- 实现求链表的中间结点
- 定义两个指针fast和slow。slow一次遍历一个节点，fast一次遍历两个节点，由于fast的速度是slow的两倍，所以当fast遍历完链表时，slow所处的节点就是链表的中间节点。
（3）实现单向循环链表
- 带头节点的单向循环链表（尾节点下一个为头节点）
约瑟夫环（暴力循环）
-
2.3 栈
结构定义
栈是一种“操作受限”的线性表，只允许在一端插入和删除数据，并且满足后先进后出的特性。
结构操作
（1）入栈
入栈后，在栈顶加入一个元素，栈顶指针上移一个单元
（2）出栈
出栈后，在栈顶删除一个元素，栈顶指针下移一个单元
代码实现练习
（1）用数组实现一个顺序栈 定义栈顶指针指向栈顶，添加或者删除移动指针
private String[] items; private int stackTop;//栈顶指针 private int size; public boolean push(String item){} public String pop() {}
（2）用链表实现一个链式栈
- 与数组类似，栈顶指针更换为结点的引用
- 完整实现代码
（3）编程模拟实现一个浏览器的前进、后退功能
2.4 队列
结构定义
队列也是一种“操作受限”的线性表，它只允许在队头进行删除操作，而在表的队尾进行插入操作，满足后先进先出的特性。
结构操作
（1）入队
（2）出队
代码实现练习
（1）用数组实现一个顺序队列
定义头指针指向队首、尾指针指向队尾，添加或者删除移动对应的指针
private String[] items; private int capacity; private int head; private int tail; public boolean enqueue(String item) {} public String dequeue() {}
（2）用链表实现一个链式队列
- 与数组类似，栈顶指针更换为结点的引用
- 完整实现代码
（3）实现一个循环队列
2.5 跳表
一、什么是跳表？
为一个值有序的链表建立多级索引，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示down指
针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。
二、跳表的时间复杂度？
1.计算跳表的高度
如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推
，第k级索引的节点个数就是n/(2^k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2^h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度
就是log2n。
2.计算跳表的时间复杂度
假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m*logn)。那这个m是多少呢？如下图所
示，假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-
1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每一级索引都最多只需要
遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是O(logn)。
三、跳表的空间复杂度及如何优化？
1.计算索引的节点总数
如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和n-1
，所以跳表的空间复杂度为O(n)。
2.如何优化时间复杂度
如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以3为例）：n/3，n/9，n/27，…，27，9，3，
1，等比数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取一次相比，时间复杂度要低不少呢。
四、高效的动态插入和删除？
跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操
作比较费时，但在跳表中这个查找操作的时间复杂度是O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是O(logn)。
五、跳表索引动态更新？
当往跳表中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，那么如何选择这个索引层呢？可以通过随机函数来决定将这个节点插入到哪几
级索引中，比如随机函数生成了值K，那就可以把这个节点添加到第1级到第K级索引中。
2.6 散列表
一、散列表的由来？
1.散列表来源于数组，它借助散列函数对数组这种数据结构进行扩展，利用的是数组支持按照下标随机访问元素的特性。
2.需要存储在散列表中的数据我们称为键，将键转化为数组下标的方法称为散列函数，散列函数的计算结果称为散列值。
3.将数据存储在散列值对应的数组下标位置。
二、如何设计散列函数？
总结3点设计散列函数的基本要求
1.散列函数计算得到的散列值是一个非负整数。
2.若key1=key2，则hash(key1)=hash(key2)
3.若key≠key2，则hash(key1)≠hash(key2)
正是由于第3点要求，所以产生了几乎无法避免的散列冲突问题。
三、散列冲突的解放方法？
1.常用的散列冲突解决方法有2类：开放寻址法（open addressing）和链表法（chaining）
2.开放寻址法
①核心思想：如果出现散列冲突，就重新探测一个空闲位置，将其插入。
②线性探测法（Linear Probing）：
插入数据：当我们往散列表中插入数据时，如果某个数据经过散列函数之后，存储的位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有
空闲位置，直到找到为止。
查找数据：我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素是否相等，若相等，则说明就是我
们要查找的元素；否则，就顺序往后依次查找。如果遍历到数组的空闲位置还未找到，就说明要查找的元素并没有在散列表中。
删除数据：为了不让查找算法失效，可以将删除的元素特殊标记为deleted，当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来，而是继续往
下探测。
结论：最坏时间复杂度为O(n)
③二次探测（Quadratic probing）：线性探测每次探测的步长为1，即在数组中一个一个探测，而二次探测的步长变为原来的平方。
④双重散列（Double hashing）：使用一组散列函数，直到找到空闲位置为止。
⑤线性探测法的性能描述：
用“装载因子”来表示空位多少，公式：散列表装载因子=填入表中的个数/散列表的长度。
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
3.链表法（更常用）
插入数据：当插入的时候，我们需要通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即可，所以插入的时间复杂度为O(1)。
查找或删除数据：当查找、删除一个元素时，通过散列函数计算对应的槽，然后遍历链表查找或删除。对于散列比较均匀的散列函数，链表的节点个数k=n/
m，其中n表示散列表中数据的个数，m表示散列表中槽的个数，所以是时间复杂度为O(k)。
面试题目：如何设计一个工业级的散列函数？
思路：
何为一个工业级的散列表？工业级的散列表应该具有哪些特性？结合学过的知识，我觉的应该有这样的要求：
1.支持快速的查询、插入、删除操作；
2.内存占用合理，不能浪费过多空间；
3.性能稳定，在极端情况下，散列表的性能也不会退化到无法接受的情况。
方案：
如何设计这样一个散列表呢？根据前面讲到的知识，我会从3个方面来考虑设计思路：
1.设计一个合适的散列函数；
2.定义装载因子阈值，并且设计动态扩容策略；
3.选择合适的散列冲突解决方法。
2.7 树
2.7.1 树的常用概念
树：是由根节点和若干棵子树构成的的非线性存储结构。
节点：树中的每个元素称为节点。
根节点：没有父节点的节点。
叶子节点：没有子节点的节点。
父子关系：相邻两节点的连线，称为父子关系。
兄弟关系：具有相同父节点的多个节点称为兄弟关系。
节点的高度：节点到叶子节点的最长路径所包含的边数。
节点的深度：根节点到节点的路径所包含的边数。
节点的层数：节点的深度+1（根节点的层数是1）。
2.7.1 二叉树
二叉树：每个节点最多只有2个子节点的树，这两个节点分别是左子节点和右子节点。
满二叉树：除了叶子节点外，每个节点都有左右两个子节点。
完全二叉树：叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。
2.7.2 二叉树储存
一种是基于指针或者引用的二叉链式存储法
每个节点由3个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。
这种存储方式比较常用，大部分二叉树代码都是通过这种方式实现的。
一种是基于数组的顺序存储法
用数组来存储，对于完全二叉树，如果节点X存储在数组中的下标为i，那么它的左子节点的存储下标为2i，右子节点的下标为2i+1，反过来，下标i/2位置
存储的就是该节点的父节点。注意，根节点存储在下标为1的位置。完全二叉树用数组来存储时最省内存的方式。
2.7.3 二叉树遍历
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
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
3种遍历方式中，每个节点最多会被访问2次，所以时间复杂度是O(n)
代码：
2.7.4 二叉查找树
二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大
于这个节点的值。
2.8 堆
2.9 图
3 算法
3.1 递归
3.1.1 递归是什么
- 方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归 。
- 基本上，所有的递归问题都可以用递推公式来表示，比如 f(n) = f(n-1) + 1; f(n) = f(n-1) + f(n-2);
- 优缺点：
优点：代码的表达力很强，写起来简洁。
缺点：空间复杂度高、有堆栈溢出风险（ 可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出 ）、存在重复计算（ 可以通过某种数据结构来保存已经求解过的值，从而避免重复计算 ）、过多的函数调用会耗时较多等问题。
3.1.2 递归可以处理的问题
1.问题的解可以分解为子问题（数据规模更小的问题2）的解。
2.问题与子问题，求解思路完全一样
3.存在递归终止条件
3.1.2 递归的实现
理解：找到如何将大问题分解为小问题的规律（屏蔽掉递归细节），并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
例子： 假如这里有n个台阶，每次你可以跨1个台阶或者2个台阶，请问走这n个台阶有多少种走法？
int f(int n) {
if (n == 1) return 1;//终止条件
if (n == 2) return 2;//终止条件
return f(n-1) + f(n-2);//递推公式
}
3.2 排序算法
比较类排序：通过元素之间的比较来确定位置。适用于一切需要排序的情况。
非比较类排序：通过制定规则来确认元素位置。需要占用空间来确定唯一位置，对数据规模和数据分布有一定的要求。
| 名称 | 平均 | 最好 | 最坏 | 额外空间 | 是否原地 | 是否稳定 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | √ | √ |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | √ | √ |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | √ | √ |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | × | √ |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn) | √ | × |
| 希尔排序 | O(n步长) | O(n) | O(n2) | O(1) | √ | × |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | √ | × |
| 桶排序 | O(n + k) | O(n) | O(n + k) | O(n + k) | × | √ |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | × | √ |
| 基数排序 | O(n * k) | O(n + k) | O(n + k) | O(n + k) | × | √ |
注：k是数据范围
原地排序：在排序过程只利用原来存储待排数据的存储空间进行比较和交换的数据排序
稳定排序：经过排序之后，相等元素之间原有的先后顺序不变
3.2.1 冒泡排序
思路
- 每次冒泡操作（里层循环）都会对相邻的两个元素进行比较 ， 一次冒泡后最大的元素将移动到数组最后
- 排除掉数据最后一个元素，进行下一次冒泡，重复进行（外层循环）
- 当某次冒泡操作没有数据交换 ，即可跳出
实现//第一趟排序，就是将最大的数排在倒数第一位 for (int j = 0; j < arr.length - 1; j++) { if (a[j] > a[j + 1]) { //比较 ...//交换 } } //在第一次冒泡完成后，最后一个元素就不需要在参与冒泡，以此类推 for (int j = 0; j < arr.length - 1 - 1; j++) for (int j = 0; j < arr.length - 1 - 2; j++)
https://gitee.com/baozikun/data-structure-and-algorithm/blob/master/src/main/java/com/baozikun/datastructureandalgorithm/datastructure/ch05_sorts/BubbleSort.java
3.2.2 插入排序
3.2.3 选择排序
思路
假定数组的第一个元素为最小，记录其下标与值；
比较其下一个元素，如果值比假定的值小则交换；
循环上一过程，找出最小值（内层循环）
如果该最小值不是自己，则和第一个元素交换
循环以上过程（外层循环）
//假设最小值
int minIndex = 0;
int minVaule = a[minIndex];
//找出最小值
if (minVaule > a[minIndex+1]) {
}
//交换
if (minIndex != 0) {}
实现
分析
3.2.4 归并排序
思路
归并排序使用的是分治思想 ， 分治算法一般都是用递归来实现 。
- 把数组从中间分成前后两部分
- 然后对前后两部分分别排序
- 再将排好序的两部分合并在一 起
递推公式： merge_sort(p…r) = merge_sort(p…q), merge_sort(q+1…r)
终止条件： p >= r 不用再继续分解
实现
分析
归并排序是稳定的排序算法，在对两个数组的元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序
归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情 况，还是平均情况，时间复杂度都是O(nlogn)。
归并排序不是原地排序算法 — 归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间 ， 在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会 超过n个数据的大小，所以空间复杂度是O(1)。
3.2.5 快速排序
思路
快速排序使用的也是分治思想 ，选择数组中下标从l到r之间 的任意一个数据作为pivot（分区点） ,实现使用中间值mid
遍历l到r之间的数据 , 将小于mid的放到左边，将大于mid的放到右边，将pivot放到中间。
递推公式： quick_sort(l…r) = quick_sort(l…mid-1) + quick_sort(mid+1, r) 终止条件： p >= r
实现
分析
快速排序不是稳定的排序算法，在分区交换的时候可能会交换两个相同元素
快排的时间复杂度也是O(nlogn)。 。如果数组中的数据原来已经是有序的了，比如1，3，5，6，8。如果我们每次选择最后一个元素作为pivot，那每次分区得到的两个区间 都是不均等的。我们需要进行大约n次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约n/2个元素，这种情况下，快排的时间复杂度就 从O(nlogn)退化成了O(n2)。
归并排序是原地排序算法
归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。
快速排序优化
同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排
1.三数取中法
①从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。
②如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。
2.随机法：每次从要排序的区间中，随机选择一个元素作为分区点。
3.警惕快排的递归发生堆栈溢出，有2中解决方法，如下：
①限制递归深度，一旦递归超过了设置的阈值就停止递归。
②在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。
3.2.6 希尔排序
3.2.7 堆排序
3.2.8 桶排序
3.2.9 计数排序
思路
适合对一定范围内的数据进行排序；
找出array数据最小值min，最大值max
开辟一个容量为【max-min+1】的数组counts
array中元素k对应counts的索引就是【k-min】
把array所有元素按照counts的索引进行计数，counts的值就是元素的计数
最难理解的一步：把counts中的每个次数累加上其前面所有的次数，这样就能得到counts索引的值在新数组的索引
把counts的数据按序放回原数组，原数组的索引计算【counts[k-min]-p】,p代表相同元素的个数
实现
分析
计数排序不是原地排序
计数排序是原地排序稳定的排序算法
计数排序的时间复杂度为O(n)
计数排序的空间复杂度O(n)
3.2.10 基数排序
3.3 查找算法
3.3.1 二分查找
二分查找针对的是一个有序的数据集合（数组），每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0 。
1.二分查找依赖的是顺序表结构，即数组。
2.二分查找针对的是有序数据，因此只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
3.数据量太小不适合二分查找，与直接遍历相比效率提升不明显。但有一个例外，就是数据之间的比较操作非常费时，比如数组中存储的都是长度超过300的
字符串，那这是还是尽量减少比较操作使用二分查找吧。
4.数据量太大也不是适合用二分查找，因为数组需要连续的空间，若数据量太大，往往找不到存储如此大规模数据的连续内存空间。
思路
循环实现
递归实现
变体
3.3.2 二分查找
3.4 哈希算法
3.4.1 什么是哈希算法
将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而 通过原始数据映射之后得到的二进制值串就是哈希值。
- 从哈希值不能反向推导出原始数据；
- 对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同；
- 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
- 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。
3.4.2 哈希算法的应用
3.5 字符串匹配算法
3.5.1 暴力匹配算法
3.5.2 Rabin-Karp算法
若有收获，就点个赞吧
0 人点赞
