C++算法从入门到工程实践：排序、查找、图论与动态规划选型指南

1. 先把 C++ 算法的地图画出来

C++ 算法这个词，在多数人的语境里其实混着两层含义：一层是数据结构与算法课上那套东西，排序、查找、图论、动态规划；另一层是 C++ 标准库<algorithm>里已经封装好的那批函数，sort、lower_bound、next_permutation之类。这两层不是一回事，但实际写代码时几乎天天要交叉使用，所以一开始就把边界分清楚，后面学起来不会拧巴。

用最朴素的话讲，算法就是把输入变成输出的有限步骤。输入可能是十个整数，也可能是几十万个节点的一张图；输出可能是一个排好序的数组，也可能是一条最短路径。C++ 在这件事上的特殊之处在于，它把运行效率的掌控权交还给了写代码的人——同一道题，你用std::vector和用裸数组，用值传递和用引用传递，跑出来的时间可能差好几倍。这就是为什么很多人明明学了算法思路，一提交还是超时。

这篇东西适合谁看：正在被 C++ 八股文和笔试题折磨的在校生、写了两三年业务代码但没系统梳理过算法的工程师、以及想从 Python 或 Java 转过来写 C++ 的人。我会按“分类讲思路 + 给能直接跑的代码 + 说清楚什么时候不该用”的方式铺开，不搞那种只留个结论的条目式罗列。代码默认用 C++17 编译，因为结构化绑定和std::greater<>的透明比较在刷题里太省事了。

写到这里先给一张全局表，方便你决定先看哪一节。这张表我建议存下来，它不是知识清单，而是选型清单。

1.1 从业务场景倒推算法分类

我不太喜欢按教科书目录去背算法，那种“第一章排序、第二章查找”的顺序容易让人学完就忘。更靠谱的做法是从场景倒推：你手上有个什么任务，任务里最痛的那个点是什么，然后去找对应算法。比如日志分析要对 IP 做 TopK 统计，那核心就是堆或者nth_element，跟排序整个数组没关系；比如做任务调度器要判断依赖有没有环，那核心就是拓扑排序，DFS 三色标记或者 Kahn 入度法都行。

这种倒推法的好处是，你记的不是名字，而是“这一类问题的解法长什么样”。等你遇到新问题，能立刻判断它属于哪一类。我见过不少同学，背得出十种排序的复杂度，但真让他从十亿条日志里找出现次数最多的一百个词，他会下意识想“先排序再取”，然后内存直接爆掉。

顺带说一个热词里常出现的困惑：“算法是什么意思”。很多刚入门的人以为算法就是“最优解”，其实不是。算法首先得是正确的，其次才是高效的。一个跑得飞快但结果错的程序，工程价值是负的。所以下面每一节我都会先讲清楚正确性来自哪里，再谈怎么优化常数。

1.2 一套务实的优先级排法

如果时间有限，我建议按这个顺序补：数组双指针和二分、哈希表、五种排序中的快排和归并、BFS/DFS、Dijkstra、背包和 LIS。这几样覆盖了日常刷题和面试的八成场景。剩下的 Prim、匈牙利算法、模拟退火、KMP，属于特定题型才用得上，遇到了再学完全来得及。

至于复杂度估算，这是所有优化的地基。粗略记几条就够了：1e8 次简单操作大概一秒（不同机器差异很大，只是个量级感）；递归深度超过 1e5 基本会爆栈；二维 DP 开到 1e4 × 1e4 就已经是 4 亿 int，内存大概 1.6 GB，肯定超限。心里有这几个数字，写代码前就能筛掉一批注定超时的方案。

2. 排序算法：面试和工程都绕不开的一类

排序是算法的起点，也是面试出现频率最高的地方。但要注意，面试官问“手写快排”和工程里“该不该自己写排序”是两个完全不同的问题。工程里 99% 的情况你应该直接调用std::sort，它的内省排序（introsort）实现比你临时写的任何版本都稳。手写排序的意义在于理解分治、理解比较次数、理解稳定性这些概念。

