如果你想成为一个码农或是熟练工（Code Monkey），你大可以不学算法，因为算法对你确实没有用；但如果你想成为一个优秀的开发者（Developer），扎实的算法必不可少，因为你会不断的掉进一些只能借助算法才能爬出去的坑里。

算法

算法是一种将有限计算资源发挥到极致的武器，当计算资源很富余时算法确实没大用，但一旦到了效率瓶颈算法绝壁是开山第一刀

排序算法

排序我们需要关注的性能大致有两个：

平均时间复杂度(最慢的排序方法：n^2 最快的排序方法：nlg2n)
辅助空间复杂度
排序算法的稳定性

排序总结

为什么要分稳定排序和非稳定排序呢

排序的稳定性就意味着：具有相同value的数在排序后，相对顺序不变。

能保证第二次排序好的序列保持着第一次的排序顺序。

第一次排序 a=1 b=2; 第二次排序 a=1 b=2; //虽然a、b的value一致，但是采用稳定排序后，还是能保证上次value值低的在前面

具有两个排序关键字的时候，可以让key2的value值相等的同学还是按照key1的value排序。

交换排序

冒泡排序(稳定)

相邻元素进行两两比较，将最大值推动到最右边。重复以上过程。时间复杂度平均O(N^2)最差O(N^2)，空间复杂度O(1)

快速排序

选择数组中第一个元素作为基准，从左边向右找到第一个大于等于基准的元素，从右边向左找到第一个小于等于基准的元素，交换这两个元素，最后基准左边的元素都小于等于基准，基准右边的元素都大于等于基准。然后固定基准元素，对其左边和右边采取同样的做法。典型的分治思想。时间复杂度平均O(N lgN)最差O(N^2)，基于递归的实现由于用到了系统栈，所以平均情况下空间复杂度为O(lgN)

插入排序

简单插入排序(稳定，O(n^2) )

插入排序，其实就是斗地主，将原序列分为左侧(已排好的序列)，每次将右侧的第一张牌，从后往前插入到等于或者大于这张牌的位置上。

希尔排序

希尔排序是简单插入排序的改进版，它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

选择排序

简单选择排序

首先在未排序的序列中选择最小的元素，放到未排列序列的起始位置。重复以上的过程。

无论什么样的数据都是 O(n^2) 的时间复杂度，适合小规模的数据进行排序。

堆排序

堆排序使用了最大堆/最小堆，拿数组升序排序来说，需要建立一个最大堆，基于数组实现的二叉堆可以看作一棵完全二叉树，其满足堆中每个父结点它左右两个结点值都大，且堆顶的元素最大。

将堆顶元素和数组最后一个元素交换，最大元素被交换数组最后一个位置，同时从堆中删除原来处于堆顶的最大元素被交换到堆顶的元素一般会打破堆结构的定义，因此需要进行堆的调整（下沉）。将堆顶的元素和其左右两个结点比较，将三者中的最大的交换到堆顶，然后继续跟踪此结点，循环上述过程，直到他比左右两个结点都大时停止调整，此时堆调整完毕，再次满足堆结构的定义重复以上两个过程。直到堆中只剩一个元素，此时排序完成每次调整堆的平均时间为O(lg N)，因此对大小为N的数组排序，时间复杂度最差和平均都 O(N lg N).

归并排序

二路归并排序（稳定）

多路归并排序（稳定）

非比较类排序(线性时间稳定)

基数排序

桶排序

计数排序

Huffman编码

Huffman是一种压缩算法，它本身是一颗带权重的二叉树。

首先统计所有字符出现的次数。将其放置到优先队列中。将队列转化为二叉树。（从队列的头中取两个数相加，同时作为两个叶子结点，再把相加的数放到优先队列中。重复以上过程）

动态规划

分阶段解决决策问题的数学思想。

大事化小，小事化了动态规划算法也可以说是 ‘记住求过的解来节省时间’”

动态规划存在三个重要的概念： 最优子结构：就算是一个大问题，如何拆解成最优的小问题 F(n)=F(n-1)+F(n-2); 边界 : 没得选的时候 状态转移公式 ：根据最优子结构和边界构建公式

爬楼梯问题：

int getClimbingWays(int n){
    if(n<1){
        return 0;
    }
    if(n==1){
        return 1;
    }
    if(n==2){
        return 2;
    }
    int a=1,b=2,temp=0;
    for(int i=3;i<=n;i++){
        temp=a+b;
        a=b;
        b=temp;
    }

    return temp;
}

数据结构

就是用一个计算机可以识别的东西，把现实世界中的东西给装进去。

数组和字符串

