Python经典算法清单：按使用频率与出错代价精讲核心算法

1. 我重新梳理这套Python算法清单的缘由

每隔一段时间，总会有人在群里问一句：python经典算法大全到底该从哪儿看起，python算法有哪些是真正需要花时间掌握的。这个问题我回答过不下十遍，但每次回答都不太一样，因为提问的人背景差别太大。有的是刚学完语法想做点练习的，有的是工作两年突然要准备技术考察的，还有的是写业务代码写久了，想回头把基础重新打一遍。所以这次索性把我会反复翻看的那部分算法整理成一份清单，把每个模块为什么这么选、代码怎么写、哪些地方最容易出错都写清楚。

这份内容适合谁？如果你是刚接触 Python、能写函数但一遇到复杂度分析就发懵的新人，可以从第 2、3 节顺着读；如果你已经有项目经验，只想找回手感、顺手补一下动态规划和图论，直接跳到第 4、5 节也没问题。我不会把几十种算法全部罗列一遍，那种清单在搜索结果的首页能找到一大堆，但大多只有名字和一句解释，看完还是不知道该怎么用。我关注的是那些在真实场景里被反复调用、被反复写错、被反复讨论的算法，以及围绕它们的一整套工程习惯。

先交代一个前提：算法清单不应该按“考试大纲”来组织，而应该按“使用频率 + 出错代价”来组织。一个排序写错，可能只是结果顺序不对；一个二分边界写错，可能就是线上数据查不到；一个并查集漏了路径压缩，可能就让程序从毫秒级变成分钟级。这个思路决定了下面所有内容的排列顺序和取舍方式。

2. 排序与查找：最基础，也是最容易出问题的地方

2.1 快速排序、归并与堆排序之间的选择

排序是所有人学算法的第一站，但真正到了写代码的时候，绝大多数情况直接调用sorted()就够了。Python 内置的 Timsort 是归并和插入排序的混合实现，平均和最坏都是 O(n log n)，而且对部分有序的数据有额外优化，手写基本不可能比它快。所以我一般只在两种情况下手写排序：一是需要理解分治思想，二是需要做“部分排序”或者“只取前 K 个”这类内置函数不方便处理的场景。

快速排序值得手写的核心原因不是它快，而是它把“分治 + 原地交换”这套模式展示得最干净。我常用的版本做了两件事：三数取中选基准，以及小区间切换插入排序。前者用来规避已经有序的输入导致的 O(n²) 退化，后者是因为递归到 16 个元素以下时，递归开销已经超过比较开销了。

def quick_sort(arr, lo=0, hi=None): if hi is None: hi = len(arr) - 1 while lo < hi: if hi - lo < 16: insertion_sort(arr, lo, hi) return mid = lo + (hi - lo) // 2 # 三数取中，把中位数换到 lo 位置 if arr[mid] < arr[lo]: arr[lo], arr[mid] = arr[mid], arr[lo] if arr[hi] < arr[lo]: arr[lo], arr[hi] = arr[hi], arr[lo] if arr[hi] < arr[mid]: arr[mid], arr[hi] = arr[hi], arr[mid] arr[lo], arr[mid] = arr[mid], arr[lo] pivot = arr[lo] i, j = lo, hi while i < j: while i < j and arr[j] >= pivot: j -= 1 arr[i] = arr[j] while i < j and arr[i] <= pivot: i += 1 arr[j] = arr[i] arr[i] = pivot # 先递归较短的一侧，控制栈深度 if i - lo < hi - i: quick_sort(arr, lo, i - 1) lo = i + 1 else: quick_sort(arr, i + 1, hi) hi = i - 1 return arr

这段代码有两个细节值得单独拿出来说。第一个是i, j双指针加“挖坑填数”的写法，比左右交换的写法少一半赋值操作，实测在几十万级别的列表上差距能到 15% 左右。第二个是“先递归较短的一侧”这个尾递归优化，它把最坏情况下的递归栈深度从 O(n) 压到 O(log n)，避免数据量一大就触发递归深度限制。

归并排序的适用场景和快排不太一样。快排是原地排序，空间 O(log n)；归并需要额外 O(n) 空间，但它是稳定排序，而且天然适合处理外部排序和链表排序。我处理链表排序时基本只用归并，因为链表没法随机访问，快排的 partition 在链表上非常别扭。堆排序的优势在于最坏情况也是 O(n log n) 且空间 O(1)，但它不稳定、缓存不友好，实际项目里我用它的次数屈指可数，更多是拿堆这个结构去做优先队列，而不是拿堆排序去排数组。

