算法学习第35天：排序、枚举、剪枝与分治的基础复盘

“更弱智的算法学习”写到第35天了，说实话我自己也没想到真能坚持下来。这个系列标题里的“更弱智”不是谦虚，而是我给自己定的一条硬标准：每个算法必须用我能听懂的废话解释一遍，写出来的代码也必须是那种丢了注释还能看懂的写法。今天是第35天，我没急着学新东西，而是把过去一个月翻车最多的几个基础点重新翻出来整理了一遍：排序算法、暴力枚举、剪枝，顺带补了一点分治思路。如果你也是那种“收藏夹里存了几百个算法教程，一打开编辑器还是不知道从哪下手”的人，这篇可以当一份侧写参考——我踩过的坑，你大概率也会踩。

1. 第35天，我为什么回头啃排序算法

很多人觉得排序太老土、太简单，不值得专门花时间学。我一开始也是这么想的，结果被现实狠狠教育了一顿。所以今天第一个主题，就是把排序算法重新放到它应有的位置上。

1.1 排序算法是算法界的“九九乘法表”

数据结构排序算法这东西，看起来谁都懂，但真正能徒手写对的人并不多。我第3天的时候觉得自己会冒泡排序，结果一合上教程，打开编辑器直接傻眼：两个循环的边界条件怎么写来着？j要不要减i？为什么有的排序要交换好几轮？

排序算法之所以值得专门回炉，是因为它是所有算法题的基础工具。不管是LeetCode必刷基础算法题，还是Java蓝桥杯算法题目，很多人碰到的第一道坎基本都是排序变形题：合并两个有序数组、找第k大的数、区间合并、逆序对统计……全都是在排序的地基上盖房子。你如果连冒泡和归并都写不顺，后面学哈希、图论、动态规划的时候，会发现自己连“准备数据”这一步都做得特别吃力。

我建议初学者把排序当成“九九乘法表”来对待：不需要思考，但是必须形成肌肉记忆。就像你不会去背乘法口诀的原理才开始算数一样，排序的模板代码也需要达到“伸手就写”的程度。这不是应试思维，而是因为排序实在太常作为其他算法的前置步骤出现，如果你每次调用排序都要想半天，精力就全浪费在搬砖上了，哪还有余力学真正的核心思路？

1.2 不懂排序，后面的KMP和Tarjan会加倍痛苦

我之前硬啃KMP算法的时候卡了整整两天，当时我还以为是自己智商有问题。后来回头看，发现最让我崩溃的不是那个next数组到底怎么求，而是我对“怎么高效地利用已有顺序信息”这件事本身没有直觉。KMP里的前缀函数，本质上是在维护一个叫“部分匹配表”的东西，它依赖你对数组操作、指针移动、还有“跳过已比较位置”的理解——而这些基本功，恰恰都能在排序算法里练出来。

同理，Tarjan算法看起来神秘，什么时间戳、low值、强连通分量，我第一次看到的时候感觉自己在看天书。后来明白了一件事：它本质上是对DFS的遍历过程做了一套“时间排序”。如果你连排序里最基本的“比较、交换、归并”都没有建立肌肉记忆，读到后半程就全是玄学了。

我自己第35天回头整理排序，很大一部分原因就是发现自己前面的基础构筑不够稳。基础不牢的代价不是你“不会某一道题”，而是你会像看悬疑小说被剧透一样，刚看到题目就知道思路不对，却写不出任何能跑的代码。所以这两天我干脆把新算法停一停，买了个便宜白板贴在书桌前面，把每种排序的状态变化画成图。画完再回头去看之前看不懂的那些高级算法的讲解，感觉脑子里的线一下子就通了。

1.3 面试官最想从排序里看到什么

算法工程师面试里，排序问题属于高频中的高频。但面试官问排序，绝对不是想让你现场造一个工业级轮子。之前我以为面试考排序就是考“背代码”，后来我模拟面试了几次才明白，他们真正想看的是三件事：

第一，你能不能分析复杂度。说得出平均时间复杂度和最坏时间复杂度，还要能解释为什么快排的平均是O(n log n)，最坏却是O(n^2)。第二，你会不会处理边界条件。空数组怎么办？只有一个元素怎么办？数组里有大量重复元素怎么办？这些细节暴露的是工程素养。第三，你能不能讲清楚稳定性。什么是稳定排序，为什么归并排序稳定而快排不稳定，如果面试官问“让快排变得稳定”你会怎么处理。

