数据结构和算法速记

目录

• 数据结构
• 算法
  • 查找算法
  • 排序算法

数据结构

• 数组 结构特征：内存地址连续，大小固定 使用特点：查询快，插入慢
• 链表 结构特征：内存地址不连续，大小可变 使用特点：查询慢，插入快
• 栈 结构特征：顺序栈（基于数组实现，继承数组特征），链式栈（基于链表实现，继承链表特征） 使用特点：先进后出，后进先出
• 队列 结构特征：顺序队列（基于数组实现，继承数组特征），链式队列（基于链表实现，继承链表特征） 使用特点：先进先出，后进后出
• 树 结构特征：每个节点有0个或多个子节点
  • 二叉树 结构特征：每个节点最多有两个子节点
  • 二叉查找树 结构特征：每个节点最多有两个节点，且左子树的值<根节点的值<右子树的值 使用特点：二叉查找树的查询，插入的时间复杂度都为O(logn)
  • 平衡二叉树 结构特征：在二叉查找树的基础上，加了限制条件：每个节点的左子树和右子树高度差最多为1
  • 红黑树 比喻：如果说平衡二叉树是一个类的话，红黑树就是这个类的实例 结构特征：任意节点到叶子节点拥有相同数量的黑节点（共有5个特征） 使用特点：红黑树通过变色和自旋来实现自平衡
  • B树 结构特征：每个节点可包含多个子节点，叶子节点位于同一层（每个节点保存索引和数据） 使用用法：B树为磁盘预读设计，其特征相对于二叉树降低了高度，减少IO次数（树的高度等于IO次数）
  • B+树 结构特征：只在叶子节点存储数据，且叶子节点有序排列，通过链指针相连（只有叶子节点保存数据，其他节点都只保存索引，单次IO能加载更多节点） 使用用法：B树解决了磁盘IO问题，而B+树通过数据结构优化和区间访问加快了元素的查找效率

算法

查找算法

• 顺序查找 挨个遍历，时间复杂度为O(n)
• 二分查找 折半查找（前提：元素有序排列），时间复杂度为O(logn)
• 插值查找 二分查找的优化版，折半改为自适应 mid= low + (key - a[low]) / (a[high] - a[low]) * (high - low) 平均复杂度为O(log(logn))，最坏情况O(logn)
• 分块查找 思想：将元素按块有序划分，块内无序，块与块之间有序，比如说第一个块的任意一个元素小于第二个块中的任意一个元素 流程：先取出每个块中的最大值构成索引表，然后使用顺序查找或二分查找确定块，然后顺序查找当前块 时间复杂度：O(logn)
• 哈希查找 典型实现：HashMap，使用数组+链表的结构 时间复杂度：在不形成链表的情况下时间复杂度为O(1)，反之时间复杂度为O(n)，1.8中引入红黑树，时间复杂度为O(logn)
• 二叉查找树 时间复杂度为O(logn)，但在树不平衡的情况下可能为O(n)
• 平衡二叉树 时间复杂度为O(logn)，红黑树就是平衡二叉树的一种

排序算法

• 插入排序 直接插入排序和二分查找排序适合小规模且基本有序的数据 希尔排序适合大规模且无序的数据
  • 直接插入排序 思想：第2个元素和第1个元素比，第3个元素和前两个元素比（遍历元素，在左侧合适的位置插入） 时间复杂度：平均时间复杂度为O(n2)，当元素有序时时间复杂度为O(n)，遍历一遍就完了
  • 二分插入排序 相对于直接插入排序，顺序遍历改为二分查找 时间复杂度：平均时间复杂度为O(n2)，当插入位置总是为最后一个时，不会引起数组的批量移动，时间复杂度为O(logn)
  • 希尔排序 思想：在大规模数据情况下，通过分组避免大量的遍历操作 过程：根据增量分组，增量=元素/2(组数，例如8个数分为4组，16个数分为8组)，在组内排序。 ​ 然后增量/2，继续分组，在组内排序，继续循环，直到增量为1. 增量序列：{1,2,4,8,...}时间复杂度为O(n2) ​ {1,5,19,41,109,...}时间复杂度为O(n1.3)
• 交换排序
  • 冒泡排序 比较相邻的元素，如果第一个比第二个大，元素交换（按照升序排列）第一次循环，最后一个数为最大的数。 对所有的数执行同样的操作，除了最后一个。 时间复杂度：O(n2)
  • 快速排序 在数列中选取一个基准数，分区：遍历数列，大的数放右边，小的数放左边。子序列递归操作。 时间复杂度：平均时间复杂度O(nlogn)，如果选择的基准数为最小或最大的数，时间复杂度为O(n2)
• 选择排序
  • 直接选择排序 两层循环，每次把最小的数移动到头部。 时间复杂度为O(n2)
  • 堆排序 最大堆：根节点最大（二叉树） 将数据构成一颗最大堆，每次取顶端的数；然后对剩下的数据进行最大堆重新构造 时间复杂度：O(nlogn)
• 归并排序 首先使子序列有序，然后将子序列有序合并，得到完全有序的数列。（递归） 时间复杂度：O(nlogn)
• 计数排序
  • 找出最大的数和最小的数
  • 统计每个值出现的次数，值为数组下标，次数为数组的值
  • 遍历数组，反向填充数组 当元素为n个0~k之间的整数时，时间复杂度为O(n+k)，空间复杂度为O(n+k)
• 桶排序 类似HashMap数组+链表的结构，有一个索引函数，然后根据这个函数和输入的值计算数组下标。 发生函数冲突时，在链表中排序。这样每个桶都是有序的，再取出来就好了 时间复杂度：入桶O(n)，桶排序（链表排序）O(logm/n)。一般情况O(nlogm/n) 在不发生冲突的情况下，也就是每个桶刚好一个数的时候，时间复杂度为O(n)
• 基数排序 先个位排序，然后十位排序，依次类推 使用桶排序按照数列的个位入桶，生成一个序列。 将这个序列按照数列的十位入桶，生成一个序列.... 时间复杂度：O(n)