先说一个容易被忽略的点：稳定性。稳定排序意味着相等元素的相对顺序在排序后不变。这个性质在处理“先按时间排，再按优先级排”这种多关键字场景时非常关键。std::sort是不稳定的，std::stable_sort才是稳定的。我曾经用std::sort处理一个带时间戳的订单列表，结果同一秒内的订单顺序被打乱，下游对账直接出错，排查了两个小时才发现是稳定性问题。

2.1 冒泡、选择、插入：慢，但必须理解

冒泡排序的核心是相邻比较交换，每轮把最大值“冒”到末尾。加了提前退出标志后，最好情况能退化到 O(n)，这也是它唯一的亮点。

void bubbleSort(std::vector<int>& a) { int n = static_cast<int>(a.size()); for (int i = 0; i < n - 1; ++i) { bool swapped = false; for (int j = 0; j < n - 1 - i; ++j) { if (a[j] > a[j + 1]) { std::swap(a[j], a[j + 1]); swapped = true; } } if (!swapped) break; // 本轮无交换，已经有序 } }

选择排序每轮从未排序区间里挑最小值放到前面，比较次数固定为 n(n-1)/2，不管数据初始状态如何。它的优点是交换次数最少，只有 n-1 次，所以在“写操作代价极高”的场景（比如某些闪存或外部存储场景）反而有一点价值。

插入排序是这三个里唯一真正能上生产环境的。它的特点是数据越接近有序越快，最好情况 O(n)。很多标准库的排序实现在小数组（通常是长度小于 16）时会退化成插入排序，因为它的常数因子极小，在短区间上比快排还快。

注意：冒泡、选择、插入的平均复杂度都是 O(n²)，n 上到 5000 以上就会明显卡顿。刷题时如果看到 n ≤ 5000 并且允许 O(n²)，那大概率是让你写这三样的变体，比如统计逆序对（用插入排序或归并）。

2.2 归并排序与快速排序：分治的两条路

归并排序是“先分到底，再合并上来”，稳定，复杂度恒为 O(n log n)，代价是需要 O(n) 的额外空间。它的最大价值不只是排序，而是归并过程本身可以用来统计逆序对。

void mergeSort(std::vector<int>& a, int l, int r, std::vector<int>& tmp) { if (l >= r) return; int m = l + (r - l) / 2; mergeSort(a, l, m, tmp); mergeSort(a, m + 1, r, tmp); int i = l, j = m + 1, k = l; while (i <= m && j <= r) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; while (i <= m) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (int t = l; t <= r; ++t) a[t] = tmp[t]; }

快速排序是“先分区，再递归”，原地排序，平均 O(n log n)，但最坏会退化到 O(n²)。退化的典型触发条件是“每次都选到极值作为基准”，所以在已排好序的数组上直接用首元素做基准是最糟糕的写法。工程上的解法是随机选基准或者三数取中。

void quickSort(std::vector<int>& a, int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1; int pivot = a[l + (r - l) / 2]; while (i < j) { do ++i; while (a[i] < pivot); do --j; while (a[j] > pivot); if (i < j) std::swap(a[i], a[j]); } quickSort(a, l, j); quickSort(a, j + 1, r); }

这段 Hoare 划分写法的好处是不会出现基准值集中在一侧导致的极端退化，配合中间取基准，实际表现很稳。我实测过在 1e6 随机整数上，它和std::sort差距在 10% 以内；但如果数组里有大量重复值，这段代码会退化成 O(n²)，因为划分后重复值被均匀分到两边。这种时候要用三路划分，把等于基准的元素单独聚成一堆。

2.3 堆排序与优先队列：TopK 的正确打开方式

堆排序的核心是siftDown这个下沉操作。建堆从最后一个非叶节点开始往前，复杂度是 O(n) 而不是 O(n log n)，这一点很多人不知道。排序阶段做 n 次“堆顶与末尾交换 + 下沉”，总计 O(n log n)。

void siftDown(std::vector<int>& a, int n, int i) { while (true) { int l = 2 * i + 1, r = 2 * i + 2, best = i; if (l < n && a[l] > a[best]) best = l; if (r < n && a[r] > a[best]) best = r; if (best == i) break; std::swap(a[i], a[best]); i = best; } } void heapSort(std::vector<int>& a) { int n = static_cast<int>(a.size()); for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i); for (int i = n - 1; i > 0; --i) { std::swap(a[0], a[i]); siftDown(a, i, 0); } }

真正在生产里高频出现的是std::priority_queue。求“最大的一百个数”，不需要把全部数据排序，维护一个大小为 100 的小顶堆即可，每次新元素比堆顶大就替换并下沉，复杂度 O(n log k)，空间 O(k)。数据量上千万的时候，这个方案比全排序快一个数量级，内存占用还小。

2.4 非比较排序的适用边界

计数排序适合值域很小的情况，比如统计年龄分布（0 到 120），复杂度 O(n + k)。基数排序适合定长整数或字符串，从低位到高位逐位分桶。桶排序适合数据均匀分布的场景。这三种的共同点是都突破了 O(n log n) 的比较排序下界，代价是对数据分布有假设。

使用前必须问自己两个问题：值域到底多大？数据分布是否可假设？我见过有人对一个取值范围到 2^31 的数据做计数排序，申请了 20 多亿的数组，程序直接被系统杀掉。值域超过 1e7 就基本别考虑计数排序了。

2.5 排序算法横向对比与选型

选型的口诀很简单：默认std::sort；要稳定用std::stable_sort；只求第 k 个用std::nth_element；只求前 k 个用优先队列；值域小考虑计数排序。这四条能覆盖你写业务代码时 95% 的排序需求。

3. 查找与字符串匹配算法

查找这块最容易被低估。很多人觉得二分查找“太简单了”，结果面试手写十个里有六个写出死循环或者边界错误。二分查找的坑全在while (l <= r)还是while (l < r)、mid更新加不加一这四行代码上。

3.1 二分查找：边界比思路重要

二分的核心前提是单调性。数组必须有序，或者判定函数具有单调性（这一步更抽象，叫“二分答案”）。标准写法如下：

// 返回第一个 >= target 的位置，找不到返回 n int lowerBound(const std::vector<int>& a, int target) { int l = 0, r = static_cast<int>(a.size()); // 左闭右开 while (l < r) { int mid = l + (r - l) / 2; // 防溢出 if (a[mid] < target) l = mid + 1; else r = mid; } return l; }

用左闭右开区间[l, r)可以避免一大堆边界讨论，我的建议是永远固定这一种写法，不要换。mid = l + (r - l) / 2这个写法是为了防止l + r溢出，虽然 C++ 里 int 溢出是未定义行为，但用减法写法图个心安，也让代码更容易迁移到其他语言。

工程里其实直接用std::lower_bound和std::upper_bound就够了。要特别注意的是upper_bound返回的是第一个大于目标的位置，两者相减就是目标值的出现次数。这个技巧在统计频次时很好用：

int cnt = std::upper_bound(a.begin(), a.end(), x) - std::lower_bound(a.begin(), a.end(), x);

二分答案是个值得单独拎出来的技巧。当题目问“最小的最大”“最大的最小”时，八成是二分答案加一个 check 函数。比如“把 n 本书分给 k 个人抄，让抄得最多的人耗时最少”，答案的单调性是显然的：给的时间越多越容易满足。这类题的写法是把二分套在答案值域上，check 函数用贪心验证。

3.2 哈希查找与冲突处理

std::unordered_map的平均查找是 O(1)，但它不是银弹。第一，它的常数因子比std::map大不少；第二，哈希函数被恶意构造时会被卡成 O(n)；第三，它在 C++ 标准里不保证迭代顺序稳定。

最大的坑是自定义 key 类型时必须提供哈希函数和相等比较。很多人写了个结构体当 key，编译时报了一堆模板错误，其实只要补两个东西：

struct Point { int x, y; bool operator==(const Point& o) const { return x == o.x && y == o.y; } }; struct PointHash { size_t operator()(const Point& p) const { return std::hash<int>()(p.x) * 1315423911u ^ std::hash<int>()(p.y); } }; std::unordered_map<Point, int, PointHash> mp;

另外提醒一句性能：如果数据规模不大（几千以内），直接用std::map或者排序后二分，实测经常比unordered_map更快，因为它没有分配和哈希开销。这个结论跟直觉相反，但你写个 benchmark 一跑就知道了。

3.3 KMP：next 数组在干什么

KMP 解决的问题是“在主串中找模式串第一次出现的位置”。暴力匹配在失配时会把主串指针回退，KMP 的做法是让主串指针永不回退，靠模式串自己记录“失配时该跳到哪”。

next[i]的含义是：模式串前 i+1 个字符中，最长的相等前后缀长度。失配时跳到next[j-1]，因为那里之前的部分一定是匹配的。

std::vector<int> buildNext(const std::string& p) { std::vector<int> nxt(p.size(), 0); for (int i = 1, j = 0; i < static_cast<int>(p.size()); ++i) { while (j > 0 && p[i] != p[j]) j = nxt[j - 1]; if (p[i] == p[j]) ++j; nxt[i] = j; } return nxt; } int kmp(const std::string& s, const std::string& p) { if (p.empty()) return 0; std::vector<int> nxt = buildNext(p); for (int i = 0, j = 0; i < static_cast<int>(s.size()); ++i) { while (j > 0 && s[i] != p[j]) j = nxt[j - 1]; if (s[i] == p[j]) ++j; if (j == static_cast<int>(p.size())) return i - j + 1; } return -1; }

这两段代码的结构几乎完全一样，理解了一个就理解了两个。我建议自己拿纸画一遍p = "ababaca"的 next 数组，画完就再也忘不掉了。

注意：真实工程里做子串查找，几十 KB 的文本用std::string::find就够；上 GB 的文本检索应该用专门的索引结构，而不是纠结 KMP。KMP 的价值更多在算法思维和面试题（比如“最短回文串拼接”这类题就是 next 数组的变形）。

3.4 剪枝：搜索算法的生命线

剪枝严格说不算独立算法，而是 DFS/BFS 的优化手段。核心思想是：在搜索过程中提前判断某个分支不可能产生最优解，直接砍掉。常见的有最优性剪枝（当前代价已超过已知最优解就返回）、可行性剪枝（剩余量不够满足约束就返回）、搜索顺序剪枝（先搜分支少的变量）。

一道典型的题是“数独求解”。不加剪枝的暴力 DFS 要跑到天荒地老，加上“优先填候选数字最少的空格”这一条顺序剪枝，速度能快几个数量级。记忆化搜索也是一种广义剪枝，把已经算过的状态存下来，本质是用空间换时间。

我这里给个实操建议：写 DFS 时先写出最朴素的版本验证正确性，跑通之后再逐条加剪枝，每加一条都测一下时间变化。一上来就堆五条剪枝，很容易出错而且说不清哪条有用。

4. 图论算法：从最短路到二分图匹配

图论算法的学习曲线比排序陡得多，因为首先要过“图的存储”这一关。存得不对，后面的算法再快也白搭。

4.1 存储方式的选择

三种主流存法：

• 邻接矩阵：vector<vector<int>> g(n, vector<int>(n, INF))，适合点少边多的稠密图，n 一般在 300 以内。优点是查询 O(1)，Floyd 算法必须用它。
• 邻接表：vector<vector<int>> g(n)或带权版本vector<vector<pair<int,int>>>，适合稀疏图，是默认选择。
• 链式前向星：用数组模拟链表（head、to、next、w四个数组），内存紧凑，常数小，竞赛里大量使用，但可读性差。

我个人的判断标准是：n 超过 5000 就一定要用邻接表或前向星，邻接矩阵会爆内存。带权图用pair<int,int>存{邻点, 权重}，配合结构化绑定写起来很清爽。

4.2 最短路：选对算法比优化常数更重要

最短路有三个主要算法，适用的图性质完全不同。

Dijkstra用于非负权图，堆优化后复杂度 O(m log n)。核心是每次从优先队列里取出当前距离最小的点，用它松弛邻居。

const int INF = 0x3f3f3f3f; std::vector<int> dijkstra(int n, int s, const std::vector<std::vector<std::pair<int,int>>>& g) { std::vector<int> dist(n, INF); dist[s] = 0; std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, std::greater<>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 过期条目直接跳过 for (auto [v, w] : g[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }

那段if (d > dist[u]) continue;是懒删除的关键。优先队列不支持修改已有的元素，所以同一个点可能入队多次，比的时候直接跳过旧的即可。少了这一行，复杂度会退化。

Bellman-Ford用于含负权边的图，复杂度 O(nm)。它的额外价值是能判断负环：如果第 n 次松弛还能更新，说明存在负环。SPFA 是它的队列优化版本，平均快很多，但最坏仍是 O(nm)，某些精心构造的数据能把它卡死。

Floyd用于求所有点对的最短路，只有三行：

for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);

三层循环的顺序绝对不能换，k必须在最外层，这是动态规划的阶段维度。我见过有人把k放最里面，结果在小数据上也能过样例，一交就挂。

4.3 最小生成树：Prim 与 Kruskal

最小生成树解决的是“用最小的总代价把所有点连通”。Prim 从任意一个点开始，每次把距离生成树最近的点拉进来，适合稠密图。Kruskal 把边排序后从小到大尝试加入，用并查集判环，适合稀疏图。

Kruskal 的代码结构非常固定，并查集写熟之后五分钟能写完：

struct DSU { std::vector<int> p, sz; explicit DSU(int n) : p(n), sz(n, 1) { std::iota(p.begin(), p.end(), 0); } int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) std::swap(a, b); p[b] = a; sz[a] += sz[b]; return true; } };