数组是数据结构的基本模块，可以理解为 同一类事物的顺序线性集合，它支持随机读取，通过索引能够获取特定位置的元素。

数组可以有多个维度，如一维、二维、三维、乃至N维。

#include <iostream>
#include <algorithm>
int main() {
    int a1[5] = {1, 2, 3}; 
    int size = sizeof(a1) / sizeof(*a1);
    for (int i = 0; i < size; ++i) {
        printf("%d\n", a1[i]);
    }
    a1[0] = 4;
    sort(a1, a1 + size);//C++自带的排序函数，默认是递增
}

注意如果对静态数据进行删除和添加操作，往往会涉及到数组的拷贝，因此在涉及这些操作时，考虑使用动态数组。

动态数组

数组具有固定的容量，我们需要在初始化时指定数组的大小。有时它会非常不方便并可能造成浪费。

因此，大多数编程语言都提供内置的动态数组，它仍然是一个随机存取的列表数据结构，但大小是可变的。例如，在 C++ 中的 vector，以及在 Java 中的 ArrayList。

动态数组是由编程语言提供的，基础也是静态数组，但是在数组上进行额外的代码补充。

字符串

字符串也是数组的一种，我们通过使用 字符数组 char [] str 或者 string s 来定义字符串。

这里可以理解为 str是静态数组 s是动态数组。

双指针技巧

1.首尾双指针 2.快慢指针

具体案例：参考leetCode数据结构相关题目、牛客网的题库中有考研真题也可以做一做

链表

与数组类似，也是一种线性的数据结构。

每个链表的结点一方面要存储value值，还要存储下一个结点的引用。

对于链表元素的访问，如访问第i个元素，我们往往需要从第一个元素逐个遍历。平均访问时间为o(n)。

那么链表的优势在那里？他的插入和删除操作只需要修改临近的两个结点，而不用对整个链表进行修改。

插入：

删除：更简单

prev->next结点=next->next结点

双向链表

双向链表就是存储上下两个结点的引用。通过一种空间的损耗，可以提供更方便的访问。如删除某个结点时，我们可以使用prev获取当前结点的父亲，从而实现快速删除。(常规的单链表需要从头遍历找到元素再删除)

链表操作函数

画图法+考虑null值

1.get(index) 2.addAtHead(val) 3.addAtTail(val) 4.addAtIndex(index,vak) 5.deleteAtIndex(index)

双指针

1.快慢指针

具体案例：参考leetCode数据结构相关题目，牛客网的题库中有考研真题也可以做一做

queue

先入先出的数据结构。

入队列 enqueue，添加到数组尾部，需要考虑扩容检测。(尾入) 出队列 dequeue，从数组的头部出队列。(头出)

循环队列

传统的基于数组实现的队列存在这样的问题，如果一个队列满了，我们无法插入下一个元素，即使队列的前面存在空间(出队列导致front指针向后移动)。

循环队列，可以让我们去重新使用这些空间。

广度优先遍历

在图和树的层次遍历中经常使用。

stack 🥛

先入后出的数据结构，本质还是数组。

入栈 push，添加top，需要进行扩容检测。（如果使用动态数组，就可以不用自己去写扩容检测）出栈 pop，取出top。

同时我们要知道大多数的语言都提供了内置的栈库，因此你不需要自己去开发轮子。(当然你不能不会开发轮子)

深度优先遍历

栈可以记录你的路径，然后进行回退。

在路径和图、二叉树树的深度遍历中经常使用。

树

树 是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。

森林

森林其实就是多个树

如何把森林给转化为一个二叉树？

第一步将每个树给变成二叉树：树的每一层，将兄弟联接在一起，然后每个父节点，只保存长子(最左侧的孩子)。同时我们发现每个二叉树的根结点的右孩子为空。

第二步将各个二叉树的根节点依次连接在上一个二叉树的右孩子结点上。

二叉树

二叉树是一种更为典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

这里的前中后是针对根结点而言的。

前序遍历
中序遍历
后序遍历

这里特别说说后序遍历，既先左子树再右子树最后根节点

删除树结点和后序遍历，删除左子树，右子树和根结点后缀表达式和后序遍历，如果你想对这棵树进行后序遍历，使用栈来处理表达式会变得更加容易。每遇到一个操作符，就可以从栈中弹出栈顶的两个元素，计算并将结果返回到栈中。

层次遍历

利用一个队列，可以实现层次遍历。

递归实现前、中、后序遍历

这个就狠简单了，就是用递归。

Huffman树

Huffman树又称最优二叉树，其作用在于数据压缩与编码长度的优化。