这给了我一个很具体的复习思路：不要只背代码，要做一个排序算法对比表，把一个排序的“翻车场景”写下来。比如堆排序的稳定性为什么差、快排在什么数据分布下会退化、插入排序在近乎有序数组里为什么反而快。这些问题比单纯敲代码值钱得多，因为它们才是面试场上的加分点。

2. 用最“弱智”的方式理解暴力枚举和剪枝

第二个主题是暴力枚举，这个名字听起来就很不聪明，但我今天反而想为它正个名。暴力枚举其实是整个算法世界里最可靠的基石。

2.1 暴力枚举：先学会把答案“试”出来

暴力枚举算法的思路简单到令人发指：把所有可能的解一个一个列出来，逐个验证，找到符合条件的那个就完事。比如给你一个长度为偶数的数组，问能不能分成两组让两组和相等，你可以把所有分组方式都试一遍；再比如求一个数组的连续子数组最大和，暴力做法就是用三层循环把所有子数组都扫一遍。

我刚开始学的时候特别鄙视暴力解法，觉得这谁不会啊。但后来做LeetCode刷题刷到一定阶段，我发现一个反直觉的事实：很多所谓的“优化算法”，其实是把暴力枚举压缩进了一个更聪明的数据结构里。比如前缀和优化的子数组求和、双指针优化的滑动窗口、哈希表优化过的两数之和，本质都在干同一件事——少试几种不合理的组合。

更重要的是，暴力枚举是所有算法的“正确性基准”。你现在写一个网上看来的高级算法，怎么确认它没写错？最靠谱的方法就是：用一个绝对正确的暴力版本去和它对拍。我第35天前就养成了这个习惯：写完一段动态规划或贪心代码，一定先跑一遍纯暴力生成的随机数据，两边结果不一致，那就说明我的优化算法写错了，而不是暴力那道题本身有问题。这个方法朴素，但真的救了我很多次。

2.2 剪枝：不是变聪明，而是提前“认怂”

暴力枚举的痛点是复杂度高，比如枚举一个包含n个元素的集合的所有子集，需要的计算量是2的n次方。n=20就已经百万级别，n=30就十亿级别了。这时候就需要剪枝算法出手。

剪枝的核心思路说出来也很弱智：如果当前这个分支已经确定不可能走到答案了，就别再往下走了。就好比你找钥匙，已经确定客厅沙发下面没有，那就不会再去把沙发翻第三遍。但在算法里，这个“确定”需要有严格的逻辑依据，不然剪的不对就会漏掉正确答案。

我见过很多初学者刚学剪枝的时候特别兴奋，觉得终于可以告别脑残的暴力枚举了。但剪枝有个大前提：你先得有一棵完整的搜索树，知道哪些分支可能存在答案，哪些不可能。也就是说，你得先老老实实把暴力写出来，才能在上面做优化。如果你连最朴素的枚举都写不顺，直接想剪枝，那大概率剪掉的是正确答案。

2.3 一个可以上手跑的枚举+剪枝案例

今天下午我一直在练一道经典的子集和问题：给定一个数组，判断能否从中选出若干个数，使得它们的和等于target。暴力解法就是枚举每个数选或者不选，代码写出来其实很短：