路径压缩加按大小合并之后，并查集的单次操作复杂度几乎可以看作常数。这里的find用了递归写法，合并了路径压缩，代码极短。如果点数特别大，递归可能爆栈，可以改成循环版本。

Kruskal 的主流程是：边按权排序，逐条调unite，成功就计数并累加权重，累计到 n-1 条边就停。最后判断边数是否为 n-1，不是就说明图不连通。

4.4 拓扑排序与 BFS/DFS 通用框架

拓扑排序处理的是有向无环图上的依赖顺序问题。Kahn 算法最直观：统计每个点的入度，入度为 0 的入队，出队时把邻居入度减一，减到 0 就入队。最后如果输出的点数小于总点数，说明图里有环。

std::vector<int> topoSort(int n, const std::vector<std::vector<int>>& g) { std::vector<int> indeg(n, 0), order; for (int u = 0; u < n; ++u) for (int v : g[u]) ++indeg[v]; std::queue<int> q; for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); order.push_back(u); for (int v : g[u]) if (--indeg[v] == 0) q.push(v); } return order.size() == static_cast<size_t>(n) ? order : std::vector<int>{}; }

这个模板在工程里对应的场景很多：构建系统解析编译依赖、任务调度器排执行顺序、包管理器解析版本依赖。我之前写过一个配置热更新的小工具，就用它检测用户配置项之间的循环引用，报错信息比系统自带的清晰得多。