下面这张表是我自己整理的选择依据，遇到具体问题时可以直接对照：

注意：手写快排时不要用arr[0]当基准，也不要对已经有序的数据做测试就下结论。真实数据里“部分有序”非常常见，比如按时间戳追加的日志，这时候固定基准会直接退化。

2.2 二分查找：边界写错一次就够记一辈子

二分查找的代码只有十来行，但它是公认最容易写错的算法之一。根因不在算法本身，而在于“区间定义”这件事没有被统一。我现在的习惯是全程只用左闭右开区间[lo, hi)，所有变体都在这套约定下推，不再混用闭区间写法。

def lower_bound(arr, target): """返回第一个 >= target 的下标，找不到返回 len(arr)""" lo, hi = 0, len(arr) while lo < hi: mid = lo + (hi - lo) // 2 if arr[mid] < target: lo = mid + 1 else: hi = mid return lo

这个模板能覆盖绝大部分需求：要判断存在性，就看lo < len(arr) and arr[lo] == target；要找最后一个小于等于 target 的位置，就换成upper_bound再减一；要在旋转数组里查找，只改判断条件不改框架。统一模板的价值在于，你不需要每次重新推导边界，只要记住“循环结束时 lo 是答案”这一条。

mid = lo + (hi - lo) // 2这种写法不是为了好看。在支持 int 溢出的语言里它能防止溢出，在 Python 里虽然没有溢出问题，但保持这个习惯可以让你在跨语言写代码时不用重新想一遍。

有一个坑我踩过：对浮点数做二分时用while lo < hi会陷入死循环，因为两个浮点数之间永远存在更近的值。这种情况要么改成固定迭代次数（比如 100 次），要么给区间加一个精度阈值，while hi - lo > 1e-7。我一般用固定次数，因为精度阈值在不同量级的数据上不好统一。

3. 数据结构类算法：栈、队列、哈希与并查集

3.1 该用内置结构还是自己手写

这个问题的答案很明确：业务代码里全部用内置结构。list当栈用，collections.deque当队列用，dict当哈希表用，heapq当优先队列用。Python 的内置实现是 C 层优化过的，手写一遍性能只会更差。

但“用内置”不等于“不用懂”。栈和队列的价值在于它们约束了访问顺序，这个约束本身就是算法设计的一部分。比如用栈做括号匹配、用单调栈求下一个更大元素、用 deque 做滑动窗口最大值，这些都是把数据结构当成“状态容器”来用，而不是简单地存数据。单调栈这个模式特别值得单独练，它的核心是“维护一个单调递增或递减的栈，入栈前弹掉破坏单调性的元素”，一旦理解了这个动作，接雨水、柱状图最大矩形、滑动窗口最大值这一串题目就是同一套逻辑换个外套。

哈希表这块，我要提醒的是“哈希冲突”和“可哈希性”两个概念。Python 的dict用开放寻址法处理冲突，平均 O(1)，但如果你自定义了__eq__却没定义__hash__，这个类就变成不可哈希的，塞不进set和dict。反过来，如果两个对象相等但哈希值不同，字典查找就会失效。这是一个很隐蔽的 bug，表现出来是“明明放进去了却查不到”。

3.2 并查集：路径压缩不能省

并查集是那种“代码极短、作用极大、细节极易漏”的结构，典型用于连通性判断、朋友圈合并、岛屿数量统计这类问题。

class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * 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, x, y): rx, ry = self.find(x), self.find(y) if rx == ry: return False # 按秩合并，把矮树挂到高树下面 if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx self.parent[ry] = rx if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 self.count -= 1 return True

三个细节：第一，find用迭代不用递归，因为路径压缩后的树虽然矮，但极端情况下仍可能很深，递归有栈溢出风险；第二，路径压缩和按秩合并一起用，复杂度才接近常数，只用其中一个会退化成 O(log n)；第三，用count维护连通分量个数，比每次遍历统计快得多，这是图上判环的关键。

我见过一个真实案例：某项目用并查集做大批量数据的分组，只做了路径压缩没做按秩合并，单次操作平均下来还是很快，但在“先大量 union 再集中 find”的模式下，性能比两者都用慢了将近 3 倍。这不是理论问题，是实测出来的。

4. 动态规划与贪心：思路永远比代码重要

