欧几里得算法
欧几里得算法（辗转相除法）基于“两数最大公约数等于较小数与两数相除余数的最大公约数”这一定理，通过重复取余运算，在余数为 0 时快速求得两个非负整数的最大公约数。
基础算法
属于该分类的文章：
基础算法
21篇文章
SPFA 算法
Bellman‑Ford 算法用于求解带负权边的单源最短路径，允许边权为负，通过对所有边执行 n‑1 轮松弛操作得到最短路径；再执行一轮松弛，若仍可更新距离，说明图中存在负权回路，时间复杂度 O (nm)，效率低于 Dijkstra，适合检测负权环。
基础算法, 最短路径问题
桶排序
桶排序将数据按数值范围划分到若干个桶内，每个桶内部再使用其他排序算法排序，最后依次合并所有桶的元素得到有序序列；平均时间复杂度 O(n)，适合数据分布均匀的场景，需要额外开辟桶空间，属于稳定排序。
基础算法, 排序
快速幂取模
快速幂取模通过二进制拆分指数，将大指数幂运算的时间复杂度降至 O (log n)，在每一步运算中同步做取模操作，避免数值溢出，用来高效求解 a 的 b 次方对 m 取模的结果。
基础算法
快速幂
快速幂借助指数的二进制拆分，把 a 的 b 次方的时间复杂度从 O (b) 优化到 O (log b)。不断对底数平方，当指数二进制位为 1 时就把当前底数乘入答案，常搭配取模处理大数，高效计算大指数的模值。
基础算法
堆排序
堆排序利用大顶堆（或小顶堆）的堆性质，先将待排序数组构建成堆，反复取出堆顶最大元素放到末尾，再调整剩余元素维持堆结构，完成排序；时间复杂度稳定\(O(n\log n)\)，原地排序，属于不稳定排序。
基础算法, 排序
DAG 上的最短路径问题
DAG 即有向无环图，DAG 上的最短路径先对图做拓扑排序，按照拓扑序列依次取出每个顶点，对它的所有出边执行松弛操作即可求出单源最短路径；该算法可以处理负权边，不能处理负环（DAG 本身不存在环），时间复杂度 O(n+m)，效率优于 Bellman‑Ford 与 SPFA。
基础算法, 最短路径问题
Floyd-Warshall 算法
Floyd‑Warshall 算法是基于动态规划的全源最短路径算法，可求解图中任意两点最短距离，支持负权边，适合小规模稠密图，也能够检测图中的负权环。
基础算法, 最短路径问题
增量式 Floyd 算法
增量式 Floyd 在标准 Floyd 基础上，按顺序逐步加入中间节点 k，动态更新任意两点间最短路径，支持节点逐个新增的场景；它复用之前已算好的路径结果，不必每次从头完整重跑，适合图中节点不断增加的问题，时间复杂度仍为\(O(n^3)\)。
基础算法, 最短路径问题
二分查找
二分查找针对有序序列，每次取中间元素和目标对比，减半缩小查找范围，时间复杂度 O (log n)，查找效率高。
基础算法
快速排序
快速排序基于分治思想，选取一个基准元素，把数组划分成小于基准和大于基准的两部分，再递归对左右子区间继续划分排序；平均时间复杂度\(O(n\log n)\)，最坏\(O(n^2)\)，属于不稳定排序，不需要额外开辟大量辅助空间。
基础算法, 排序
Dijkstra 算法
Dijkstra 算法是图论中经典的贪心算法，依托松弛操作求解非负边权带权图的单源最短路径，广泛运用于路径规划、网络路由等各类工程场景。
基础算法, 最短路径问题
Prim 算法
Prim 是求解最小生成树的算法，从任意顶点出发维护一个已选顶点集合，每次选取连接集合内外、权值最小的边，将对应顶点并入集合，直到包含全部顶点；朴素实现 O(n^2) 适合稠密图，堆优化版本 O(mlog n) 适合稀疏图，支持负权边。
基础算法, 最小生成树问题
查找 s-t 路径
给定图中起点 s 与终点 t，判断是否存在一条从顶点 s 到顶点 t 的路径，通常可用深度优先搜索或广度优先搜索求解，有路径则 t 从 s 可达，否则不可达。
基础算法, 单源单汇路径问题
Bellman-Ford 算法
SPFA 是 Bellman‑Ford 的队列优化版本，用于求解带负权边的单源最短路径，只将被松弛成功的顶点入队，避免无效松弛；通过记录顶点入队次数，若某点入队超过顶点总数，即可判定存在负权回路，平均时间复杂度较低，最坏仍为 O (nm)。
基础算法, 最短路径问题
Kruskal 算法
Kruskal 是求解最小生成树的算法，核心思路是将全部边按权值从小到大排序，依次选取边，借助并查集判断边的两个端点是否属于不同连通块，若不连通就把这条边加入生成树，直到选出 n‑1 条边；适合稀疏图，时间复杂度主要由排序决定 O(mlog m)，可以处理带负权的边。
基础算法, 最小生成树问题
插入排序
插入排序的核心思想是将数组分为已排序和未排序两部分，依次取出未排序部分的元素，向前遍历已排序部分找到合适位置插入，不断扩大有序区间直至整个数组有序，适合小规模数据，时间复杂度最坏为 O (n²)。
基础算法, 排序
归并排序
归并排序采用分治思想，先把数组不断对半拆分成子数组，对子数组排序后，再将两个有序子数组合并为一个有序数组；时间复杂度稳定为 O (nlogn)，需要额外辅助空间，是稳定排序算法。
基础算法, 排序
二部图判断
二部图判断即检验图能否把顶点划分成两个互不相交集合，使得每条边的两个端点分别属于不同集合，不存在同一集合内部的边；可通过 BFS 或 DFS 进行染色，若发现相邻顶点颜色相同则不是二部图，无冲突则为二部图。
基础算法
汉诺塔问题
汉诺塔是一个经典的数学谜题，其核心在于运用递归思维，在遵循“大盘不能压小盘、一次只移一片”等规则下，将整体移动过程拆解为规模更小的子问题，最终把所有圆盘原样转移到目标柱。
基础算法
斐波那契数列
斐波那契数列指从 0、1 开始，后续每一项都等于前两项之和的数列，即 0，1，1，2，3，5，8……，它频繁出现在植物生长、自然形态中，同时在算法、递归、黄金比例相关问题里有着广泛应用。
基础算法