BFS 求无权图最短路也是必会的：从起点开始逐层扩展，第一次访问到某个点时的层数就是最短距离。DFS 则用于连通块计数、路径枚举、树上问题。

4.5 匈牙利算法与二分图匹配入门

匈牙利算法解决的是二分图最大匹配：左边一堆点，右边一堆点，中间有若干可行连线，问最多能配成多少对。经典场景是任务分配和排课。

核心思路是不断找增广路。对左边每个点尝试匹配，如果右边的目标点已被占用，就递归地问“那个占用者能不能换一个”，能换就让出来。

bool dfs(int u, const std::vector<std::vector<int>>& g, std::vector<int>& match, std::vector<int>& vis, int tag) { for (int v : g[u]) { if (vis[v] == tag) continue; vis[v] = tag; if (match[v] == -1 || dfs(match[v], g, match, vis, tag)) { match[v] = u; return true; } } return false; }

vis数组用tag标记而不是每次清零，是个小优化技巧，能省掉 O(n) 的清空开销。整体复杂度 O(nm)，点数在 500 以内通常没问题。

5. 动态规划与贪心：最容易被滥用的两类

动态规划的核心不是“写出转移方程”，而是定义状态。状态定义对了，方程自然就出来了；状态定义歪了，怎么推都别扭。