bool dfs(vector<int>& nums, int index, int sum, int target) { if (sum == target) return true; if (index == nums.size()) return false; // 不选当前这个数 if (dfs(nums, index + 1, sum, target)) return true; // 选当前这个数 if (dfs(nums, index + 1, sum + nums[index], target)) return true; return false; }

这段代码每一行我都看得懂，但它的复杂度是O(2^n)。如果数组有40个数，那就基本上跑不完了。加了剪枝之后就完全不一样：

// 先排序，方便后面剪枝 sort(nums.begin(), nums.end()); bool dfsPrune(vector<int>& nums, int index, int sum, int target) { if (sum == target) return true; if (index == nums.size()) return false; if (sum > target) return false; // 核心剪枝：和已经超过目标，继续加只会更大 if (dfsPrune(nums, index + 1, sum, target)) return true; if (dfsPrune(nums, index + 1, sum + nums[index], target)) return true; return false; }

注意这里有个细节：只有先对数组做排序，这个“sum > target就返回”的剪枝才安全。因为如果数组里有负数，当前和大了不代表以后不能变小，直接剪掉就可能漏掉正确答案。这就是为什么我在这个例子里先做了排序预处理。实际操作中，剪枝是否安全永远是第一位的，其次才是剪枝的效率。

这道题背后的思想，其实就是把问题抽象成一棵决策树，每个节点代表一个状态，每个分支代表一次选择。懂了这一点，后面再接触那些名字特别长的搜索类算法，我第一次听说深度强化学习算法里那堆缩写的时候也觉得头大，后来发现很多基础框架也还是在“遍历状态空间+剪枝”的逻辑上不断叠加，只不过状态本身变得更复杂了而已。

3. 从排序到分治：一组组合拳

如果说暴力枚举是算法的左脚，那分治就是右脚。第35天我把归并排序和快排重新拿出来手写，突然意识到一件事：我之前总觉得它们是两个不同的排序算法，其实它们的骨架都是C++分治算法的经典模板。

3.1 归并排序：分治思想的活教材

归并排序的流程，用一句话就能说清楚：把数组对半拆，拆到只剩一个元素，然后两两合并成有序。这个“拆”就是分，“合并”就是治。

我之前看归并排序的视频觉得特别简单，轮到自己写的时候却频繁翻车。翻车的核心原因是我没有真正理解merge这一步在干什么。合并两个有序数组，需要一个额外的临时数组来放结果，用两个指针分别指向左边数组和右边数组的头部，谁小就先把谁放进临时数组。这个过程你如果只是在脑子里“觉得”懂了，不动手写，很快就会在边界条件上栽跟头。

归并排序还有一点值得每个初学算法的人亲手推一遍：它的时间复杂度为什么是O(n log n)。推法很简单，每一层递归都会把问题规模减半，递归深度是log2(n)，每一层我要处理的数据总量是O(n)，乘起来就是O(n log n)。这个推导本身不复杂，但很多人没有自己算过，所以只留下一个模糊印象“归并是nlogn的”，过几天就忘了。我自己用白纸画了三棵递归树之后，这个复杂度就再也忘不掉了。

归并排序的另一个价值，是它可以顺手解决逆序对问题。所谓逆序对，就是数组里左边比右边大的数对，比如[3,1,2]里，3和1、3和2都是逆序对。归并排序在合并的过程中，天然就能统计出逆序对的数量，这个扩展开来就是LeetCode上一道经典的中等难度题。学一个排序顺带学会一个经典题型，这种性价比很高的操作，值得刷题的朋友重点掌握。

3.2 快排和堆排序，它们的底层逻辑是完全两套思路

快排和堆排序都能达到平均O(n log n)，你都听说过，但很少有人把它们放在一起对比。快排的思路是选一个基准值pivot，把比它小的放左边、比它大的放右边，然后递归处理左右两部分。这本质上是一种“分区”思想：每次处理完，pivot就到了它最终该在的位置。

堆排序则完全不同。它是先把整个数组构建成一个大顶堆，保证堆顶元素全局最大，然后把堆顶和堆尾交换，再把堆的规模缩小一位，重新调整堆。这本质上是一种“选择”思想：每次都从剩余元素里挑中最大值放到最后面。

我在学堆排序的时候特别容易搞混下标，因为堆通常用数组表示，下标0是堆顶，下标i的左右孩子在2i+1和2i+2。我第一次手写的时候，把调整堆的函数写得乱七八糟，调了一个晚上才转对。后来我给自己编了一个类比：快排像是老师在教室里重新给同学分座位，每次有一位同学被固定到正确位置；堆排序像是大家排队轮流上台领奖，但队伍一直在变。这个比喻可能不太严谨，但至少能让我在写代码的时候记住“堆排序的核心不是排序，是维护一个优先级关系”。

顺带也说一下C++ STL里的sort到底做了什么。很多初学者以为STL的sort是纯快排，其实它是“内省排序”，也就是快排、堆排、插入排序三者的组合：默认走快排，但递归深度太深的时候换成堆排序防止退化，遇到小数组时换成插入排序减少常数开销。这个设计非常巧妙，也说明真实的工程代码里各种排序算法并不是互斥的，而是各取所长。

3.3 手动推一遍，比看十遍视频都管用

我今天下午给自己布置了一个任务：不看任何参考，在白纸上把冒泡、插入、选择、快排、归并、堆排六种排序分别推演一遍，每次推演都写下每一轮的数组状态。这个练习看起来非常笨，但收获极大。

比如推演完冒泡排序我才真正明白，为什么它的优化版是加一个“本轮是否发生交换”的标记。如果某一轮从头到尾都没有发生交换，说明整个数组已经有序了，后面几轮完全不用再跑。这个优化在普通场景下没什么用，但在处理“几乎有序”的数据集时能省钱省到肉疼。

推演快排的时候我则发现了一个很经典的坑：如果每次选的pivot都是当前区间的最小值，那快排会退化成O(n^2)的复杂度。这就是面试官最爱问的场景之一：什么样的输入会让快排变慢？答案是“基本有序”的数据，因为每次分区都很不平衡。标准库里用内省排序来规避，但在手写快排的时候你必须有这个意识。

我的建议是，学算法不要只刷题或者只看视频，每周抽一天时间，关掉编辑器，用纸笔把学过的东西推演一遍。看起来效率低，但推完一遍之后你的记忆深度是视频的十倍不止。

4. 实操现场：把概念落到代码里的全过程

这一节我完整记录一下今天做基础练习的过程，包括我是怎么翻车的、又怎么爬起来的。可能比任何教程都更适合参考，因为我把错误也写出来了。

4.1 第一遍默写冒泡排序，暴露了三个问题

今天下午我做的第一件事，是默写冒泡排序。按理说这是最简单的排序，但结果我写了三遍才完全对。第一次错在第二层循环的边界：我把j的结束条件写成了n-1，导致每一轮都多比较了几次，虽然结果对，但效率不对，而且没理解“每一轮最大的数已经沉底，不需要再碰它”这个关键点。

第二次错在忘了加提前退出的标记，也就是前面说的swapped优化。剑走偏锋来讲，这不算“错”，但面试官一眼就能看出你写的是标准教科书版还是只会背代码的版本。第三次我终于写对了，但也花了不少时间。

这段经历给我的教训是：默写和自己“以为会了”完全是两回事。你自以为记住的知识点，落到代码里就会现出原形。这里也建议大家从今天开始，给自己一个“闭卷默写”的任务，写完再对照标准实现查漏补缺，而不是永远开着答案抄。

4.2 第二遍用递归写归并排序，差点把边界写崩

默写完冒泡之后，我开始写归并排序。递归版本的代码思路很清楚，但我在merge函数里犯了三个典型错误。

第一个错误是临时数组的下标没对齐。merge的时候，我的循环是逐位写入临时数组，最后应该把临时数组的内容复制回原数组对应位置，结果我写成了从原数组开头开始复制，导致数组完全错乱。纠正方法是在复制回去的时候加上左边界偏移量：arr[left + i] = temp[i]。

第二个错误是递归终止条件写晚了。我在写mergeSort函数的时候，第一行没有写“如果区间长度小于等于1就直接返回”的终止条件，结果递归永远不结束，直接把程序跑崩了。这个错误虽然低级，但它说明了一个重要习惯：任何递归函数，先写终止条件再写递归公式。

第三个错误是关于合并操作的一个理解偏差。我一开始以为merge函数应该返回新数组然后再接回去，后来才发现如果每次都返回新数组，空间复杂度会特别难看。正确的做法是在原数组上原地修改，配合一块临时缓冲区。

我把归并排序掰开揉碎写完一遍之后，又拿一个长度为5的小数组手动推演了一遍，把每次递归调用的区间和中间结果写下来，才真正做到心里踏实。这种“拿着小数据手工走一遍”的方法，我建议每个人都做一次，尤其面试前特别管用。

4.3 第三遍手写堆排序，越写越怀疑人生

堆排序是我今天花时间最长的部分。它的核心操作就两个：建堆，以及从堆顶取最大值后重新调整堆。代码本身不长，但理解起来是真的绕。

我选择了“从最后一个非叶子节点开始，从下往上调整”的建堆方式。为什么必须从倒数第二层开始而不是从根节点开始？因为调整堆的前提是左右子树已经是合法的堆，只有从底部往上调整，才能保证每一轮都在处理合法的子树。这个顺序问题，我一开始完全没转过弯，调了半天才发现方向反了。

调整堆的下沉函数我写了好几版，最后的版本大概是这样的：

void heapify(vector<int>& arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } }

