我统计过自己这几年写下的 Python 代码真正跟刷题算法重合的部分不到三成但恰恰是这三成——排序、二分、堆、并查集、BFS、滑动窗口——在关键时刻救过场一次是把一个跑了四十多分钟的对账任务压到两分半一次是把一个内存爆掉的图遍历改成了可控的迭代版本。所以当有人问我Python 经典算法有哪些、Python 算法大全该怎么学的时候我一般不会甩一份清单过去而是先反问一句你是要应付面试还是要让线上那段代码别再把 CPU 吃满。这两个答案指向的算法集合重叠度很高但优先级排序完全不一样。这篇东西就是把我自己踩过的路径整理出来Python 里那些真正称得上经典的算法分别解决什么问题、官方标准库已经替你实现了哪些、哪些必须自己手写、手写时最容易在哪一行翻车。不管你是刚接触算法的新手还是写过几年代码但一直靠sorted和in混日子的老手下面这些内容应该都能抠出点能直接用的东西。1. 先把Python 算法大全这个词拆开看1.1 面试算法和工程算法的分层差异网上流传的Python 经典算法大全清单绝大多数是按刷题平台的知识树排的数组、链表、哈希、双指针、二分、递归、回溯、贪心、动态规划、图论、位运算。这套体系没问题它覆盖了计算机科学里最核心的思维训练。但如果你直接照着它去写业务代码会发现一个尴尬的事实里面一大半算法标准库或者第三方库已经做到你手写永远追不上的程度。我习惯把算法分成三层来看这个分层决定了你该花多少时间在手写上层级典型内容处理策略标准库已实现层排序、二分查找、堆、双端队列、有序字典、字符串查找优先用库但要懂边界和复杂度必须手写层并查集、拓扑排序、滑动窗口、回溯剪枝、状态压缩 DP必须能手写且要写得能过性能关框架/库替代层最短路、最小生成树、最大流、矩阵运算小规模手写练思维生产环境上专用库这张表的意义在于省时间。新手最容易犯的错是把排序算法全家桶背得滚瓜烂熟却在需要 Top-K 的时候写了个全量排序反过来老手容易过度依赖库遇到需要自定义合并规则的场景就抓瞎。1.2 Python 这门语言给算法带来的特殊约束Python 写算法和其他语言有个根本差异解释执行带来的常数开销极大。同一份快速排序C 写出来可能比 Python 快几十倍。这意味着在 Python 里算法复杂度的常数项往往比复杂度本身更能决定成败。举个具体的一个 O(n log n) 的归并排序如果每一层都做大量的列表切片和拼接实际耗时可能比一个常数优化良好的 O(n²) 插入排序还慢——在 n 小于几百的时候这几乎是必然的。我实测过对 200 个随机整数排序纯 Python 手写插入排序和sorted()的差距在 10 倍以内但手写归并的差距能到 30 倍以上因为递归调用加临时列表分配的成本太高了。所以学 Python 算法有个隐含前提你要知道哪些操作在 Python 里是贵的。列表中间插入删除贵、递归调用贵、属性访问贵、全局变量访问贵而内置函数、列表推导式、切片、sum、min、max、any、all这些由 C 层实现的操作用起来便宜得多。后面每一节我都会点出对应的性能雷区。2. 排序与查找从 sorted 的边界往外扩一圈2.1 Timsort 到底帮你做了什么什么时候必须绕开它Python 的sorted()和list.sort()用的是 Timsort这是个归并排序和插入排序的混合体。它的核心设计是识别输入中已经有序的片段术语叫 run对短 run 用二分插入排序扩展再两两归并。默认最小 run 长度是 32 或 64跟实现版本有关。带来的直接结果是最好情况 O(n)最坏和平均都是 O(n log n)并且稳定。稳定这个性质很多人不当回事实际很关键。比如你要按分数降序排学生名单同分的保持原顺序直接sorted(students, keylambda s: -s.score)就完事不用额外加索引。如果你手写快排这个稳定性就没了得用排序键 原索引的元组来补救白白多一层开销。那什么时候必须绕开sorted第一种是需要部分排序。你要从一百万个元素里取最大的十个全量排序是 O(n log n)而维护一个大小为 10 的最小堆只要 O(n log k)差距在两个数量级以上。第二种是数据流式到达你没法一次性拿到全部数据。第三种是排序键的计算成本极高而你想复用中间结果——这时候可以自己控制装饰-排序-去装饰的节奏。提示sorted对 key 函数的调用次数是严格的 n 次不是 n log n 次。它内部会先把每个元素映射成 (key, index, value) 的元组再排。所以哪怕 key 里做了复杂计算也不会因为比较次数多而被反复调用。这一点让很多人误以为 key 会被调用很多次从而去手动缓存其实是多余的。2.2 手写快排时那两个必踩的坑就算平时用sorted快排还是得会写面试绕不开。但 Python 版快排有两个坑几乎所有第一次写的人都会撞上。第一个坑是递归深度和切片开销。教科书式写法left [x for x in arr if x pivot]看着优雅实际每次递归都新建两个列表内存分配和垃圾回收的成本会吃掉算法优势。对 10 万个随机数这种写法比sorted慢 5 倍以上。改良方式是原地分区Lomuto 或 Hoare 分区只交换不新建。第二个坑是重复元素导致的退化。如果数组里大量元素相等标准的两路分区会把它们全部分到一边递归树退化成链复杂度掉到 O(n²)。解决办法是三路快排把数组分成小于、等于、大于三段等于段不再参与递归。代码骨架如下def quick_sort_3way(arr, lo, hi): if lo hi: return pivot arr[lo] lt, gt, i lo, hi, lo 1 while i gt: if arr[i] pivot: arr[lt], arr[i] arr[i], arr[lt] lt 1 i 1 elif arr[i] pivot: arr[gt], arr[i] arr[i], arr[gt] gt - 1 else: i 1 quick_sort_3way(arr, lo, lt - 1) quick_sort_3way(arr, gt 1, hi)注意gt那一支在交换后i不前进因为换过来的元素还没被检查过。这个细节漏掉就是死循环或者结果错乱我第一次写的时候在这一行上卡了半小时。2.3 二分的四种边界变体和 bisect 的正确用法二分查找看着简单实际是算法题里翻车率最高的。核心原因是找目标值只是最基础的一种真正有用的是四种边界变体找第一个等于目标的位置、找最后一个等于目标的位置、找第一个大于等于目标的位置、找第一个大于目标的位置。Python 的bisect模块直接给了后两种bisect_left返回第一个 x的插入点bisect_right返回第一个 x的插入点。前两种可以由此推出第一个等于 x 的位置i bisect_left(a, x)检查i len(a) and a[i] x最后一个等于 x 的位置j bisect_right(a, x) - 1检查j 0 and a[j] x元素 x 的出现次数bisect_right(a, x) - bisect_left(a, x)手写二分最容易出的错是循环条件和 mid 取法的配套。while left right配mid (left right) // 2更新时必须是right mid和left mid 1如果写成left mid就会死循环。我的经验是只要区间定义为左闭右开就统一用left right加mid (left right) // 2右边界更新写right mid这套组合几乎不会错。还有一种进阶用法叫二分答案当问题的解具有单调性判定某个值可行则更大或更小的值也可行时可以对答案域做二分。典型场景是最小化最大值、最大化最小值这类问题。这种题的关键不是二分本身而是把判定函数写对——判定函数写错二分再标准也是错的。3. 线性结构deque、heapq、并查集、LRU 的落地写法3.1 list 当队列用是个高频事故新手写 BFS十有八九写成queue.pop(0)。这行代码是 O(n) 的因为 Python 的 list 是连续内存的动态数组删掉头部元素要把后面所有元素整体前移。在 10 万节点的图上这个操作能把 BFS 从秒级拖到分钟级。正确做法是collections.deque两端插入删除都是 O(1)。它的代价是不支持切片、随机访问是 O(n)、中间插入也慢但对于队列和栈的用途完全够。另一个常见误区是把 deque 当有序容器用以为它有sort方法——没有需要排序就先转成 list。栈的话直接用 list 就行append和pop()都是 O(1)没必要上 deque。我见过有人为了统一风格全用 deque结果代码里到处是popleft和pop混用可读性反而下降。3.2 heapq 的三个隐藏细节heapq是 Python 里最被低估的标准库之一。它实现的是最小堆所有操作基于 list 原地进行heappush和heappop都是 O(log n)heapify建堆是 O(n)。三个细节必须知道第一最大值要用负数。Python 没有内置最大堆标准做法是存-x。如果你的元素是元组就在第一位放负的优先级heapq.heappush(h, (-priority, item))。第二tuple 比较会继续比较后续元素。这既是特性也是陷阱。存(priority, item)时如果两个元素优先级相同Python 会去比较item。如果item是自定义对象且没实现__lt__直接抛TypeError。解决办法是加一个自增计数器作为第二元素(priority, count, item)保证比较永远在计数器处终止。import heapq, itertools counter itertools.count() heap [] heapq.heappush(heap, (5, next(counter), {name: task_a})) heapq.heappush(heap, (5, next(counter), {name: task_b})) # 两个优先级相同也不会去比较 dict第三建堆别用循环 push。从已有列表建堆用heapq.heapify(lst)O(n)循环heappush是 O(n log n)。差一个 log 因子在大数据量下很明显。3.3 并查集迭代实现比递归实现靠谱并查集Union-Find解决的是元素分组 快速判断是否同组的问题典型应用是连通性判断、Kruskal 最小生成树、朋友圈合并。核心就两个操作find找根union合并。两个优化路径压缩、按秩或按大小合并。两个都上均摊复杂度接近 O(α(n))α 是反阿克曼函数实际可以当成常数。Python 实现建议用迭代版 find别用递归。递归版在链很长的时候会撞上默认 1000 层的递归限制虽然路径压缩会把链压平但第一次 find 之前链可能已经很长了。class DSU: def __init__(self, n): self.parent list(range(n)) self.size [1] * n self.count n # 连通分量数 def find(self, x): root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! root: # 路径压缩迭代版 self.parent[x], x root, self.parent[x] return root def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb] self.count - 1 return Trueunion返回布尔值表示是否真的合并了这个返回值在 Kruskal 里非常方便合并成功就说明这条边要加入生成树失败说明成环要跳过。3.4 手写 LRUOrderedDict 和双向链表两条路LRU最近最少使用缓存是面试高频题Python 里有两条实现路径。第一条是collections.OrderedDict三行搞定from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap capacity self.data OrderedDict() def get(self, key): if key not in self.data: return -1 self.data.move_to_end(key) return self.data[key] def put(self, key, value): if key in self.data: self.data.move_to_end(key) self.data[key] value if len(self.data) self.cap: self.data.popitem(lastFalse)第二条是哈希表 双向链表面试时如果被要求不许用 OrderedDict就得靠这个。核心是虚拟头尾节点避免边界判断。手写版本的价值在于理解为什么是 O(1)——哈希定位节点链表调整顺序两个操作都是常数时间。工程上如果真要做缓存直接用functools.lru_cache或者更完整的第三方缓存库别自己造。自己写的版本通常缺并发保护、缺过期策略、缺内存回收。我见过有人手写 LRU 结果在多线程下把链表指针改乱了排查了很久。4. 递归、回溯与 DP从能跑通到不超时的距离4.1 递归深度这道坎比想象中低Python 默认递归限制是 1000 层sys.setrecursionlimit()可以调高但调高不等于安全。因为每层递归在 C 栈上也有开销调太高比如 10 万可能导致解释器直接崩溃而不是抛RecursionError这个后果比报错严重得多。我的经验是递归深度超过 5000 就该考虑改迭代了。改法有三种显式维护栈最适合 DFS、BFS 替代如果只关心可达性、状态转移改循环DP 场景。显式栈的写法是把递归函数里的参数打包成元组压栈本质上是手动模拟调用栈。尾递归在 Python 里没有任何优化写return f(x-1)照样占一层栈。这一点和其他语言差别很大别指望靠它省空间。另外有个高频坑是可变默认参数def dfs(node, path[]): # 错误 path.append(node) ... def dfs(node, pathNone): # 正确 path [] if path is None else path path.append(node)默认参数在函数定义时求值一次所有调用共享同一个 list第二个测试用例就直接全错了。这个坑排错时特别隐蔽因为单次运行看起来完全正常。4.2 回溯剪枝放在哪一行决定了快十倍还是慢十倍回溯的通用模板是选择 - 递归 - 撤销选择难点不在模板在剪枝。剪枝位置有三种效果差异巨大第一种是排序后跳过重复处理组合中有重复元素但不能重复选的问题if i start and nums[i] nums[i-1]: continue。这里i start不能少否则第一个元素就被跳过了。第二种是提前终止当当前和已经超过目标、或者剩余元素全加都不够时直接 return。前提是数组已排序所以排序往往不只是为了去重也是为了剪枝。第三种是可行性预判在进入递归前检查剩余资源比如背包问题里检查容量是否还够。这种剪枝写起来最麻烦但收益最大。我做过一个对比解数独的朴素回溯和加了候选数最少优先的版本在中等难度题上差距接近 20 倍。剪枝的收益不是线性的它砍掉的是整棵子树。状态恢复也要注意。用list.append和list.pop配对是最安全的别用path path [x]这种写法虽然也能得到正确结果但每层都复制一次列表空间和时间都翻倍。4.3 DP 的状态设计比递推式难十倍动态规划的关键从来不是写递推式是定义状态。状态定义对了递推式自然出来定义错了怎么推都漏情况。我一般按三步走先写出暴力递归版本保证正确再看递归函数有哪些参数在变化这些就是状态维度最后决定用自顶向下的lru_cache还是自底向上的循环。functools.lru_cache是个好东西几行代码就能把指数级递归变成多项式级。但它有三个限制参数必须可哈希list 不行得转 tuple缓存没有自动清理长生命周期函数会吃掉内存递归深度限制依然存在。所以在生产代码里我倾向手写 DP 表用数组存状态可控性强得多。二维 DP 转一维是个必备技能尤其背包类问题。0-1 背包的一维写法必须逆序遍历容量完全背包必须正序遍历这个方向的差异来源于同一物品能否重复使用。我见过太多人把方向写反结果要么答案偏小要么偏大还得靠打印中间表才能发现。记忆口诀是逆序保旧值正序用新值。5. 图与树BFS、拓扑排序、最短路的三套写法5.1 邻接表的三种存法和选择依据建图方式直接影响后续代码的可读性和性能。三种常见存法存法结构适用场景注意点列表套列表g [[] for _ in range(n)]节点编号连续、稠密度中等节点数大但边少时浪费内存字典套列表g defaultdict(list)节点编号离散、字符串节点遍历时要.items()边列表edges [(u, v, w)]Kruskal、Bellman-Ford需要邻接表时再转换选哪种我的判断标准是节点编号是否在 0 到 n-1 范围内。是就用列表套列表访问速度最快不是就用defaultdict(list)省去编号映射的麻烦。邻接矩阵只在稠密图上用比如 Floyd 求全源最短路。n 超过 2000 时矩阵内存就到 GB 级了得换思路。5.2 BFS 的 visited 标记时机是最大的坑BFS 里 visited 的标记时机直接决定代码是线性复杂度还是指数复杂度。正确做法是入队时就标记不是出队时。from collections import deque def bfs(graph, start, target): visited {start} q deque([(start, 0)]) while q: node, dist q.popleft() if node target: return dist for nxt in graph[node]: if nxt not in visited: # 入队前判断 visited.add(nxt) # 入队前标记 q.append((nxt, dist 1)) return -1如果写成出队时才标记同一个节点会被多个前驱重复入队队列规模可能膨胀到边的数量级。在稠密图上这就是灾难。这个问题我调试过两次每次都是通过打印队列长度才发现的——队列长度异常增长八成就是标记时机错了。5.3 Dijkstra 的堆优化和两个必备补丁Dijkstra 的朴素版是 O(n²)堆优化版是 O((nm) log n)。Python 实现堆优化版有两个补丁不能省第一个补丁是跳过过期条目。堆里可能存着同一个节点的多个距离值弹出时检查if d dist[u]: continue否则会用旧距离去松弛邻居算出来的结果虽然是更长的路径但不影响正确性因为最终会被更小的覆盖只是浪费计算。第二个补丁是提前终止。如果只关心起点到某个终点的最短距离在终点首次弹出时就可以返回不需要跑完全图。这在图很大而终点很近的时候收益巨大。Dijkstra 有个硬约束不能处理负权边。有负权边必须换 Bellman-Ford 或 SPFA。判断依据很简单如果有边的权重为负先用 Bellman-Ford 检测负环没负环再用 SPFA 求最短路。5.4 拓扑排序Kahn 算法和 DFS 后序的取舍两种写法都能给出拓扑序但用途不同。Kahn 算法基于入度把所有入度为 0 的节点入队弹出时把它指向的节点入度减一减到 0 就入队。它的额外好处是能直接判断有没有环——如果最终输出的节点数少于总数说明剩下的节点互相依赖成环了。DFS 后序法是遍历完一个节点的所有后继后把它加入结果最后整体反转。代码更短但环检测要做额外的三色标记未访问/访问中/已完成遇到访问中的节点就说明有环。我一般优先用 Kahn理由是它天然给出同时可执行的批次——把每轮队列里的元素当成一批就能得到分层拓扑序。这个性质在任务调度场景里直接能用上比如构建依赖图里哪些模块可以并行编译。6. 字符串与窗口类算法Python 语境下的特殊打法6.1 KMP 的 next 数组到底在算什么KMP 是字符串匹配的经典算法核心是next数组也叫前缀函数、失配函数。它记录的是模式串的每个前缀最长的既是前缀又是后缀的子串长度。听起来绕作用是匹配失败时模式串不用从头开始直接根据 next 数组跳到一个已知的前缀位置继续。Python 里日常做子串查找直接用in或者str.find就行底层是优化过的算法手写 KMP 在绝大多数场景都更慢。KMP 的价值在于算法思维以及在需要求字符串周期、判断由重复子串构成这类问题上——比如判断s是否能由某个子串重复多次构成解法就是看n - next[n-1]是否能整除n。6.2 滑动窗口的模板要配何时收缩的判断滑动窗口解决的是连续子数组/子串满足某条件的问题模板固定def sliding_window(s): left 0 counter {} best 0 for right in range(len(s)): counter[s[right]] counter.get(s[right], 0) 1 while 条件不满足: counter[s[left]] - 1 if counter[s[left]] 0: del counter[s[left]] left 1 best max(best, right - left 1) return best关键在两个地方while里的收缩条件怎么写以及结果在收缩前更新还是收缩后更新。求最长是在收缩后更新求最小长度是在收缩过程中更新。这个差别我一开始老是搞混后来统一记成最长看窗口外面最短看窗口里面。还有一个非模板的东西字符串里涉及字符计数时Counter比手写 dict 方便但每次比较Counter相等是 O(k)k 是字符种类数。字符集固定比如只有小写字母时用一个长度为 26 的 list 计数会快不少。6.3 字符串拼接的性能雷区Python 的字符串不可变s c在循环里理论上每次都新建对象是 O(n²)。虽然 CPython 对有引用计数优化在s只被引用一次时能原地扩展但这个优化属于实现细节不可依赖。稳妥做法是.join(parts)或者用io.StringIO。另一个常被忽视的点字符串的s[i]返回的是长度为 1 的新字符串不是字符类型。所以需要原地修改字符的场景比如双指针交换必须先lst list(s)转成列表改完再.join(lst)。直接对字符串做下标赋值会抛TypeError。涉及正则的场景如果同一模式要匹配多次先re.compile缓存别在循环里反复编译。这个差异在百万级匹配下能到 30% 以上。7. 从能跑到跑得快算法代码的性能验证与工程化7.1 用数据说话timeit 和 cProfile 的分工写完算法不看性能等于没写完。我习惯用两个工具timeit测单段代码的重复执行耗时cProfile定位整个程序的耗时分布。timeit的正确用法是给stmt和setup让它内部做多次重复取最小值。手动写time.time()前后相减是最粗糙的做法受系统负载和缓存影响极大测出来的数字基本不能比。cProfile输出的是函数级调用统计按cumtime累计时间排序找热点。我发现过好几次以为慢在算法上实际慢在日志打印和数据转换的情况没有 profile 根本看不出来。一个真实例子一个图遍历程序算法部分只占 15% 时间剩下 85% 花在 JSON 序列化上优化算法毫无意义。7.2 那些让算法白写的语言级细节有几个 Python 层面的细节能让同一份算法代码差出几倍性能把常用的全局函数绑定到局部变量。循环里反复访问len、append、heapq.heappush这类全局名字每次都要做字典查找。在函数开头写成_append lst.append、_heappush heapq.heappush在热循环里能省下可观的开销。用列表推导代替 for 加 append。列表推导在 C 层执行比显式循环快 30% 到 50%。用sum、any、all代替手写累加。内置函数走 C 循环快得多。避免在循环里做重复计算。for i in range(len(arr))里的len(arr)每轮都要求值改成n len(arr)再for i in range(n)。这些优化单个看起来都是小打小闹叠加起来在百万级数据上能有两三倍的差距。当然前提是算法复杂度已经对了用这些技巧去优化一个 O(n²) 的算法是本末倒置。7.3 把算法封装成可测试的模块面试写完就交生产代码不行。我的习惯是每个算法实现配一组边界用例空输入、单元素、全部相同、已排序、逆序、含负数或特殊值。这些用例不是为了凑覆盖率是因为它们对应着真实会踩的坑。举个我自己的教训写过一版二分查找逻辑完全正确但没处理空列表bisect_left([], x)返回 0我的代码直接arr[0]抛了IndexError。这个 bug 在上线两周后才因为某个数据源为空而暴露。封装时还有一个建议把算法的输入校验和核心逻辑分开。校验层负责类型检查、边界处理、异常抛出核心逻辑保持纯粹只处理已经合法的输入。这样核心逻辑好测、好复用也不会被各种防御性代码搞成一锅粥。还有一点如果算法涉及浮点数比较一律用math.isclose别写。round(2.675, 2)返回2.67不是2.68因为 2.675 在二进制里存不下精确值。这种问题在几何计算和数值算法里出现频率极高。8. 几个让我改了代码习惯的具体现场说几个真实的场景都是我在项目里撞上的比抽象讲道理有用。第一个是 BFS 的内存爆炸。做一个层级依赖分析图有几十万节点跑着跑着内存涨到几个 G。排查下来是 visited 用 list 存然后in判断查询是 O(n)总复杂度变成 O(n²)加上重复入队导致的队列膨胀内存直接失控。改成 set 加正确的入队前标记内存降到几百兆时间从分钟级到秒级。第二个是排序键不一致导致的崩溃。线上环境sorted抛TypeError: not supported between instances of NoneType and int原因是某条数据里排序字段是 null。修复方案是在 key 函数里做默认值处理并且明确业务上 null 应该排在最前还是最后。这类问题提醒我算法代码里的理想输入假设在真实数据面前经常不成立。第三个是 DP 缓存没清理。一个用lru_cache写的路径计算方法跑批处理任务时内存持续增长跑了几个小时之后被系统杀掉。原因是缓存 key 里带了整个请求上下文每个请求都产生新条目且永不过期。改成手动管理缓存表按批次清理问题解决。lru_cache适合函数式、参数空间小的场景不适合参数空间巨大且持续变化的场景。最后再分享一个我自己的判断标准如果一个算法的实现超过 60 行还没写完八成是状态设计或者数据结构选错了回头重想比硬写下去快。我见过太多人包括我自己在错误的方向上硬啃最后写出来的代码又长又慢还不容易发现哪里错了。真正干净的实现往往短得让你怀疑是不是漏了什么。