5.1 状态定义的三条经验

第一，状态要能描述“子问题”，也就是“前 i 个元素的最优解是什么”。第二，状态要满足最优子结构，大问题的最优解能从小问题推出来。第三，状态要满足无后效性，当前状态确定后，后面的决策不受之前怎么走到这里的影响。

举个反面例子：求最长递增子序列时，如果定义为dp[i]表示前 i 个元素的最长递增子序列长度，会发现推不动，因为不知道结尾元素是多少。正确做法是定义为“以第 i 个元素结尾的最长长度”，这样才能比较。

5.2 背包问题：一维数组的方向是关键

01 背包的二维版本是dp[i][j]表示前 i 件物品、容量 j 的最大价值。滚动到一维后，容量必须倒序遍历：

// 01 背包：每件物品最多取一次 std::vector<int> dp(W + 1, 0); for (int i = 0; i < n; ++i) for (int j = W; j >= w[i]; --j) dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);

为什么倒序？因为一维数组里dp[j - w[i]]如果被正序遍历先更新了，那它就已经包含“第 i 件物品被选过”的信息，会导致同一件物品被重复选。倒序保证读到的是上一轮的状态。

完全背包（每件可取无限次）则正好相反，容量正序遍历：

for (int i = 0; i < n; ++i) for (int j = w[i]; j <= W; ++j) dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);