这段代码的递归点在哪？如果你把节点i和它某个孩子做了交换，那被换下去的那个孩子原来的子树可能已经不是堆了，所以你必须继续调整那个孩子作为根节点的子树。这个逻辑很多教程一笔带过，但实际操作中，漏掉这一行递归就会导致整个堆排序失效。

写完堆排序我发现，它是六种排序里我最容易搞混的。但经过今天的推演，我对“为什么堆排序是原地排序且不稳定”有了新的理解。所谓不稳定，是因为堆排序在堆顶交换时，可能把相同大小的两个元素的相对顺序打乱。面试如果问到这个，你就不能再只说一句“堆排序不稳定就完了，最好能给这个具体例子。

4.4 结合刷题场景，把排序派上用场

今天基础练习完成后，我还整理了一张小表，帮自己把排序和题目类型对应起来。这张表我贴在书桌上，也分享给你们：

这张表的出现，让我意识到学排序不是单纯背代码，而是要能够根据“数据特点”和“题目限制”选择合适的方法。这种能力，是面试和竞赛中真正拉开差距的地方。

5. 常见问题与避坑记录（35天踩过的坑）

写到这里，我觉得最实用的部分其实是这一节。下面这些问题，我全都在过去一个多月里真实遇到过，把排查思路和解决方法一并写出来，希望能帮大家少走点弯路。

