在接触编程的十几年里我一直被同一个问题反复问到学算法到底该用哪门语言尤其当很多人已经能用 Python 流畅写出代码之后总觉得再碰 C 是自己给自己找罪受。但如果你聊的是算法本身我的结论始终没变C 是一线算法工程师、算法竞赛选手和面试候选人都绕不开的语言它的运行效率、STL 容器深度和内存控制能力决定了你在处理大规模数据时能走多远。这篇“C算法概述一”我想把算法学习里第一批必须吃透的内容完整梳理一遍复杂度分析、排序与查找、枚举回溯与剪枝、KMP、单调栈和单调队列最后再聊一聊 C 实现时容易踩的坑。适合刚入门算法、想把基础打厚的同学照着练也适合即将面试、想快速把核心索引过一遍的人。注意这篇文章默认你已经能写出基本的 C 程序知道什么是循环、数组、函数用过std::vector、std::string。如果这些还不熟建议先把 C 基础语法过一遍再回来否则后面的代码会读得比较吃力。1. 把地基打牢算法本质与复杂度1.1 先搞清楚“复杂度”到底在说什么很多人一上来就背排序算法背到最后只知道“快排很快”却说不出为什么快。算法好坏的标准从来不应该是“代码长短”而是它面对大数据量时还能不能撑住。这个“撑不撑得住”就是时间复杂度要回答的问题。你可以把输入规模想象成工作量合同从 100 份增加到 1 万份、100 万份时你的处理时间会怎么变如果处理时间几乎是平方级地涨那多半是 O(n²)如果只是从 10 秒变成 15 秒那说明你用了个更高效的方式。复杂度描述的不是“某一条语句跑多少个纳秒”而是“当 n 变大时运行时间增长的趋势”。大 O 记号的核心是去掉常数、只看最高项。O(n) 代表时间和数据量近似线性关系O(n²) 代表数据量翻倍、时间变成原来的四倍O(log n) 代表即使数据量翻倍时间也只增加一个常数步骤。真正有经验的工程师拿到题目第一件事不是写代码而是先估复杂度n 是 10^5那 O(n²) 基本走不通n 是 20深度搜索 N 皇后才算是可行方案。这个“先估复杂度”的习惯能帮你在几十秒内排除掉一大批错误方向。1.2 用两段代码感受 O(n) 和 O(log n)先看一个最基础的线性查找场景。假设有一个数组你想知道某个值是否存在#include vector int linearSearch(const std::vectorint arr, int target) { for (int i 0; i (int)arr.size(); i) { if (arr[i] target) return i; } return -1; }这段代码平均要检查一半元素最坏情况全部检查。时间复杂度 O(n)。如果数组有序呢二分查找登场int binarySearch(const std::vectorint arr, int target) { int left 0, right (int)arr.size() - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) return mid; if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }二分查找每次把搜索空间砍掉一半所以最坏也只要log2(n)次比较。n 等于一百万时线性查找平均要查五十万次二分查找最多二十次。这就是为什么“先排序再二分”这种组合在很多场景下非常划算排序只做一次后续多次查询都能受益。注意二分写法里left (right - left) / 2这是为了防止left right溢出尤其是当边界值接近 int 上限时这个细节能救你一次。1.3 空间与时间常见的取舍思路复杂度的另一个重要维度是空间复杂度也就是“算法占了多少额外内存”。很多新手只看时间忽略空间结果写出来的程序要么内存爆掉要么为了省内存把逻辑搞得极其复杂。实际工程里我们经常用“空间换时间”。最经典的例子是哈希表。给定 n 个数字反复询问某个数字是否存在。如果每次都线性查找一次查询就是 O(n)如果第一次遍历时把元素放进std::unordered_set之后每次查询只要 O(1)。这就是把一部分时间成本转化成了预处理的空间成本。在动态规划里这种交换更明显dp 数组用 O(n) 或 O(n²) 的空间记录已经算过的子问题避免递归里重复计算同一个状态。你要是写过斐波那契的朴素递归版本会看到它能把一个简单的问题算得比蜗牛还慢因为连 F(40) 都要展开无数重复分支而一旦用数组缓存结果立马变成线性时间。空间换时间不是万能解但如果内存够用多数情况下值得换。这个思想在后面的剪枝、记忆化搜索、静态预处理中都会反复出现。2. 排序与查找算法界的经典主力2.1 排序算法的横向对比排序是算法里最基础的“句式”也是面试高频区。我见过很多人被问到冒泡排序时露出一副“这也太简单了吧”的表情可让他分析稳定性却又说不出。这里直接给一张久经考验的对比表算法平均时间复杂度最坏时间复杂度额外空间稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定稳定性是什么意思就是相等元素的先后顺序在排序后是否保持不变。比如你按分数对学生排序如果希望分数相同的人保持原来的相对顺序就必须选稳定排序。冒泡复杂度高但代码极短、逻辑直观适合用来理解“比较和交换”的本质真正处理大规模数据时工程上很少手动写快排归并绝大多数情况直接用 STL 的std::sort就够了。2.2 归并排序与堆排序的简单实现虽然日常用 STL但面试手写和算法学习里归并、堆排依然高频。归并排序的思路是分治左边排好、右边排好再把两路合并。合并时需要一个临时数组这也是它 O(n) 空间的来源。void merge(std::vectorint nums, int left, int mid, int right) { std::vectorint temp(right - left 1); int i left, j mid 1, k 0; while (i mid j right) { if (nums[i] nums[j]) temp[k] nums[i]; else temp[k] nums[j]; } while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j]; for (int t 0; t (int)temp.size(); t) nums[left t] temp[t]; } void mergeSort(std::vectorint nums, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid 1, right); merge(nums, left, mid, right); }归并排序的“分”天然是 log 层“合”每层是 O(n)所以总复杂度 O(n log n)。它还是稳定排序这也是它常被用来做外部排序的原因。缺点是临时数组频繁分配如果数据量特别大申请内存的开销也不小写代码时我喜欢在函数外提前开一个可复用的临时数组避免反复分配。堆排序则是基于堆结构原地对数组整理空间 O(1)。写起来比归并复杂而且缓存命中率不如快排所以工程性能上不一定占优。但“堆”这个概念本身太重要了后面讲优先队列、Dijkstra 算法时都要用到。我的建议是先熟练掌握std::priority_queue维护最大/最小堆再在其基础上理解堆排序效率更高。2.3 二分查找的边界问题与 std::sort 工程实践二分查找边界是算法初学者翻车率最高的地点之一。左右边界、结束条件、下标更新任何一个错都会让人调试到怀疑人生。我的习惯是统一采用“左闭右闭”区间循环条件写left right更新时写left mid 1、right mid - 1。如果用“左闭右开”循环条件就要改成left right这两套思路不要混着记更不要每次现场推。C 里其实有现成的有序容器查找函数std::lower_bound返回第一个不小于目标值的位置std::upper_bound返回第一个大于目标值的位置。两者结合可以快速统计区间[l, r)内的元素个数。用它们的前提是区间已经按同一比较规则排好序否则结果完全不可预测。同理std::sort传入自定义比较器时必须保证“严格弱排序”不能在一组数据里一会儿 a b、一会儿 b a否则库内部会触发未定义行为或让排序结果变得混乱。还有一件常被忽略的小事std::sort底层是“内省排序”在快排递归过深时会自动切换成堆排序所以它保证最坏情况下也有 O(n log n)。很多教材讲“快速排序最坏 O(n²)”但在标准库层面上你已经不用太担心这个最坏情形。工程上优先用std::sort不要自己造轮子造出来的轮子大概率不如别人几十年的优化。3. 不只是枚举暴力枚举、回溯与剪枝3.1 枚举的价值验证正确性的底线很多初学者觉得暴力枚举是“笨办法”其实它是算法思维的起点。所谓枚举就是把所有可能的情况都列出来逐个检查是否合法。虽然效率低但它写着简单、不容易错遇到小规模数据时反而是最可靠的答案生成器。比如求数组的所有子集一个经典的递归写法如下void genSubsets(const std::vectorint nums, int idx, std::vectorint cur, std::vectorstd::vectorint res) { if (idx (int)nums.size()) { res.push_back(cur); return; } // 不选当前元素 genSubsets(nums, idx 1, cur, res); // 选当前元素 cur.push_back(nums[idx]); genSubsets(nums, idx 1, cur, res); cur.pop_back(); }n 个元素就有 2^n 个子集n20 时已经是 100 万量级n30 时 1 亿量级基本跑不动。所以在用枚举之前我总会先做一件事确认题目允许的规模。平时练习时我还会故意用暴力解法去跑小数据再和优化后的算法结果对拍。这个“暴力 对拍”的习惯是排查逻辑错误最有效的手段比对着题目看半天代码强十倍。3.2 回溯算法的通用模板回溯和枚举的区别在于枚举通常只是“列出全部”回溯则会在路径不合法时提前回退本质上是带状态的深度优先搜索。全排列是一个经典例子void backtrack(std::vectorint nums, std::vectorbool used, std::vectorint path, std::vectorstd::vectorint res) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i (int)nums.size(); i) { if (used[i]) continue; used[i] true; path.push_back(nums[i]); backtrack(nums, used, path, res); path.pop_back(); used[i] false; } }这段模板的关键点有两个一是递归后要“恢复现场”也就是pop_back和used[i] false二是在循环里跳过已经用过的元素。恢复现场是回溯题里最容易漏的一步。你以为只是把状态改回去实际上它决定了一棵搜索树能否正确分叉。如果不恢复后面的分支会拿到被污染的状态产出一堆重复或错误结果。初学者最容易犯的错就是“只往前 push忘了 pop”最后发现结果数量对不上。3.3 剪枝让回溯不再“一路莽”回溯的问题在于搜索空间往往是指数级的。如果只是机械地遍历所有分支n 稍微一大就卡死。剪枝的核心思想是在递归过程中发现某个分支已经没有希望得到合法解或者即使有解也不会比当前结果更优就立刻返回不再往下搜。以 N 皇后为例你在棋盘某一行放置皇后时如果当前位置已经和前面的某一斜线冲突那这一整棵子树都不可能合法直接跳过。再比如子集和问题搜索子集找目标和为 target 的组合一旦当前和已经超过 target后面全是正数越加越大直接return即可。剪枝要剪得准依赖对题目条件的理解。一个通用经验是尽量早地访问“约束最多”的分支因为越早发现冲突能剪掉的分支就越多。这种做法在竞赛里叫“可行性剪枝”在深度优先搜索和求解优化问题时非常常见。不要觉得剪枝只是给暴力搜索打补丁很多中等偏上的搜索题好的剪枝能把百万级搜索变成几十次计算。4. 字符串与线性结构的套路KMP、单调栈与单调队列4.1 KMP 字符串匹配字符串匹配的场景太常见了主串 text 长度为 n模式串 pattern 长度为 m想找到所有匹配位置。朴素算法是每个位置都试一遍最坏时间复杂度 O(n*m)比如主串全是 A、模式串是 AAA...B每移动一位都要扫到底。KMP 的核心是把已经匹配过的信息利用起来失败时不让主串指针回退而是让模式串跳到下一个可能的位置。这个“下一个位置”由前缀函数决定。前缀函数next[i]表示模式串[0..i]中最长相等真前缀和真后缀的长度。C 实现大致如下std::vectorint buildNext(const std::string pattern) { int m pattern.size(); std::vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 pattern[i] ! pattern[j]) j next[j - 1]; if (pattern[i] pattern[j]) j; next[i] j; } return next; } std::vectorint kmpMatch(const std::string text, const std::string pattern) { std::vectorint next buildNext(pattern); std::vectorint positions; int m pattern.size(); for (int i 0, j 0; i (int)text.size(); i) { while (j 0 text[i] ! pattern[j]) j next[j - 1]; if (text[i] pattern[j]) j; if (j m) { positions.push_back(i - m 1); j next[j - 1]; } } return positions; }这段代码的重点是while (j 0 text[i] ! pattern[j]) j next[j - 1];不理解的话建议手动画一遍匹配过程。KMP 匹配过程中主串指针只前进不回退模式串每次跳转又不会跳过头所以整体时间复杂度是 O(n m)。理解了 KMP你再看字符串哈希、AC 自动机这些后续内容都会顺很多。4.2 单调栈下一个更大的元素单调栈是一个看着抽象、用起来很顺的线性结构。它维护一个栈栈内元素从底到顶保持单调递增或递减。它的典型场景是“在数组里找每个元素右边第一个比它大的元素下标”也就是题目“找下一个身高更高的小朋友”那个模型。std::vectorint nextGreater(const std::vectorint heights) { int n heights.size(); std::vectorint ans(n, -1); std::vectorint st; for (int i 0; i n; i) { while (!st.empty() heights[st.back()] heights[i]) { ans[st.back()] i; st.pop_back(); } st.push_back(i); } return ans; }这段代码的精妙之处在于每个下标最多入栈一次、出栈一次所以整体 O(n)。当你遇到一个更大的元素它会“逼”前面的小个子出栈出栈时答案就已经确定了。很多题目比如柱状图最大矩形、接雨水都可以转化为单调栈问题。建议你拿到数组题先想想“是否存在一种栈结构能让答案在出栈时确定”如果行大概率就是单调栈这类解法。4.3 单调队列滑动窗口最大值滑动窗口最大值是单调队列最经典的场景。给定数组和一个固定窗口大小 k窗口每次右移一格求窗口内的最大值。朴素做法每移动一次扫一遍窗口复杂度 O(n*k)。用双端队列维护“窗口内候选元素的下标”队头始终是最大值。std::vectorint maxSlidingWindow(const std::vectorint nums, int k) { std::dequeint dq; std::vectorint res; for (int i 0; i (int)nums.size(); i) { if (!dq.empty() dq.front() i - k 1) dq.pop_front(); while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back(); dq.push_back(i); if (i k - 1) res.push_back(nums[dq.front()]); } return res; }队列里存的是下标而不是值这点很重要存下标才能判断过期元素是否已经离开窗口。每次新元素从队尾进来之前先把所有比它小或等于它的元素从队尾弹出因为它们已经不可能成为窗口最大值了。这样每个元素也只进出一次整体 O(n)。我自己的习惯是先用普通队列做窗口计数再升级成双端队列做单调队列循序渐进不容易写错。5. C 实现中的那些坑与优化5.1 数据范围少一点 int多一点 long long算法写对了数据范围没算对一样挂。C 里int通常是 32 位最大约 21 亿左右。看起来很多但两个 10^5 量级的数相乘就是 10^10直接就溢出成负数。比如求两点距离的平方int x 100000; int y 100000; long long dist x * y;这里的x * y已经按 int 算完再转成 long long结果还是错的。正确做法是long long dist 1LL * x * y;或者一开始就把 x、y 定义为 long long。养成习惯只要题目里出现 10^9 量级的数或者相乘后可能超过 21 亿一律用 long long涉及更大范围时再用__int128或自行处理高精度。5.2 容器使用与数组初始化算法题里最常用的容器是std::vector它连续存储、支持随机访问相比链表要友好得多。一个小建议是如果知道大概需要多少元素提前reserve避免扩容时反复拷贝。比如vectorint v; v.reserve(100000);。字符串数组初始化也是新手经常卡的地方。静态数组可以这么写std::string words[] {apple, banana, cherry};但如果元素个数不固定更推荐std::vectorstd::string words {apple, banana};。还有一个容易踩的坑char*指向字符串字面量时内存是只读的强行修改会引发未定义行为所以不要用char*去当可变字符串。用到字符串处理时优先考虑std::string它自带的find、substr、append接口足够覆盖大多数算法场景。这一章顺带说一句传参问题C 的“值传递”会把整个对象复制一份对大 vector 来说代价巨大“引用传递”不复制但如果不希望修改原值要加const。在算法函数里我基本都写成const std::vectorint arr既能避免拷贝又能明确告诉读代码的人“我不会乱改数据”。这一点与“指针 vs 引用 vs 值传递”的经典选择题相通理解三者的区别后很多容器相关的性能问题都能避开。5.3 调试与性能分析的实战习惯很多人配好了 VS Code 的 C/C 环境却不会用它调试算法。事实上我的日常流程是先在本地写好一个main函数用几个小用例跑通程序再用随机数据生成器生成数据把当前版本和一个暴力参考版本对拍最后才分析耗时。这个“暴力 对拍”技巧并不只属于竞赛在工程里做重构时同样能用来验证新旧代码逻辑是否等价。如果怀疑某段逻辑不对不要靠人眼检查几十行输出直接加中间日志或者用 VS Code 的断点功能。条件断点尤其好用只在迭代次数等于某个特定值时停下来观察现场。C 里也可以用assert做运行时断言比如assert(ans 0);条件不满足时程序会立刻崩掉方便定位。输入加速也是老生常谈在main里加两行std::ios::sync_with_stdio(false); std::cin.tie(nullptr);会让大数据量的 cin/cout 快很多。但注意sync_with_stdio(false)之后不能混用scanf/printf和cin/cout否则可能造成缓冲错乱。很多人在这里踩坑项目里最终选择了纯 C 流输入不再混用 C 风格 I/O。5.4 常用 STL 工具速记算法题里 STL 用得好能帮你省一半时间。这里列几个我常备的std::priority_queue默认是最大堆想要最小堆可以写priority_queueint, vectorint, greaterint pq;。当你需要频繁取集合中的最值时优先队列往往比set更快、更省心。std::set自带有序在 O(log n) 时间内完成查找、插入、删除但常数比vector大。如果你的数据只排序一次之后只做顺序遍历不如直接用vectorsort。std::unordered_map平均 O(1) 查找适合计数统计但不保证遍历顺序。它依赖哈希函数自定义结构体作为 key 时要当心内置类型int、string都已经有默认哈希直接用就好。6. 学完第一讲后怎么继续6.1 先建立可验证的题目清单完整掌握这一篇内容之后建议给自己列一个“验证清单”。每一类算法至少要独立写出三道题排序做一道逆序对计数用归并排序实现顺便理解稳定性的价值。二分做一道“最大值最小化”问题体会二分答案的套路。枚举回溯做一道 N 皇后并尝试加一两种剪枝策略看效果。字符串做一道 KMP 匹配把next数组打印出来看每一步变化。单调栈和单调队列分别找一道变种题比如柱状图最大矩形和滑动窗口最大值。这个清单不能省因为“看懂”和“能写”之间的距离只能通过亲手敲代码来缩短。题量不需要多但每一题都要问自己三个问题复杂度是多少为什么可以这样做如果数据规模扩大十倍代码还扛得住吗这三个问题比单纯“跑通样例”重要得多。6.2 学习习惯与工具环境学习算法没有捷径但有更省劲的路。我是固定每天留出四十到六十分钟状态好的时候啃一道中等难度的题状态懒的时候就做一道简单题外加拆解题解。做题不要贪多每道题做完我会在题解里记一句“这题的核心套路是什么”刷题一个月后再翻回来复习效率非常高。开发环境不必复杂VS Code 配好 C/C 插件、编译器和调试工具就能满足绝大多数练习场景。装好环境之后请一定亲手走一遍“写代码、编译、断点调试”的完整流程确保不是只会看教程、不会点按钮。在正式比赛或线上测评环境中编译环境往往是预配置好的更值得培养的是“完全不依赖 IDE 提示也能写对函数原型”的能力。这里再分享一个我个人的习惯不管做哪道题第一步先把题目里 n 的范围圈出来再写下复杂度预判。这个动作看起来微不足道但它逼着你在动手前就思考规模而不是先写代码碰运气。很多看起来很难的题读完范围之后就已经能排除掉几类错误方向这种敏感度就是靠一次次“先估复杂度再写代码”练出来的。等你把这些内容吃透后面的动态规划、图论、更多进阶字符串算法就能顺利展开到时候你会发现所有高级套路都建立在今天这块地基上。