这两个方向的差异我建议自己动手打断点看一遍数组变化，比看十篇博客都管用。多重背包、分组背包都是在这个基础上的变形，掌握了基础版本再推很快。

5.3 LIS：O(n²) 到 O(n log n) 的跨越

最长递增子序列的朴素做法是 O(n²)，用二分优化后可以做到 O(n log n)。做法是维护一个数组tails，tails[k]表示长度为 k+1 的递增子序列的末尾最小值。这个定义有点绕，但性质很好：tails本身是严格递增的，所以可以二分。

int lengthOfLIS(const std::vector<int>& a) { std::vector<int> tails; for (int x : a) { auto it = std::lower_bound(tails.begin(), tails.end(), x); if (it == tails.end()) tails.push_back(x); else *it = x; } return static_cast<int>(tails.size()); }

这里用lower_bound求的是严格递增，如果要非严格递增（允许相等），换成upper_bound即可。这是一个非常高频的细节坑。

5.4 贪心：证明比代码重要

贪心的代码往往只有几行，难的是证明它是对的。常见证明手段有交换论证（把任意最优解通过交换变成贪心解而不变差）和归纳法。

经典的“跳跃游戏”就是贪心：在每个位置能跳到的范围内，选一个“下一步能跳最远”的位置作为落点。局部选最远，全局也最优，这个结论可以用反证法证。区间调度问题也是同类：按右端点排序后能选就选，得到的区间数最多。

我踩过的坑是：有些题看起来像贪心，实际上必须用 DP。判断标准是“局部最优能不能保证全局最优”，如果举得出反例，那就老老实实上 DP。比如“硬币找零”，面值是任意给定的时候，贪心就不成立，必须用完全背包。

5.5 模拟退火：非精确算法的定位

模拟退火、粒子群这类启发式算法属于“求近似最优解”的范畴，适合解空间巨大、精确算法算不动的场景，比如函数极值搜索、旅行商问题的近似解。它们的共同点是有随机性，需要调参（初始温度、降温系数、迭代次数），而且结果不稳定。

我的建议是：这类算法先在参数上做粗调（步长、温度范围），再考虑优化收敛速度。而且一定要设一个“保底解”，也就是记录搜索过程中历史最优值，防止最后一步跳到一个差解上。要不要用它们，取决于业务能不能接受“大概对”的结果。

6. 数论、位运算与其他高频小算法

6.1 质数判断的优化写法

判断单个质数的暴力做法是从 2 试到 √n，已经够用。进一步优化可以只试 2、3 和形如 6k±1 的数，因为所有大于 3 的质数都满足这个形式，循环次数能砍掉三分之二。