5.1 排序算法背了又忘，怎么回事

这几乎是最多初学者问的问题。我的答案是：你背的不是“过程”，而是“代码”。如果你只是对着代码一行一行背，过两天就忘干净了。正确的做法是背“过程描述”。冒泡排序的过程是“每轮把最大的冒到末尾”，插入排序的过程是“从前往后维护有序区，每次把当前元素插入到有序区的合适位置”。用过程描述去推代码，远比死记硬背牢固。

具体操作上，我推荐一个“三步复习法”：第一步，不翻资料，在纸上画出算法的一次完整执行过程；第二步，根据画的过程尝试手写代码；第三步，把算法讲给另一个人听，讲不通的地方就是你还没懂的地方。这三步走完，基本很难再忘。

5.2 暴力枚举跑不动怎么办

遇到数据规模比较大的题目，暴力枚举跑不动是常态。我的排查顺序是这样的：第一步看能不能换一种更省空间的枚举方式，比如把排列改成组合；第二步看当前搜索树有没有明显的剪枝机会，比如已经超过目标值就返回；第三步评估数据规模，如果剪枝后仍然可能超时，那就要考虑是不是该换算法方向了。

这里给一个非常粗略的规模参考：n不超过10可以枚举全排列，n在20左右可以考虑状态压缩DP，n在30上下用剪枝后有希望，n一旦超过40就基本要靠更优化的算法了。当然这是经验值，具体还得看题目限制。有一点必须提醒：剪枝不是万能的，它只能去掉明显无效的分支，最坏情况下的复杂度还是可能很高。如果你对自己的剪枝策略不是100%确定，一定要保留一个暴力版本做对拍，防止剪掉正确答案。

5.3 工作里用STL还是自己手写

这个问题我纠结了很久，现在的结论是分场景。工作或打比赛的时候，能用STL绝对不要自己造轮子。C++ STL里的sort经过高度优化，各种边界情况都处理好了，你手写的排序在绝大多数场景下跑不过它。刷题的时候，除非题目明确要求你手写某种排序，否则直接用sort也没问题。

但在面试的时候，情况就反过来。面试官让你实现快排或归并，你当然不能直接说“我用sort”，你需要展示自己的手写能力。我现在的建议是：日常练习时，基础排序至少用手写各过一遍；实际做题时，直接用STL。两者不冲突，都是为了让你在不同场景下都能交出自己的答卷。

5.4 看到高级算法名词就心慌怎么办

算法世界里，各种名词满天飞。PID算法、粒子群算法、匈牙利算法、各种带缩写字母的强化学习方法……我第一次看到这些词的时候，恐慌感直接拉满，觉得自己这辈子都学不完。后来我慢慢发现，很多看起来吓人的名词，其实背后都是基础思想的不同组合。你不需要在第一阶段把它们全部学会，只需要做到“遇到没见过的名词不慌，知道它有基础结构，先去搜个最短的科普，再看一个最小例子，然后放下”。

具体到今天的排序和枚举，它们其实是很多高级算法的“前菜”。比如我之前一直不敢碰的那些深度强化学习算法的名字，底层少不了状态遍历、策略评估、好坏剪枝这样的基本盘。你连排序和枚举都没有啃透，直接去看那些东西，当然会觉得自己是弱智。反过来，把眼前这一小块地基夯实了，你会发现那些名词看着依然很多，但你已经能分辨出哪些跟自己的方向有关，哪些可以暂时不用管。

最后说点个人感受

坚持到第35天，我最明显的变化不是背下了多少个算法，而是我开始习惯性地把新问题拆成自己认识的结构去套用，排序、枚举、剪枝、分治，这些东西像乐高零件一样在脑子里拼来拼去。学习方法上，我最大的体会是：做笔记的时候感觉很充实是假学习，合上屏幕还能默出代码才是真学会。我给自己定了一个小规矩——每学一个算法，都必须写成一篇通俗的博客讲明白，讲不明白就说明还没学透。第35天只是一个节点，后面还有图论、动态规划的专题等着我去翻车，到时候再把这些新坑整理出来分享给你们。