博客内容为PHP-Interview-QA读后笔记
衡量算法优劣的指标
- 空间复杂度
- 时间复杂度
链表有哪些
- 单向链表
- 双向链表
- 循环链表
线性结构
线性结构是指一个有序数据元素的集合，除了第一个和最后一个外，其他元素都是首尾相接的。
常见的线性结构有：线性表、栈、队列、数据
树
- 二叉树
- 二叉搜索树
- 平衡二叉树
- 红黑树
- B树
- B+树
散列表
散列表，就是哈希（Hash）表，在PHP中，数组就是哈希表的实现。
散列表是用来存储key-value键值对的数据结构，其原理是将key通过散列函数计算，得到相应的桶的序号，然后通过桶号直接访问value。
散列函数应尽可能让所有key均匀地散布到整个集合。
此外，散列函数计算得到的结果可能相同，这种情况就叫哈希冲突。
处理哈希冲突的常用方法：
- 拉链法：在每个桶中存放一个链表，通过链表存储冲突的值
- 开放地址法：用大小为M的数组保存N个键值对，其中M>N，数组中的空位用于解决冲突问题。线性探测法就是这种方法的具体实现：当发生碰撞时，我们会检测数组的下一个位置，直到找到该键或遇到一个空位置。
排序
- 选择排序：简单选择排序（每次选择最小或最大的排在起始位置）、堆排序（将序列构成最大堆或最小堆，将堆顶元素（最大元素或最小元素）放于序列末尾，然后将剩下的n-1个元素继续如上操作，直至得到有序序列）
- 插入排序：简单插入排序（前面为有序序列，后面为无序序列，每次从无序序列中选择第一个元素，比较并插入到有序序列中的合适位置）、希尔排序
- 交换排序：冒泡排序（比较相邻元素的大小，并按条件进行交换）、快速排序（选择一个数值，交换并保证比它小的元素在其左边，比它大的元素在其右边）
- 归并排序（将序列分为左右两个子序列，对两个子序列分别进行归并排序，将排好序的两个子序列合并成最终的排序序列）
- 基数排序：桶排序、基数排序
其他算法
- KPM（字符串查找算法）
- 布隆过滤器（检索一个元素是否在集合中）
- 贪心算法
- 回溯算法
- 动态规划
- 最小生成树
- 最短路径
- 推荐算法
- 深度优先、广度优先