算法总结

一、图算法：解决 “连接与路径” 问题

比如地图路线规划、网络拓扑分析，先明确 “怎么遍历节点”，再解决 “怎么找最短路径 / 最小成本”。

1. 图的遍历算法（基础：先学会 “逛遍所有节点”）

• BFS（广度优先搜索）

  → 核心逻辑：按 “层次” 逛，比如先逛完当前节点的所有邻居，再逛邻居的邻居（用队列记待逛节点）。

  → 用在哪：找无权图最短路线（如迷宫最少步数）、朋友圈人数统计、APP 消息 “逐层推送”。

• DFS（深度优先搜索）

  → 核心逻辑：按 “深度” 逛，比如一条路走到头，没路了再回头换条路（用栈 / 递归记路线）。

  → 用在哪：找所有迷宫出口、项目任务依赖排序（拓扑排序）、检测网络中是否有 “循环依赖”。

2. 最小生成树算法（需求：连接所有节点，成本最低）

• Prim 算法

  → 核心逻辑：从一个节点出发，每次选 “离已连区域最近的节点” 加入，像 “慢慢扩大圈子”。

  → 用在哪：稠密图（边多、节点少），比如城市内部电网铺设（少节点、多电缆，要省总长度）。

• Kruskal 算法

  → 核心逻辑：先把所有 “边” 按成本排序，每次选 “不绕圈的边” 接上，像 “拼积木”。

  → 用在哪：稀疏图（边少、节点多），比如跨城市光纤搭建（多城市、少光纤，避免绕路浪费）。

3. 最短路径算法（需求：从 A 到 B，路线最短 / 成本最低）

• Dijkstra 算法

  → 核心逻辑：从起点出发，每次选 “当前最短路径的节点”，更新邻居的路径长度（不支持负成本）。

  → 用在哪：导航 APP 算 “家到公司最短距离”、外卖平台算 “骑手到商家最快路线”。

• Floyd 算法

  → 核心逻辑：算 “所有节点之间的最短路径”，比如 A 到 B、A 到 C、B 到 C，像 “一次性算完所有组合”。

  → 用在哪：物流系统算 “所有仓库到所有门店的运输成本”（小规模数据适用）。

4. 拓扑排序算法（需求：处理 “依赖关系”，比如先做 A 再做 B）

• 基于 DFS 的拓扑排序

  → 核心逻辑：逛节点时，“最后逛完的节点” 先记下来，最后倒过来就是排序结果。

  → 用在哪：代码编译顺序（先编译被依赖的文件）、课程表安排（先学高数再学线代）。

• Kahn 算法

  → 核心逻辑：先找 “无依赖的节点”（比如不用先学任何课的通识课），处理完再找下一批，像 “逐步解锁任务”。

  → 用在哪：检测是否有循环依赖（比如 “先学 A 要先学 B，先学 B 要先学 A”）、项目任务排期。

二、查找算法：解决 “快速找数据” 问题

比如查字典、找手机联系人，核心是 “越快越好”，不同数据类型对应不同方法。

1. 简单查找（数据无序 / 少量）

• 顺序查找

  → 核心逻辑：从第一个数据开始，逐个对比，直到找到（像翻书找某一页）。

  → 用在哪：找未排序的列表（如微信聊天记录搜关键词）、数据量少（比如 10 个以内）的场景。

2. 有序查找（数据已排好序）

• 二分查找

  → 核心逻辑：把有序数据分成两半，比目标大就查左半，小就查右半，像 “猜数字游戏”。

  → 用在哪：查字典（按拼音排序）、APP 里的 “联系人按字母排序查找”（仅支持数组，不支持链表）。

• 二叉排序树（BST）查找

  → 核心逻辑：树的规则是 “左子树比根小，右子树比根大”，按目标大小找左 / 右子树。

  → 用在哪：数据要频繁增删（如实时更新的商品列表），但数据有序时会 “变丑”（比如全是左子树，找起来变慢）。

• 平衡二叉树（AVL）查找

  → 核心逻辑：在 BST 基础上 “整容”，保证左右子树高度差不多，避免 “变丑”（用旋转调整结构）。

  → 用在哪：股票行情实时查询（价格频繁变，还要快速找某支股票）、高频增删的有序数据。