bool isPrime(long long n) { if (n < 2) return false; if (n % 2 == 0) return n == 2; if (n % 3 == 0) return n == 3; for (long long i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; }

注意i * i <= n这里要用long long，否则 i 接近 5 万时 i*i 虽然不溢出 int，但 n 是 64 位的时候会出问题。这个细节在“判断质数 C++ 优化”这类场景里被反复提及，属于必知项。

如果需要判断 1e7 以内的所有质数，就要用筛法。埃氏筛 O(n log log n) 已经很够用，欧拉线性筛能保证每个合数只被最小质因子筛掉一次，复杂度 O(n)，代码稍长但常数也不大。写筛法时记得用vector<bool>或vector<char>存标记，vector<bool>是位压缩版本，内存能省 8 倍，但有代理对象的坑，取地址会出问题，一般场景直接用没关系。

6.2 gcd、快速幂与模运算

辗转相除法求最大公约数是最古老的算法之一，几行就能写完：

long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); } long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }

lcm要先除后乘，防止中间结果溢出。这个顺序问题在数据接近 int 上限时是致命的。C++17 之后标准库自带了std::gcd和std::lcm，在<numeric>里，直接用即可。

快速幂用来算 a^b mod m，把指数按二进制拆开，复杂度从 O(b) 降到 O(log b)。写的时候要注意底数先取模，以及乘法可能溢出时改用__int128或者龟速乘。

6.3 位运算的几个实用技巧

位运算在状态压缩和底层优化里用得多。几个我常用的：

• x & 1判奇偶，比x % 2快，但负数取模会出问题，位运算不会。
• x & (x - 1)消掉最低位的 1，可以用来统计二进制中 1 的个数，也能判断是不是 2 的幂（结果是 0 就是）。
• x & -x取出最低位的 1，树状数组里天天用。
• x << 1是乘 2，x >> 1是除 2 向下取整（对负数不是除以 2 的语义，要注意）。
• __builtin_popcount(x)直接数 1 的个数，__builtin_clz数前导零，GCC 和 Clang 都支持，遇到不支持的编译器可以用std::bitset或者手写查表。

状态压缩 DP 是位运算的重灾区，用二进制位表示集合的选取状态，dp[mask]里的 mask 从 0 遍历到(1<<n)-1。n 通常在 20 以内，因为状态数是指数级的。

7. 把算法落到 C++ 工程里

7.1 STL algorithm 里已经有的别重造

我见过太多人自己手写快排然后比std::sort慢，原因在于标准库用了内省排序——快排递归到一定深度会切换到堆排序防止退化，小区间会切换到插入排序降低常数。这些工程细节不是随手能写出来的。

常用的几个函数值得记住：

std::unique有个大坑：它只是把重复元素移到末尾并返回新的逻辑结尾，并不会真的删除元素。标准用法是a.erase(std::unique(a.begin(), a.end()), a.end())，而且必须先排序，因为它只处理相邻的重复。

7.2 数据规模决定算法选择

这张表是我做题和写业务时都会对照的速查表，用 1e8 次操作约 1 秒的粗略基准估算：

按这个表估一遍，能提前筛掉大量注定超时的方案，省下的时间够你多做好几道题。

7.3 环境与工具链的准备工作

写 C++ 最劝退的环节往往不是算法本身，而是环境。几个高频问题提前说清楚。

第一，用 VS Code 写 C++ 需要三样东西：编译器（Linux 用 g++，Windows 用 MinGW-w64 或 MSVC）、tasks.json（定义怎么编译）、launch.json（定义怎么调试）。这两份配置文件最容易出错的地方是路径用了相对路径，导致换目录就找不到源文件。我的习惯是统一用${file}和${fileDirname}这些内置变量。

第二，tasks.json里建议加-std=c++17 -Wall -Wextra -O2，-Wall打开警告能帮你提前发现未使用变量、隐式转换这类问题，-O2保证测的是优化后的性能。调试时把-O2换成-g -O0，否则断点和单步会错乱。