4.1 动态规划的四步定式

动态规划是很多人卡住的地方，卡点通常不是写不出代码，而是不知道状态该怎么定义。我现在的做法是固定走四步：定义状态、写转移方程、确定初始值和边界、确定遍历顺序。这四步里，第一步和第四步最容易错，代码反而是最简单的。

以 0-1 背包为例。状态定义成dp[i][j]表示“前 i 个物品、容量 j 时的最大价值”，转移方程是“不选第 i 个”和“选第 i 个”取较大值。到这里还没完，关键在遍历顺序：01 背包用一维数组优化时，容量必须从大到小遍历，因为每个物品只能用一次；完全背包则从小到大，因为物品可以重复用。这个顺序差异不是记忆题，而是由“当前状态依赖的是本层还是上一层”决定的。

def knapsack_01(weights, values, cap): dp = [0] * (cap + 1) for i in range(len(weights)): # 倒序遍历，保证每件物品只被选一次 for j in range(cap, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[cap]

另一个高频模式是最长递增子序列。O(n²) 的写法是dp[i]表示以 i 结尾的最长长度，状态转移要遍历前面所有元素；O(n log n) 的写法维护一个“最小结尾数组”，用二分插入。后者不好想，但它其实是“贪心 + 二分”的组合，理解了“让每个长度的结尾尽可能小”这个贪心策略，代码就只是辅助。

我在实际使用中发现，动态规划真正难的地方在于“能不能把问题拆成重叠子问题”。有些题看起来像 DP，其实是贪心；有些看起来像贪心，其实必须 DP。判断标准是：局部最优能不能推出全局最优。能，就是贪心；不能，才需要 DP 枚举所有状态。

4.2 贪心的适用边界与验证方法

贪心的坑在于“看起来对”但实际不成立。我验证一个贪心策略是否正确的土办法是：构造三个反例。第一个是“相邻两项交换后结果变差”的边界，第二个是“局部最优但全局不是最优”的构造，第三个是“相等值导致的并列选择”。三个都能顶住，才敢用。

典型的贪心场景包括：区间调度（按结束时间排序）、分发饼干（双指针匹配）、跳跃游戏（维护最远可达位置）。这些问题的共性是存在一个明确的“排序依据”，排完序之后每一步的最优选择都是确定的。如果没有明确的排序依据，或者排序依据需要反复调整，那多半不是贪心。

提示：写完贪心不要急着提交，先用小规模数据暴力枚举所有方案，和贪心结果对比。这一步花不了五分钟，但能省掉一次返工。

5. 图论与字符串：工程里真正会碰到的部分

5.1 图遍历与最短路的选择

图的表示我一般只用两种：邻接表用dict[list]存，适合稀疏图；邻接矩阵用二维列表存，适合稠密图或者需要 O(1) 判断两点是否相邻的场景。绝大多数业务问题是稀疏图，所以邻接表用得最多。

BFS 和 DFS 的选择取决于你要什么。求最短步数用 BFS，因为它是按层扩展的，第一次访问到目标时路径一定最短；求所有路径、做连通性判断、做拓扑排序用 DFS，因为它的递归结构天然适合回溯。这里有个细节：BFS 的 visited 标记必须在入队时就打上，不能等出队才打，否则同一个节点可能被重复入队，队列会急剧膨胀。这个错误在网格类问题上特别常见。

Dijkstra 是带权最短路的默认选择，用heapq实现优先队列，复杂度 O((V+E) log V)。它的前提是边权非负，一旦出现负权就必须换 Bellman-Ford 或 SPFA。这一点在实际项目里要特别注意，因为“负数权重”往往不会写在需求里，而是从数据里冒出来的。

import heapq def dijkstra(graph, start): dist = {node: float('inf') for node in graph} dist[start] = 0 heap = [(0, start)] while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue # 过期数据，直接跳过 for v, w in graph[u]: nd = d + w if nd < dist[v]: dist[v] = nd heapq.heappush(heap, (nd, v)) return dist

if d > dist[u]: continue这一行是懒删除的关键。Python 的heapq不支持修改堆中元素的优先级，所以每次更新距离就重新 push 一份，堆里会有历史数据。不做这个判断，算法仍然正确，但会多做很多无用功。

5.2 字符串匹配：什么时候该手写 KMP