带权路径长度=所有叶子结点的权值*路径长度之和

叶子结点生成Huffman树

要求构成的树的带权路径长度达到最小。

每次从森林中取最小的两个进行组合。

编码

从根结点开始，左0，右1就可得到Huffman编码。 Huffman编码长度最小

二叉查找树

左边的节点都小于根节点，右边的节点都大于根节点。这个特性给查找带了方便，从树根出发，有一半的节点你都不用访问。二叉查找树在最坏情况下，退化成链表，查找时间从平均O(lg n)降到O(n), 二叉树的中序遍历就是有序的数列。

插入：空树，首先生成根节点；不是空树就进行查找，找到父节点，然后作为叶子结点插入。删除：（1）如果是叶子结点，直接删除（2）如果只有一个子节点，将子节点平移到被删除元素的位置（3）如果有两个子节点，利用中序遍历，获取被删除元素的后一个元素，将其进行互换，此时被删除元素已经是叶子结点，可以直接删除。

平衡二叉树（理解即可）

针对二叉查找树退化为链表的情况，平衡二叉树使树的结构更加平衡，提高了查找的效率；但是由于插入和删除后需要重新恢复树的平衡(我们称为旋转操作，分为左旋转和右旋转)，所以插入和删除会慢一些。

首先理解左旋和右旋左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点；

右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。

插入 1.左左，就对结点进行右旋 2.右右，就对结点进行左旋 3.左右，对左结点先左旋变成左左，再右旋 4.右左，对右结点先右旋变成右右，再左旋

删除（1）当删除的节点是叶子节点，则将节点删除，然后从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，此时到根节点还发现没有失衡，则说此时树是平衡的；如果中间过程发现失衡，则判断属于哪种类型的失衡（左左，左右，右左，右右），然后进行调整（2）删除的节点只有左子树或只有右子树，这种情况其实就比删除叶子节点的步骤多一步，就是将节点删除，然后把仅有一支的左子树或右子树替代原有结点的位置，后面的步骤就一样了，从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，如果中间过程发现失衡，则根据失衡的类型进行调整。（3）删除的节点既有左子树又有右子树，这种情况又比上面这种多一步，就是中序遍历，找到待删除节点的前驱或者后驱都行，然后与待删除节点互换位置，然后把待删除的节点删掉，后面的步骤也是一样，判断是否失衡，然后根据失衡类型进行调整。

平衡二叉树首先是一棵二叉查找树，其次它需要满足其左右两棵子树的高度之差不超过1，且子树也必须是平衡二叉树，换句话说对于平衡二叉树的每个结点，要求其左右子树高度之差都不超过1。查询的时间复杂度是 O(logN) 插入复杂度是 O(1)

应用场景比如在HashMap中用到了红黑树（平衡二叉树的特例），数据库索引中的B+树等。

红黑树

红黑树的存在就是为了解决二叉查找树的缺陷，因为二叉树在某些情况下会退化为一个线性结构。

红黑树示意图

红黑树是一种自平衡的二叉查找树。红黑树从根到叶子的最长长度不会超过最短路径的2倍

红黑树的特点：根节点总是黑色的；每个叶子节点都是黑色的空节点（NIL节点）每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。（即相同的黑色高度）

B+树

B+树是最常见的索引结构。

结构特点是：

1、是多叉树了,而不是二叉树了，同时每个节点可以包含更多的节点，这样做有两个原因,一个是降低树的高度。另外一个是将数据范围变为多个区间，区间越多，数据检索越快。 2、每个节点不再只是存储一个key了，可以存储多个key； 3、非叶子节点存储key，叶子节点存储key和数据。 4、叶子节点两两相连，为顺序查询提供了帮助

使用优势：

1、B+树的非叶子节点只是存储key，占用空间非常小，因此每一层的节点能索引到的数据范围更加的广。换句话说，每次IO操作可以观看更多的数据； 2、叶子节点两两相连，符合磁盘的预读特性。如图三中存储50和55的叶子节点，它有个指针指向了60和62这个叶子节点，那么当我们从磁盘读取50和55对应的数据的时候，由于磁盘的预读特性，会顺便把60和62对应的数据读取出来。这个时候属于顺序读取，而不是磁盘寻道了，加快了速度。 3、支持范围查询，而且部分范围查询非常高效，原因是数据都是存储在叶子节点这一层，并且有指针指向其他叶子节点，这样范围查询只需要遍历叶子节点这一层，无需整棵树遍历。

图

图的知识点就是图的遍历（广度和深度）

图的表达（数组表达，链表表达）

图的算法最短路径算法，联通性等

算法