3. 哈希查找（追求 “瞬间找到”）

• 哈希表查找

  → 核心逻辑：给数据编个 “专属编号”（哈希值），按编号直接定位位置，像 “快递柜按取件码找柜子”。

  → 用在哪：缓存（比如 Redis 存用户信息）、数据库索引、手机联系人按 “姓名首字母” 快速定位。

三、排序算法：解决 “数据变有序” 问题

比如成绩排名、商品按销量排序，先看 “数据规模”，再看 “是否要稳定（相等数据不换位置）”。

1. 小规模数据 / 基本有序（简单排序）

• 直接插入排序

  → 核心逻辑：像整理扑克牌，拿到一张牌，插入到前面已排好的牌里合适的位置。

  → 用在哪：班级小测验成绩排序（30 人以内）、Excel 里的 “小批量数据排序”。

• 冒泡排序

  → 核心逻辑：像气泡往上飘，每次把最大的数 “推到最后”（相邻数据对比，逆序就交换）。

  → 用在哪：教学演示（容易理解）、数据基本有序（比如大部分成绩已排好，只剩几个乱的）。

2. 中大规模数据（高效排序）

• 快速排序

  → 核心逻辑：选一个 “基准数”，把比它小的放左边，大的放右边，再分别排序左右（像 “分蛋糕”）。

  → 用在哪：电商平台 “千万级商品按销量排序”、数据库里的 “大规模数据查询排序”（最快的排序之一）。

• 堆排序

  → 核心逻辑：把数据建成 “大堆”（堆顶是最大数），每次拿最大数放最后，再调整堆（像 “选冠军”）。

  → 用在哪：找 “TopK”（比如销量前 10 的商品）、内存有限时的大规模排序（省空间）。

• 归并排序

  → 核心逻辑：把数据分成两半，分别排序，再把两个有序的半区 “合并”（像 “合并两个有序列表”）。

  → 用在哪：海量日志排序（支持外部排序，数据放硬盘）、需要 “稳定排序” 的场景（比如按成绩排序，相同成绩保留原顺序）。

3. 特殊数据（整数 / 固定长度字符串）

• 基数排序

  → 核心逻辑：按 “数字位数” 排序，先排个位，再排十位，最后排百位（像 “按学号最后一位、倒数第二位排序”）。

  → 用在哪：手机号排序、快递单号排序（固定长度的字符串 / 整数）。

四、树与二叉树算法：解决 “层级数据” 问题

比如文件系统（文件夹套文件夹）、公司组织架构，先学会 “遍历”，再学 “构建与优化”。

1. 二叉树遍历（基础：逛遍树的所有节点）

• 前序 / 中序 / 后序遍历（递归 / 非递归）

  → 核心逻辑：

  • 前序：先逛根，再逛左子树，最后逛右子树（像 “先看文件夹，再看里面的文件”）；

  • 中序：先逛左子树，再逛根，最后逛右子树（常用于 “二叉排序树”，遍历结果是有序的）；

  • 后序：先逛左子树，再逛右子树，最后逛根（像 “先删文件，再删文件夹”）。

    → 用在哪：重建二叉树（比如根据遍历结果恢复文件目录）、统计树的层数（比如公司有多少级部门）。

• 层次遍历

  → 核心逻辑：按 “层” 逛，先逛完第一层（根），再逛第二层（根的孩子），以此类推（用队列记待逛节点）。

  → 用在哪：APP 评论区 “按楼层显示回复”、计算树的 “最宽层”（比如某层有多少个部门）。

2. 树的构建与应用（解决实际问题）

• 哈夫曼树构建

  → 核心逻辑：选两个 “权重最小的节点” 合并成新节点，重复到只剩一个节点（权重可以是 “出现次数”）。

  → 用在哪：数据压缩（比如图片、音频压缩），权重高的节点用短编码（少占空间），权重低的用长编码。

• 二叉树线索化

  → 核心逻辑：把树里 “空着的指针” 改成 “线索”，指向 “前一个节点” 或 “后一个节点”（像给树加 “导航箭头”）。

  → 用在哪：频繁遍历树的场景（比如日志系统按时间顺序遍历所有日志），不用每次遍历都用栈 / 递归（省内存）。