Python 的str.find和in操作底层是高效的字符串匹配实现，日常开发直接用它就行。手写 KMP 的意义在于理解“失配时利用已有信息”这个思想，以及处理一些内置函数覆盖不到的需求，比如“求所有匹配位置”、“求最小循环节”、“求字符串的 border 结构”。

KMP 的核心是next数组（也叫失配数组），它记录的是“到当前位置为止，前缀和后缀相等的最大长度”。构造next的过程本身就是一次自我匹配，这一步是整段代码里最难理解的部分。

def build_next(p): nxt = [0] * len(p) k = 0 for i in range(1, len(p)): while k > 0 and p[i] != p[k]: k = nxt[k - 1] if p[i] == p[k]: k += 1 nxt[i] = k return nxt def kmp_search(s, p): if not p: return 0 nxt = build_next(p) k = 0 for i, ch in enumerate(s): while k > 0 and ch != p[k]: k = nxt[k - 1] if ch == p[k]: k += 1 if k == len(p): return i - len(p) + 1 return -1

k = nxt[k - 1]这个回退动作是 KMP 的灵魂。它的含义是“当前这个前缀已经对不上了，退而求其次，看看更短的前缀还能不能对上”。理解了这句话，next数组的构造就不需要死记了。

6. 常见问题与排查技巧实录

6.1 复杂度误判与性能陷阱

最常见的误判是把“嵌套循环”直接等同于 O(n²)。实际上要看内层循环的执行次数总和，比如双指针、单调栈这些写法，外层是循环、内层是 while，但内层指针不会回退，总执行次数是 O(n)。判断方法是看“指针是否有单调性”，单调就是均摊分析，不单调就得老实算。

第二个高频陷阱是隐性复杂度。list.pop(0)是 O(n)，在循环里做就成了 O(n²)；x in list是 O(n)，换成set就是 O(1)；字符串拼接s += ch在循环里是 O(n²)，换成''.join(parts)是 O(n)。这些问题不会报错，只会让程序在数据量上来之后突然变慢，排查起来非常费劲。

第三个是递归深度。Python 默认递归深度限制是 1000 左右，DFS 遍历深度较大的树或图时很容易触发RecursionError。解决方案要么改成显式栈的迭代写法，要么用sys.setrecursionlimit调大限制，但后者要配合更大的栈空间才有意义，否则可能直接段错误。

6.2 我的几个实操心得

第一个心得：每写完一个算法，用三组数据验证——空输入、单元素、含重复元素。这三组能挡住 80% 的边界错误。空输入考验的是提前返回，单元素考验的是循环条件，重复元素考验的是比较符号。

第二个心得：不要在没有性能需求的时候做“提前优化”。我见过有人把所有查找都改成手写二分，结果代码可读性大幅下降，而实际数据量只有几百条，in操作完全够用。算法的选择要看数据规模，n 小于 1000 的时候，常数因子比复杂度更重要。

第三个心得：复杂度分析最好写成注释。写# O(n log n)，排序 + 单次遍历这种，比只写# 排序有用得多。过几个月回头看，你能立刻想起当时的取舍理由。

第四个心得：动态规划的调试不要靠打印整个 dp 表，先手动推演前三个状态，确认初始值对了，再看转移方程。绝大多数 DP 的 bug 都在初始值，而不是转移方程。

第五个心得：图论题目先把图画出来，标上节点和边权，再动笔写代码。直接在脑子里推演图的遍历顺序，出错概率非常高，而且错了很难定位。

7. 一个补充：算法清单的练习节奏

最后分享一点关于练习节奏的体会。我自己的习惯是每个模块只精做五到八道题，做完之后隔一周再重写一遍，不看之前代码。第二遍能独立写出来的，才算真的会了；写不出来的，说明当时是靠记忆而不是靠理解。

排序和二分属于“必须肌肉记忆”的部分，快排模板、二分模板、并查集模板这几个要能做到提笔就写。动态规划和图论属于“必须理解思路”的部分，代码可以查，但状态定义和算法选择必须自己想清楚。字符串算法属于“知道有这个东西就行”的部分，真要用的时候再翻文档，没必要全部背下来。

这套清单我前后改过三四版，删掉了很多“考试会考但实际用不上”的内容，比如 AVL 树的完整旋转实现、红黑树的插入删除，这些了解概念即可。留下来的都是会在实际代码里反复出现的，或者是在技术讨论中必须能讲清楚的。要是你正在按某个“大全”清单从头刷，不妨先停下来看看自己真正需要的是哪一部分，把有限的时间投在出错代价最高的地方。