兄弟们一聊到“十大基础算法”很多人脑子里先蹦出来的是大学《数据结构》课上被冒泡排序支配的恐惧或者是LeetCode刷题时那个永远超时的暴力解。说实话我在刚入行那几年也这样认为算法就是面试造火箭、工作拧螺丝。直到后来真正处理过几千万级的数据、调过嵌入式设备的实时响应、亲手把接口的耗时从几秒压到几十毫秒才反过来把基础算法重新翻出来咀嚼了一遍。今天这篇就不绕弯子了直接把我自己心里那张“十大基础算法”清单摊开讲。这个清单不是按教科书目录排的而是我按“实际打工人用得上的高频度”来选的覆盖排序、搜索、策略设计、图论、字符串、数值优化几条主线。不管你是刚入门的学生、想跳槽的面试党还是已经在业务代码里泡了多年的老哥这十个算法都值得再来一遍。我会把每个算法的使用场景、底层逻辑、代码骨架和踩坑点都聊透最后再送上一份自测和排查指南保证看完能直接上手。1. 内容整体设计与思路拆解1.1 为什么是这十个算法而不是别的刚开始列清单时我脑补过很多候选红黑树、跳表、布隆过滤器、LSTM……这些都是大名鼎鼎的东西但真要从“基础”和“高频”两个维度筛它们的普适性还是差了点。我最终选定的十大类是这样的排序算法快速排序、堆排序、归并排序二分查找包括二分区间的各种变体哈希与查找表贪心算法动态规划图的遍历BFS与DFS最短路径算法Dijkstra字符串匹配KMP分治思想启发式优化粒子群/模拟退火这里有个很微妙的地方前九个是传统计算机科学的基础第十个是我故意加进去的“现代拉练项”。原因很现实你现在去企业中台团队或者算法岗位面试官大概率会从前九个里抽两个考你代码功底再从第十个里抽一个问问你工程落地经验。我见过太多人能把快排背得滚瓜烂熟但被问到“一个非凸优化问题业务里到底怎么搞”时直接卡壳。所以这份清单本质上是一条“稳中有进”的路线图。1.2 这些算法解决的到底是什么问题如果给这十个算法归归类你会发现它们其实是在解决四种底层诉求排布、寻找、决策、逼近。排布就是排序场景数据无序得先变得有序寻找则涵盖了二分查找、哈希和图的搜索路径决策更多是贪心和动态规划在做选择把一个大问题拆成一个挨一个的小选择贪心选局部最优动态规划则通过记录各种状态来逼近全局最优逼近则是启发式优化算法的强项遇到没有解析解、复杂度又高到炸的问题时不再求绝对精确而是用迭代的方式找到一个“足够好”的解。为什么要反复强调这种归类因为我发现很多新手学算法的通病是这样的每种算法都认识但不知道它们之间的替代关系和应用边界。你跟他说“用动态规划不用贪心”他不知道为什么你跟他说“用Dijkstra不用BFS”他也只能背出“Dijkstra有权重、BFS没权重”这句话却不知其所以然。所以后面每个算法的解读我都会刻意带上“它和相邻算法的较量”这个视角。2. 核心细节解析与实操要点2.1 排序算法不只是冒泡和快排先聊最通俗的排序。很多人一提排序脑海里第一反应就是冒泡排序。上课时用它理解算法思想确实不错但真正到工程界冒泡基本没人会直接拿去排序大批量数据。理由很简单它的平均时间复杂度和最坏时间复杂度都是O(n^2)数据量一上几千就原形毕露。我在实际项目里最常用的是快速排序和归并排序偶尔用堆排序三者各有侧重。快排的平均复杂度是O(n log n)通过一个pivot把序列分成左右两半然后递归处理。它最大的优点是原地排序in-place不占额外内存所以很多语言内置的排序方法底层用的都是快排的变体。这里要特别提醒快排的最坏情况是O(n^2)比如对已经排好序的数组做快排如果pivot选得不好比如每次都选第一个性能会瞬间崩盘。工程上的标准做法是“三数取中”选pivot或者随机选pivot来尽量规避这种退化。归并排序则相反它的复杂度是稳定的O(n log n)不管输入数据原本多乱都能保证这个上界但代价是空间复杂度O(n)因为需要额外数组来合并左右两个有序子序列。所以它特别适合处理链表排序、外部排序比如数据量大到内存放不下、要放磁盘时。我当年处理一个上亿条记录的外部排序需求时用的就是归并的思路把大文件切成小块每块内部排序后写回磁盘再逐块归并。堆排序相对小众一点但它的优点是既能保证O(n log n)的复杂度又能做到原地排序不需要额外空间。它的思想是利用完全二叉树维护一个大顶堆或小顶堆每次把堆顶和堆尾交换再重新调整堆结构。不过它的常数项比快排大实际执行速度往往不如快排所以业界一般把它用在“需要同时保证最坏情况和原地空间”的场景比如实时流处理里要维护一个Top K的窗口众数。注意工程上除非数据量极小且你喜欢折腾否则不建议自己手写排序直接使用语言标准库的排序方法就好。但面试和底层原理学习时手写一遍这三种排序仍然非常值得——它们能检验你对递归、分治、数组操作这些基本功的掌握程度。2.2 二分查找每次排除一半的优雅二分查找可能是“看起来最简单、写起来最容易错”的算法。它核心的前提是数据必须有序每次拿中间值与目标比较等于直接命中小于则去右半边找大于则去左半边找整体复杂度O(log n)非常快。但真正落地时最大的坑在于边界条件。经典问题有取中位是用(left right) / 2还是left (right - left) / 2后者更安全因为避免了两个很大整数相加导致溢出的情况。然后循环条件是left right还是left right更新区间时是mid - 1、mid 1还是直接用mid这组组合一旦记错就会出现死循环或者漏解。更进阶一点实际工程里的二分查找很多时候不是“找某个精确值”而是“找左侧边界的值”或“找右侧边界的值”比如要在有序数组中找一个大于等于目标值的最小索引或者小于等于目标值的最大索引。这类变体在Java的Arrays.binarySearch、C的lower_bound、upper_bound这些API里都有现成实现。建议你写代码时不要死记模板而是把区间不变量的概念想清楚你确定答案在[left, right]区间内吗每次排除掉一半后新的区间还包含答案吗想明白这一点所有边界问题都能迎刃而解。这个算法远不止用在数组里凡是具有“单调性”的对象都能二分。比如温度传感器校准场景中我们需要反查中位温度对应的AD值用的就是二分思想ADC曲线整体单调给定一个目标温度值能快速定位到对应的量化区间。再比如Linux磁盘寻道算法里的LOOK/CLOOK调度策略本质上也是在“按柱面号排序后的请求队列”中快速寻找下一个最接近当前磁头位置的请求排序二分的组合直接决定了磁盘IO性能。2.3 哈希拿空间换时间的经典策略哈希的工程地位不用多说它把查找时间从O(n)降到接近O(1)。核心是设计一个好的哈希函数让不同数据能均匀地映射到哈希桶中。常见的哈希函数包括除留余数法、乘法哈希、一致性哈希多用于分布式缓存、以及加密哈希MD5、SHA-256等。哈希最容易遇到的麻烦是冲突。当两个不同的数据映射到了同一个桶工程上常用拉链法链表存储或开放寻址法向后找空位来解决。很多语言的标准库已经把这些细节封装好了比如Java的HashMap在冲突超过阈值时会转成红黑树C的unordered_map底层也是哈希表。但我特别想强调一个方向在算法题和面试场景里哈希和“记忆化”经常紧密结合。比如斐波那契数列的计算如果直接递归时间复杂度是O(2^n)分分钟卡死但用一个哈希表记录每个n对应的计算结果就变成了O(n)。这其实就是动态规划中“状态缓存”的雏形哈希在这里扮演的是“算过的结果存起来下次直接取”的备忘录角色。同理两数之和、LRU缓存等经典场景也都离不开哈希表。哈希有一个显著的局限它对数据分布比较敏感。如果哈希函数设计不当或者负载因子过高哈希表的性能会急剧退化从O(1)变成O(n)。所以在实际项目中选择哈希容器时要注意预估数据量提前分配好初始容量必要时调整负载因子避免频繁扩容导致性能抖动。2.4 贪心算法与动态规划决策问题的两大流派贪心算法和动态规划Dynamic Programming缩写DP经常被放在一起讨论因为它们都是解决“多阶段决策”问题的思路。它们的核心差别在于贪心是每步都只选当前看起来最好的不考虑未来的影响所以它能得到局部最优解但不保证全局最优动态规划则通过枚举所有可能的状态用递推公式把“所有过往步骤的代价”记录下来从而能求得全局最优解。一个常被拿来做对比的经典问题是“零钱兑换”给你若干面额的硬币凑出指定金额最少需要几枚硬币如果硬币面额是1、5、11目标金额是15贪心会先选11再选4个1总共5枚但实际上3枚5分硬币就能解决问题。这就是贪心失效的典型例子。在这种场景下必须用动态规划定义dp[i]表示凑出金额i需要的最少硬币数递推公式是dp[i] min(dp[i - coin] 1 for coin in coins)从1一直算到15。动态规划听起来高深其实核心就是“确定状态 - 写转移方程 - 初始化边界 - 按顺序计算”。这里面最难的往往不是写方程而是找出“状态是什么”。我自己的经验是先想清楚这个题目里“我们到底要记录哪些信息”才能忽略掉其他噪音信息。比如背包问题里的状态就是“背包容量”和“可选的物品”这两个维度矩阵路径问题里的状态就是“走到哪个格子”。实际工程里贪心算法的应用范围其实比DP更广因为它速度快、实现简单。比如霍夫曼编码、活动选择会议室分配、最小生成树Prim算法、Kruskal算法、区间调度等这些领域已经证明贪心能拿到最优解。而DP更常见于路径规划、编辑距离、特征选择、资源分配等需要精确优化的场景。需要特别提醒的是使用贪心算法前必须证明“贪心选择的局部最优不会阻碍后续得到全局最优”否则就老老实实上动态规划甚至分支限界。2.5 图遍历与最短路径从BFS/DFS到Dijkstra图和树相关的算法在面试中的出场率非常高。最基础的是两种遍历方式深度优先搜索DFS和广度优先搜索BFS。DFS本质上是沿着一条路走到黑再回头探索其他分支BFS则是按层扩展先遍历距离起点为1的所有节点再遍历距离为2的节点。它们各自有合适的业务场景。DFS适合搜索所有可能的解比如八皇后问题、迷宫寻路的所有路线、组合枚举BFS则适合寻找最短路径比如“最少点击次数”“最少转机次数”“社交关系几度人脉”这类场景——只要每条边的代价相同BFS第一次到达终点时的路径就是最短路径因为它按层扩散天然保证步数最少。但是一旦边上有了不同的权重比如地图导航里的路程距离、网络路由里的延迟时间BFS就不灵了。这时候需要Dijkstra算法。它的思路是维护一个“当前已知最小距离”的优先队列每次从队列中取出距离起点最近的节点尝试通过它去松弛相邻节点的最短距离直到所有节点都被处理完。它的算法复杂度可以做到O((VE) log V)堆的优化贡献很大这也是为什么堆排序和Dijkstra经常被一起提及的原因。Dijkstra有一个致命限制不能处理负权边。一旦图中出现负权边算法就会因为“已经确定最短路径的节点被负边再次更新”而陷入错误。处理负权边的场景需要Bellman-Ford算法不过业务中遇到的机会相对较少。还有一类场景是不需要全图最短路径、只关注两个点之间的最短连通性这时A算法会更有优势因为它用启发式函数引导搜索方向能显著减少搜索空间。A和BFS的取舍我遇到过几次BFS实现简单但没有方向感节点多时会很慢A*虽然要额外设计启发函数但在点数量大的地图场景里效果天差地别。2.6 字符串匹配从暴力到KMP字符串匹配是面试里很爱考的一类问题。最简单的暴力匹配是逐个位数错位地模式串与文本串比较时间复杂度O(n*m)n是文本长度m是模式串长度。当文本很长而模式串也相对较长时暴力算法会很吃力。KMP算法是教科书级的改进。它的核心思想是当某个字符匹配失败时不把模式串的指针全部退回开头而是利用已经匹配过的信息跳过那些必定不可能匹配的位置。这个“跳过的依据”就是通过预计算模式串的next数组也叫部分匹配表、前缀函数得到的。我当年学KMP时最难理解的就是next数组的计算。它本质上是在问对于模式串的每个位置i其前缀子串pattern[0..i]中最长的相等前后缀的长度是多少。有了这个信息就可以在失配时把模式串的指针回溯到这个“最长相等前缀”的后面而不是回到0。很多人会把next数组实现成next[j] 最长相等前后缀长度但为了编程方便有时会用错位的版本。建议初学者先理解后一种再优化代码不要一上来就背模板。实际业务中KMP的应用不算多因为很多语言的标准库已经内置了高效的字符串查找函数比如Java的indexOf底层就使用了类似KMP或Boyer-Moore的算法但KMP的思想在正则表达式引擎、编辑器语法高亮、文本去重、基因序列比对等场景里仍然有它的影子。另外理解前缀函数对解决“重复子串检测”“字符串循环节”等问题也很有帮助。2.7 分治把复杂问题拆到最小单元再合并分治思想的核心只有八个字分解、解决、合并。它把一个大问题分解成若干结构相同的子问题递归地解决子问题再把子问题的结果合并成原问题的答案。最有代表性的分治算法除了归并排序还有快速幂、大整数乘法、最近点对等。我印象最深的是在一次风控特征计算中需要对数百亿条交易记录做用户维度的聚合统计单机内存根本放不下。当时的思路就是把全量数据按用户ID哈希分区每一路分片交给一个计算节点独立做局部聚合最后再做一次合并。如果这还不叫分治那就没有分治了。分治的难点在于如何确定“合并”这一步的逻辑。很多初学者能很快写出递归分解的代码但卡在合并上——不知道两个子问题的结果如何组合成父问题的结果。我建议画图辅助理解把原始问题画成一个完整矩形把两半结果分别涂上颜色思考两个子结果的重叠部分是不是需要特殊处理。比如逆序对计数单纯的归并排序合并阶段需要额外统计“右边数字小于左边数字”的次数这就是合并环节里嵌入的重点逻辑。有一点容易让人混淆分治和动态规划的区别。分治的子问题通常是彼此独立的比如归并排序的左右两个子数组之间没有重叠而动态规划的子问题往往是重叠的需要用表来缓存重复计算。如果一个分治问题在递归时反复计算同一个子问题那就说明它更适合DP。2.8 启发式优化当精确解算不动时很多同学看到“十大基础算法”里放进粒子群算法PSO和模拟退火SA可能会觉得突兀。但我要说这俩在现代工程里的应用频率真不比KMP低尤其是面对大规模组合优化和非凸问题时。经典的精确算法比如整数规划、动态规划在问题规模飙升时会面临“组合爆炸”状态数呈指数级增长算到世界末日也算不完。启发式算法走的是另一条路不追求绝对最优解而是在有限时间内找到一个“足够好”的解。粒子群算法模拟鸟群觅食每个粒子代表候选解粒子有位置和速度每次都朝着“自己历史上最好的位置”和“全群体历史上最好的位置”方向更新配合惯性权重与随机扰动探索解空间。模拟退火则模拟金属退火过程在搜索过程中既接受“更优”的答案也以一定概率接受“更差”的答案从而跳出局部最优。拿粒子群举例核心公式可以简写为v[i] w * v[i] c1 * rand() * (pbest[i] - x[i]) c2 * rand() * (gbest - x[i]) x[i] x[i] v[i]其中w是惯性权重c1是自我认知系数c2是群体认知系数。调参是个经验活w太大粒子飞得太野收敛慢w太小容易陷入局部最优。一般做法是让w从0.9线性衰减到0.4前期多探索、后期多收敛。启发式算法在工程上的典型应用包括调度排产、路径规划、神经网络结构搜索、推荐系统特征权重重排序等。说句实在话这类算法的上线效果高度依赖问题建模和参数调优没有“一次调好”的捷径必须结合具体业务数据反复实验。但它确实是面对复杂优化问题时性价比非常高的实用方案。3. 实操过程与核心环节实现3.1 从零手写二分查找一个不踩边界的模板下面我用Python演示一个标准的二分查找模板这个模板适用于“在有序数组中寻找第一个不小于目标值的位置”也就是Clower_bound的语义def lower_bound(nums, target): left, right 0, len(nums) # 右边界取开区间代表搜索区间是 [left, right) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left这里的关键设计是右边界right始终是开区间的不包含位置所以当nums[mid] target时说明mid及其左边都不可能是答案直接把左边界推进到mid 1反之mid可能是答案但右边也可能存在更靠左的满足条件的值所以把右边界收缩到mid。循环终止时left right就是第一个不小于目标值的位置。如果要求“寻找最后一个不大于目标值的位置”upper_bound的前驱只需要把循环体内的比较方向稍做修改。我强烈建议你按这个模板反复手写几遍直到形成肌肉记忆。记住只要维护好“区间内是否还包含答案”这个不变量就永远不会写出死循环。3.2 手写快速排序与归并排序的要点对比快速排序的经典递归实现如下def quick_sort(arr, left, right): if left right: return pivot_index partition(arr, left, right) quick_sort(arr, left, pivot_index - 1) quick_sort(arr, pivot_index 1, right) def partition(arr, left, right): pivot arr[right] # 选择最右元素作为pivot i left - 1 for j in range(left, right): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[right] arr[right], arr[i 1] return i 1这段代码的关键是partition中的双指针技巧i指向“已处理区间里最后一个小于pivot的元素”j遍历整个区间遇到比pivot小的元素就交换到i1位置。最后把pivot放到正确的位置上它的左边全部小于pivot右边全部大于等于pivot。归并排序的合并阶段则是这样def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i j 0 result [] while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result注意归并排序在Python里如果用切片会额外产生很多新数组空间开销比较大。工程上如果真要手写归并建议使用“全局辅助数组索引区间”的方式在递归过程中复用同一块辅助内存减少频繁分配的开销性能会提升不少。3.3 动态规划实战以零钱兑换为例题目还是前面提过的零钱兑换先定义状态dp[i]表示“凑出金额i所需的最少硬币数”如果无法凑出则设为无穷大。初始化dp[0]0然后从1到amount依次计算def coin_change(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if i coin: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这段代码的时间复杂度是O(amount * len(coins))空间复杂度是O(amount)。如果amount很大比如到10^9级别这个算法就不可行了。那时候就要考虑BFS按“步数”扩散的解法因为金额空间再大步数小得多BFS可以用队列一层层搜索配合哈希去重也能在有限步数内命中目标。这种“DP不好使就换搜索思路”的思维方式在真实竞赛和工程里非常有用。3.4 Dijkstra算法从优先队列写法到业务优化Dijkstra的标准实现依赖优先队列最小堆。思路是维护一个dist数组初始时所有节点的距离设为无限大起点为0。把起点放入堆中每次从堆中弹出距离最小的节点如果该节点已经被处理过即出堆时的距离大于已记录的最短距离则跳过否则遍历它的邻接边尝试更新相邻节点的距离import heapq def dijkstra(graph, start, n): dist [float(inf)] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return dist这里最容易出错的是建图时的边存储方式。如果边很稠密比如城市数量5000道路数量50万用邻接矩阵会导致内存直接爆炸邻接表是首选。我还遇到过一种情况图里存在负数权重的“伪负边”起因是业务数据里某个时间差被转成了负数结果Dijkstra报出很离谱的路径。排查到最后才发现是对原始数据的清洗出了问题而不是算法写错了。所以用Dijkstra之前一定再三检查边的权重是否为非负同时审视数据源是否干净。3.5 KMP算法手推next数组与匹配过程KMP的next数组最直白的定义是next[i]表示模式串P[0..i]中最长相等真前后缀的长度。以模式串ABABC为例next[0] 0因为单字符没有真前后缀。next[1] 0AB的真前缀A和真后缀B不相等。next[2] 1ABA的真前缀A和真后缀A相等长度为1。next[3] 2ABAB的真前缀AB和真后缀AB相等长度为2。next[4] 0ABABC没有一个相等的前后缀。在匹配阶段假设文本串是ABABDABABC用模式串去匹配当匹配到P[4]C和文本中D时失配常规暴力会退回文本串下一个位置。但KMP知道next[3]2于是直接把模式串的指针从4回跳到了2继续尝试比较P[2]A和当前的文本字符D省去了前面已知不会匹配的重复比较。这个算法的精妙之处在于它把“模式串自身的结构”提前告诉给了匹配器。我在实际业务中接触过浏览器里的搜索高亮功能如果自己实现一个简易版KMP确实能在大文本上显著减少无谓的指针回退尤其是模式串很长且和文本串有大量重合字符时。3.6 粒子群算法求解极值问题完整流程举一个小案例求函数f(x, y) x^2 y^2在[-10, 10]区间上的最小值。理论上答案是(0,0)但我故意用PSO来演示调参流程第一步初始化随机生成30个粒子每个粒子有二维位置(x, y)和二维速度(vx, vy)。第二步计算每个粒子的适应度f(x, y)更新个体最优pbest和群体最优gbest。第三步迭代更新速度与位置。第四步判断是否达到最大迭代次数比如100次或连续多次迭代gbest变化很小则终止。下面是一段极简实现import random def pso(f, dim2, n_particles30, max_iter100, w0.7, c11.5, c21.5): # 初始化 x [[random.uniform(-10, 10) for _ in range(dim)] for _ in range(n_particles)] v [[random.uniform(-1, 1) for _ in range(dim)] for _ in range(n_particles)] pbest [p[:] for p in x] pbest_val [f(*p) for p in pbest] gbest_idx min(range(n_particles), keylambda i: pbest_val[i]) gbest pbest[gbest_idx][:] gbest_val pbest_val[gbest_idx] for _ in range(max_iter): for i in range(n_particles): for d in range(dim): r1, r2 random.random(), random.random() v[i][d] w * v[i][d] c1 * r1 * (pbest[i][d] - x[i][d]) c2 * r2 * (gbest[d] - x[i][d]) x[i][d] v[i][d] x[i][d] max(-10, min(10, x[i][d])) # 边界处理 val f(*x[i]) if val pbest_val[i]: pbest[i] x[i][:] pbest_val[i] val if val gbest_val: gbest x[i][:] gbest_val val return gbest, gbest_val跑下来的结果通常会收敛到(0,0)附近精度取决于迭代次数和参数设置。实际工程里通常还会加入“收敛早停”机制不然就是白烧CPU。另外PSO本身不保证每一步都在约束域内所以要在位置更新后强制裁剪边界不然很容易生成不可行的业务方案。4. 常见问题与排查技巧实录4.1 排序和二分场景的典型坑排序这块最常见的坑有三个。第一个是没有区分稳定排序和不稳定排序比如先按时间排序再按优先级排序如果第二个排序不是稳定的前面按时间排好的顺序全被打乱。归并排序是稳定的快排一般不稳定这个点面试时经常被追问。第二个是排序比较器没写对重写compare时的返回正负号方向搞反导致结果与期望相反。建议写完比较器后拿一个三个元素的简单数组先自测一遍。第三个是大数据量排序时没有考虑内存能走数据库ORDER BY就走数据库不要在应用层把所有数据加载到内存再排序千万条数据直接OOM。二分查找的排查集中在边界值。常见的测试用例包括空数组、长度为1的数组、目标值小于所有元素、目标值大于所有元素、数组中有重复目标值。我建议你把这五个case全部过一遍基本能覆盖90%的边界错误。另外如果你写的是“精确查找某个值”循环条件建议用left right而且更新时为left mid 1、right mid - 1如果你写的是“查找边界”用我前面展示的开区间写法思路最清晰。两者混着写是最容易出bug的直接原因。4.2 动态规划状态设计踩坑记录DP的常见问题主要症状是“答案差一点”“结果偏大或偏小”。原因多数出在初始化边界不对。比如零钱兑换里如果dp[0]忘了设为0或者设成了1整个递推都会乱掉。再比如背包问题中二维DP的dp[i][0]和dp[0][j]都要按题意初始化否则合并阶段错误传播。另一个高频错误是遍历顺序写反。以完全背包为例如果允许重复选取物品内层循环需要从前往后遍历容量如果是0-1背包内层循环需要从后往前遍历容量否则一个物品会被选取多次。这个问题我刚学DP时栽过好多次。排查时最容易的办法是打印DP表格把每一行每一列打印出来对照手工推导的前几步看看递推是否一致基本一眼就能定位是不是遍历方向搞错了。4.3 图算法常见故障与性能瓶颈排查图遍历和Dijkstra在工程上的问题第一类是“图很大、递归栈爆了”。DFS如果递归深度达到几十万层程序会直接栈溢出。解决办法是把递归改成显式的栈手动模拟DFS或者换成BFS。第二类是没有正确标记已访问节点导致图中出现环时死循环。尤其是无向图场景BFS/DFS都要在入队/入栈前标记否则会出现重复访问甚至无限循环。第三类是优先队列中的旧记录没有淘汰造成堆越来越大。我在3.4的代码里加了if d dist[u]: continue这行就是专门用来跳过那些已经被更新过的旧记录的没有这行堆的尺寸会以非常恐怖的速度膨胀。碰到Dijkstra结果不对先怀疑权重是不是存在0权重边导致多个最短路径是不是存在负数权重如果确认是负权边老老实实换Bellman-Ford如果只是稀疏图可以考虑SPFA短作业优先队列优化的Bellman-Ford但它的平均性能不错最坏性能依然不稳定线上慎用。4.4 KMP与字符串匹配的边界测试KMP最容易错的是next数组的定义没搞明白。我见过很多人拿next数组去直接跳转时差了1个位置导致匹配结果始终错位。建议先完整手推一遍模式串的next再用一个简单文本串人工模拟匹配流程千万别直接上代码。另外要特别关注模式串长度为0和文本串长度为0的情况很多库函数对空模式串会抛出异常自行实现时要提前做防御判断。如果匹配的目标是在长文本中找所有出现位置注意在找到一次匹配后要继续把模式串指针指向next[m-1]或者next[m]而不是从头开始。否则会漏掉重叠出现的匹配比如文本AAAAA找AA应该出现4次若从头重新匹配就只剩3次。4.5 启发式算法调试备忘录粒子群和模拟退火这类算法最让人头疼的问题就是“结果不稳定”“时好时坏”。这本质上是随机算法带来的正常波动但工程上必须想办法压制。我的建议是固定随机种子比如42这样每次运行结果可复现方便回归对比参数效果。另外把迭代过程中的gbest变化曲线打印出来能看到收敛速度。如果曲线一路下降很快说明参数可行如果下降很慢甚至震荡可能需要调低c1和c2或者增大w的衰减速度。模拟退火的常见参数陷阱是初始温度设得过低导致算法过早收敛到局部最优。通用做法是先用一个预跑阶段计算若干随机解的方差把初始温度设定为这个方差的一个倍数让算法初期有足够概率接受差解。工程上常有“跑了半小时结果不如随机猜测”的情况多半是目标函数建模错误或者约束条件没处理好而不是算法本身不靠谱。5. 知识链接与学习路径建议5.1 十大基础算法与其他数据结构的对应关系算法不能脱离数据结构单独谈。排序算法离不开数组和链表二分查找依赖有序数组如果是动态插入删除的场景可以换成二叉搜索树或者跳表来维持有序性哈希表本身就是一种数据结构图的BFS/DFS需要队列/栈辅助Dijkstra依赖优先队列KMP依赖字符串与next数组本质上也是一维数组动态规划几乎离不开“状态表”通常就是二维或多维数组。理解这些对应关系有助于你在不同场景下快速选型。比如一个业务需求要频繁“找到第一个大于当前时间的时间点”如果数据量不大且变动不频繁直接维护有序数组二分即可如果数据量很大且频繁插入那就要用红黑树TreeMap或者跳表了因为数组扩容和插入的成本太高。5.2 从面试准备到工程落地的算法进阶路线如果你正在求职我建议的刷题顺序是数组与链表 - 栈与队列 - 哈希 - 排序 - 二分 - 递归与回溯 - 贪心 - 动态规划 - 树与图 - 字符串。每一类至少刷20道经典题把每一道的状态定义和转移方程自己推一遍不要直接看题解抄代码。高频算法题比如LeetCode的Hot 100题可以按这个顺序反复刷三轮第一轮看懂第二轮默写第三轮限时盲写。如果你已经工作有了具体的业务场景建议反过来学先从实际问题出发把问题抽象成“排序、搜索、决策、逼近”中的某一类再去查对应的算法。比如业务方提了个需求“给几万个任务排个最优顺序让总等待时间最短”这大概率是贪心或动态规划问题。这时候带着问题去学效率比漫无目的地刷题高得多。而且你要学会画算法流程图不光是给同事讲需求时用更重要的是给自己理思路。我自己的习惯是先在白板上把输入、输出、约束条件、边界情况都列清楚再根据流程图写代码这样做能少写至少一半的debug时间。5.3 算法工程化落地时要不要重新造轮子现在很多语言的标准库和开源框架已经实现了大部分算法比如C的STL里有std::sort、std::lower_bound、std::priority_queueJava有Arrays.sort、Collections.binarySearch、TreeMapPython有sorted、bisect、heapq。除非有特殊的性能要求或者学习目的否则我建议优先使用这些经过充分测试的实现。但反过来说理解算法原理永远不会过时。原因有三点第一标准库不一定覆盖所有变体。比如带条件的二分查找、多维约束的最短路、带概率的采样策略都需要自己扩展。第二当你需要做性能调优时不知道底层复杂度是没法定位瓶颈的。第三跨语言迁移时能大大降低学习成本比如你懂KMP去写Go、Rust、Rust标准库里没有的字符串匹配逻辑也能手到擒来。6. 写在最后的个人体会做了这么多年开发我最大的体会是算法这东西学的时候觉得抽象用的时候才知道值钱。我自己刚工作那会儿遇到一个“订单量在短时间内暴增导致排序服务超时”的问题第一反应是加服务器、加内存后来一查发现数据量从十万涨到千万系统里用的还是O(n^2)的插入排序换成了标准库的O(n log n)排序后耗时直接降了一个数量级。从此以后我再也不敢小看“基础”二字。另外想特别说一句算法学习不是一锤子买卖它需要经常温习。我自己的习惯是每隔一段时间就写一个算法速览表每个算法写上适用条件、复杂度、常见坑位、代码骨架遇到新的业务问题就去查这张表。这张表更新到现在已经有几十条了有时候连我自己都惊叹原来这些年用到的算法早就远远超过了“十大”的范围但地图的起点始终是这些最基础的东西。如果这篇文章里的某一段能帮你在面试中多拿一轮offer或者在改bug时少熬一个夜那就算我没白写。最后送大家一个建议找一个你业务里反复出现的小问题用最朴素的写法先实现再尝试用今天聊到的算法去优化它对比前后的耗时和代码复杂度你一定能真切感受到算法的魅力。