数据结构与算法
2022-08-26 22:34:20 6 举报AI智能生成
登录查看完整内容
思维导图 数据结构 算法 归纳
作者其他创作
大纲/内容
物理上顺序存储，随机读取：根据下标读取元素的方式
直接插入
尾部
指定位置及以后元素后移，新元素插入指定位置
中部
扩容一个数组容量为老数组2倍的新数组，然后将老数组数据拷贝到新数组，最后将新数组地址赋值给老数组
超范围插入
插入
指定位置元素删除，其后的元素前移
中间删除
尾部删除
删除
读多写少场景
数组
单链表
双向链表
循环链表
双向循环链表
静态链表
特点：在物理上非连续、非顺序的数据结构，由若干节点所组成。随机存储
查找：只能从头结点开始按顺序查找
读少写多场景
链表
用数组实现
顺序栈
用链表实现
链式栈
先进后出，回溯，应用场景：递归、方法级联调用、面包屑
栈
普通队列
综合了栈和队列的优点
对头和队尾均可以入队或者出队
双端队列 deque
阻塞队列
并发队列
阻塞并发队列
数组实现 队尾：rear=(rear+1)%array.length; 对头：front=(front+1)%array.length; 能充分利用数组的空间，避免了数组元素的整理移动的麻烦
循环队列
先进先出，应用场景：比如公平锁的等待队列，爬取网站url按入队顺序抓取和解析
队列
顺序存储结构
链式存储结构
物理结构，内存中实实在在的存储结构
顺序表
线性结构
树
图
非线性结构
逻辑结构，抽象的概念，依赖于物理结构而存在，可以使用任一物理结构实现
结构
线性表
jdk中的哈希函数并没有直接采用取模运算，而是使用了位运算的方式来优化性能
散列函数
使用场景：HashMap
原理：数组中元素不仅仅是一个entry对象，还是一个链表的头结点，当出现冲突时，每一个entry对象通过next指针指向它的下一个entry节点。
链表法
使用场景：java中ThreadLocal
原理：当一个key通过hash函数获得对应的数组下标已被占用时，就寻找下一个可用的数组位置，如果找不到或者达到了负载因子比例，就扩容后在寻址
开放寻址
其他
冲突解决
散列表就需要扩展它的长度，数组的长度
当经过多次元素插入，散列表数组达到应饱和度，key映射位置发生冲突的概率会逐步提高。这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大影响
动态扩容
位图
散列表 hash table
平衡二叉树
在二叉树上增加了几个条件
如果左子树不为股，则左子树所有节点的值均小于根节点的值
如果右子树不为空，则右子树上所有节点的值均大于根节点的值
左右子树也都是二叉查找树
二叉查找树
AVL树
红黑树
树堆
平衡二叉查找树
对于一个有n个节点的二叉树，按顺序层级编号，则所有节点的编号为从1到n，如果这个树所有节点和同样深度的满二叉树的编号从1到n的节点位置相同，则这个二叉树为完全二叉树。只需要保证最后一个节点之前的节点都是满二叉即可，最后一个节点可以不是满二叉
完全二叉树
一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点在同一层级上
满二叉树
会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或者右孩子空缺，则数组的相应位置也空出来。比如12345X6X8 （X表示空置的位置）。对于一个稀疏二叉树来说，用数组表示法是非常浪费空间的
数组存储结构
存储
自平衡算法
2 要遵守二叉排序树的原则：左子树小于根节点，右子树大于根节点，要保证平衡，否则为成为线性链表
主要应用于查找和维持相对顺序
根节点第一个，输出顺序：根节点、左子树、右子树 。左子树遍历完了才遍历右子树
前序遍历
左子树第一个，输出顺序：左子树、根节点、右子树
中序遍历
左子树第一个，输出顺序：左子树、右子树、根节点
后序遍历
前中后的顺序是以根节点的位置定义。前序指根节点在第一个。中序指根节点在中间；后序指根节点在最后
递归
借助栈结构
遍历方式
深度优先遍历
层序遍历，一层一层的遍历
广度优先
遍历顺序
二叉树
span style=\
B+树
2-3树
2-3-4树
多路查找树
任一个父节点的值，都小于或者等于子节点的值。子节点树不定。堆顶是整个堆中值最小的元素
小顶堆
任一个父节点的值，都大于或者等于子节点的值。子节点数不定。堆顶是整个堆中值最大的元素
大顶堆
最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队。使用大顶堆
最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队。使用小顶堆
优先级队列
斐波那契堆
二项堆
存储 顺序存储，所有节点存储在数组中。数组没有左右指针，如果定位左右子节点，依靠数组的下标，左子节点：2x父节点下标+1；右子节点：2x父节点下标+2
完全二叉树，子节点数不能超过2个
应用：堆排序及优先级队列的基础
二叉堆
O(logn)
插入节点，上浮操作
删除节点，把堆最后一个节点临时补到根节点上，然后子节点进行比较，如果比他们大，则做下沉操作
O(n)
构建堆，本质上是让非叶子节点依次下沉
删除节点，下沉操作
自动调整，把一个不符合堆的树调整为一个符合堆特性的树
如何构建堆
堆
邻接矩阵
临接表
图的存储
拓扑排序
最短路径
关键路径
最小生成树
二分图
最大流
数论
计算几何
概率分析
并查集
拓扑网络
矩阵算法
线性规划
最好
最坏
平均
均摊
O(1)
O(n^n)
大O表示法T(n)=O(*)
渐进时间复杂度
时间复杂度
大O表示法S(n)=O(*)
空间复杂度
复杂度
贪心算法
分治算法
动态规划
回溯算法
枚举算法
基本算法思想
最小的往上冒，也即是最小的在前面，最大的在后面
相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换他们的位置；当一个元素小于或者等于右侧相邻元素时，位置不变
稳定排序
1 设置有序标记，有序时跳出循环
2 每轮排序后，记录下最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了
第一轮从左到右
第二轮从右到左
第N轮
元素比较和交换过程是双向的
实现：外层循环控制所有排序回合，大循环内包含2个小循环，第一个小循环从左到右比较并交换元素（奇数轮） 第二个小循环从右到左比较并交换元素（偶数轮）
3 鸡尾酒排序
优化
实现：双重循环即可，外层负责循环的回合，内层负责比较值并交换值
冒泡排序（bubble sort）
插入排序
选择排序
希尔排序
O(n^2)
分治法，但仍属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。快速排序是很重要的算法，与傅里叶变换等算法并称为二十世纪十大算法
在每一轮挑选一个基准元素，并让其他比他大的元素移动到数列的一边，比它小的元素移动到数列的另一边，从而把数列拆分成两个部分
遇到逆序要转换成顺序时，会退化为O(n^2)的排序
最简单的方式选择数列的第1个元素
随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置
基准元素(pivot)的选取
双边循环法
单边循环法
绝大多数递归，都可以用栈的方式来代替
递归和非递归实现
选定基准元素之后，要进行元素交换
空间复杂度O(logn)
不稳定排序
1 将无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
2 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶
最坏时间复杂度O(nlogn)
堆排序，使用堆(主要是二叉堆)的最大堆或者最小堆的堆顶元素时最大或者最小元素的特性，删除堆顶元素后，堆调整后，堆顶又是第二大或者第二小的元素，循环删除，即得到有序数据
JDK Collections.sort采用归并排序或者Timsort
归并排序
O(nlogn)
适用于取值范围不是很大的情况
数组长度=数列最大值-最小值+1 作为数组的长度；最小值作为偏移量，用于计算数值在统计数组中的下标。那么一个数值在数组中的位置=数值-最小值，即为实际数值在数组中的位置
单纯排序没有问题
业务上要处理相同数值谁是谁的问，比如成绩，2个同学相同，要看出哪个在前哪个在后时，还得继续优化
优化后的计数排序是稳定的排序
需要借助一个数组，统计待排序数列中各个数值出现的次数，以待排序中的最大值来决定统计数组的长度。数组长度=最大值+1
比如给出20个随机整数，范围0到1亿之间，这是如果用计数排序，需要创建长度为1亿的数组，不但严重浪费空间，而且复杂度也会随之升高
1 当数列最大和最小值差距过大时，并不适用计数排序
2 当数列元素不是整数时，也不适用计数排序
计数排序强大，但是很少被使用，是有以下2个局限
优化前是非稳定排序
计数排序
基数排序
1 桶(bucket):代表一个区间范围，里面可以承载一个或者多个元素
桶的数量：最简单的方式，桶数量等于原始数列的元素数量，除最好一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定
桶的区间范围：以数列中最小值为起点，第一个桶的值区间范围（左闭区间，右开区间）=[数列最小值，数列最小值+跨度)；第二个桶的值区间范围=[上一个桶的区间范围最大值，上一个桶的区间范围最大值+跨度);以此类推，直到桶的数量等于数列的值得数量
2 建多少个桶，如何确定桶的区间范围，有很多种不同的方式
3 桶的数量及范围确定之后，遍历数值，将元素对号入座放入属于值范围的桶中
4 对每个桶内部的元素分别进行排序
5 遍历所有的桶，输出所有元素
弥补了计数排序的局限
稳定的排序
桶排序的性能并非绝对稳定，还是要看元素是否大致均匀的分布在每个桶中，如果元素分布极不均匀，在极端情况下，某一个桶的数量为n-1个元素，最后一个桶只有1个元素。此时时间复杂度退化为O(nlogn)，而且还白白创建了许多空桶
桶排序
如果值相同的元素在排序后仍然保持着排序前的顺序，这样的算法是稳定的
如果值相同的元素在排序后打乱了排序前的顺序，则这样的排序算法是不稳定的
稳定性
排序
深度优先搜索
广度优先搜索
A*启发式搜索
搜索
线性表查找
树结构查找
散列表查找
查找
朴素
KMP
Robin-Karp
Boyer-Moore
AC自动机
Trie
后缀数组
字符串匹配
数据结构与算法
0 条评论
回复 删除
下一页