第三，安装某些依赖 C/C++ 扩展的程序时，可能遇到提示缺少编译工具链的信息，这本质上是环境里没有可用的 C++ 编译器。正规处理方式是安装官方提供的构建工具链，或者改用已经提供预编译包的安装方式，不要把时间浪费在到处找来历不明的安装包上。

8. 常见问题与排查实录

8.1 编译期问题的排查顺序

编译报错时我的一般排查顺序是：先看第一条错误，不要看后面那一堆（通常是连锁反应）；如果是模板相关的长篇报错，从最后一行的“required from here”往上找；如果是链接错误（undefined reference），检查函数声明和定义的参数列表是否完全一致，尤其是const和引用符号。

一个高频场景是模板声明和定义分离到 .h 和 .cpp 两个文件，然后链接报错。原因是模板实例化发生在使用处，编译器看不到定义就没法生成代码。解法是把定义也放到头文件里，或者显式实例化。

8.2 运行期问题的常见成因

-fsanitize=address是我最推荐的排错工具，编译时加上它，越界访问会在第一次发生时就报出精确的文件行号，比事后加打印快十倍。同样是内存问题，-fsanitize=undefined能抓出整数溢出和有符号移位这类未定义行为。

8.3 几个我踩过的具体坑

第一个坑是整数溢出。写最大子段和的时候用 int 存结果，数组长度 1e5、元素 1e9，总和能到 1e14，直接溢出。这种时候答案会变成一个莫名其妙的小数或者负数。养成习惯：只要涉及求和，先估一下上界，超过 2e9 就用long long。

第二个坑是递归爆栈。默认栈空间在 Windows 上通常只有 1 MB 左右，深搜 1e5 层必崩。解法有两种：把递归改成显式栈的迭代写法，或者在图论题里把递归改成手动维护队列的 BFS。竞赛里常用#pragma comment(linker, "/STACK:...")来扩栈，但工程代码里不推荐这么干。

第三个坑是浮点精度。二分答案时如果写成while (r - l > 1e-6)，循环次数可能因为浮点误差变得不可控。更稳的做法是直接固定循环 100 次二分，精度足够而且次数确定。比较浮点数相等时用fabs(a - b) < eps，别用==。

第四个坑是**unordered_map的遍历顺序**。标准不保证任何顺序，我当时写了个依赖遍历顺序做输出的功能，本地跑没问题，换台机器结果就乱了。需要有序遍历就用std::map，或者把 key 取出来排个序。

8.4 调试小技巧合集

先说一个最朴素的：临时把cin换成scanf或者加ios::sync_with_stdio(false)，在输入量百万级时能快好几倍。cin.tie(nullptr)也要一起加上，否则cout会在每次cin前自动刷新缓冲。

再说一个容易被忽略的：assert在 Release 编译下会被NDEBUG宏直接去掉，所以别把有副作用的代码塞进assert里。想让它生效就用-UNDEBUG，或者自己写个检查宏。

最后一个是计时。测算法性能时用std::chrono::steady_clock，别用clock()，后者测的是 CPU 时间，多线程下会失真：

auto t0 = std::chrono::steady_clock::now(); // ... 被测代码 ... auto ms = std::chrono::duration_cast<std::chrono::milliseconds>( std::chrono::steady_clock::now() - t0).count();

8.5 算法选型的最后几条经验

从我自己这几年的实际使用来看，几个判断可以省下很多纠结。第一，先在纸上把数据规模写下来，套上面那张复杂度表，方案自然就收窄了。第二，能排序就别用复杂数据结构，排序是常数最小、最不容易出错的预处理手段。第三，能二分就别用三分，能贪心就别上 DP，能 DP 就别写搜索。第四，写完先测三组数据：最小规模、最大规模、全相等或全逆序的边界情况，这三组能打掉八成的低级错误。

至于学习路径，我建议先把 STL 的容器和算法用熟，再回头手写排序和查找，最后啃图论和 DP。反过来先啃 DP 的话，很容易卡在“状态想不出来”上，挫败感很强。真正把复杂度分析的直觉练出来，是在你写下每一行循环时都下意识知道它会被执行多少次——到那一步，算法就不再是需要背的东西了。