早上打开电脑习惯性翻了一下昨天写的算法笔记正好看到文件夹里躺着今天要整理的排序算法草稿。这是算法日记的第三天状态比前两天好了不少至少不用对着题目发十分钟呆了。今天的主线很明确把排序算法里最容易混淆的几个理清楚再用LeetCode上两道贪心题检验一下昨天的学习效果。可能有朋友会问算法不是刷题就完事了吗为什么要专门写日记复盘我自己的体会是刷题只是输入真正把思路转化成自己的东西还得靠回头整理。第三天的内容其实是一个分水岭前面两天熟悉的基础数据结构开始派上用场排序、递归、贪心这些思想开始真正交织在一起。今天这篇日记我打算把当天的完整思路、代码细节、踩过的坑都写清楚既能给后面回看留个记录也希望给同在刷算法的朋友一些参考。1. 今日主线排序算法没必要全都手写但核心得会推导排序算法是算法日记里绕不开的一块面试也好、平时写业务代码也罢排序思想其实无处不在。今天花了大概一个半小时把冒泡、归并、堆排序重新推了一遍。为什么是这三个因为它们的思路分别对应了三种完全不同的问题解决方式暴力交换、分治合并、基于数据结构的调整。1.1 冒泡排序的优化空间冒泡排序是很多人接触的第一个排序算法但说实话如果面试只是背一个双重循环很容易被追问到哑口无言。冒泡的核心思想是相邻元素两两比较把大的往后推移每一轮至少让一个元素到达最终位置。这个思路本身不难真正值得玩味的是它的优化空间。最基本的版本是两层循环外层控制轮数内层做比较交换时间复杂度稳定在O(n²)。但加一个标志位之后情况就不一样了void bubbleSort(vectorint nums) { int n nums.size(); bool swapped; for (int i 0; i n - 1; i) { swapped false; for (int j 0; j n - 1 - i; j) { if (nums[j] nums[j 1]) { swap(nums[j], nums[j 1]); swapped true; } } if (!swapped) break; // 某一轮没有任何交换说明已经有序 } }这个优化在最好情况下能让时间复杂度降到O(n)。我当时第一次看到这个写法时其实不太理解觉得加一个布尔变量能有多大区别。后来在排序一个几乎有序的数组时才真切体会到原本要跑n轮现在跑一两轮就提前结束性能提升非常明显。冒泡排序虽然在实际工程中很少直接用但它教给我们一个很重要的思维方式通过记录状态来判断是否可以提前终止。网上还有一种冒泡的变体叫鸡尾酒排序就是从左往右冒泡一轮再从右往左冒泡一轮来回交替。这个变体在数组两端都有大数和小数时效率更高不过面试出现的概率不高了解即可。1.2 为什么手写归并排序分治思想的缩影归并排序我建议人人都能手写一遍不是说面试一定会考而是它的分治思路是很多算法的基础。归并排序的流程一句话概括把数组不断对半拆拆到只剩一个元素再两两合并成有序数组。拆分是递归的过程合并则是双指针的经典应用。手写归并排序的核心难点其实不在拆分而在合并这一步。合并两个有序数组时需要额外开一个临时数组来存结果然后在两个子数组之间用双指针扫一遍void merge(vectorint nums, int left, int mid, int right) { 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 idx 0; idx temp.size(); idx) { nums[left idx] temp[idx]; } } void mergeSort(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); }这里有一个细节我一开始没注意计算mid的时候我习惯写成(left right) / 2后来看到很多标准库实现里用left (right - left) / 2特意查了一下原因是为了防止left和right都很大时整数相加溢出。在LeetCode上题目给出的数组长度一般不会导致这个问题但养成这个习惯没有坏处。归并排序的时间复杂度是O(n log n)无论最好还是最坏都是这个值非常稳定。空间复杂度是O(n)因为每次合并都要开临时数组。这也是归并排序不如快排受待见的原因之一——空间占用大。不过归并排序有一个快排没有的优势稳定。排序前后相同元素的相对位置不会改变。在需要稳定排序的场景下归并排序是首选。写归并排序时还有一个容易出现的问题递归的终止条件。我之前犯过一个错误把终止条件写成了if (left right) return;在一半情况下没问题但有些边界情况会因为left大于right而陷入死循环。后来统一改成if (left right)一劳永逸。2. 堆排序与优先队列的联动堆排序是今天花费时间最长的一块不是说代码有多难写而是要真正理解堆的调整过程——上浮和下沉——需要反复在纸上画图推演。堆这个结构本身就是一颗完全二叉树在数组里存储时父节点和子节点的下标关系是父节点下标为i左孩子是2i1右孩子是2i2。这个映射关系是堆排序一切操作的基础务必记牢。2.1 从数组到堆的调整过程堆排序的第一步是建堆也就是把一个无序数组调整成堆结构。如果要从大到小排序建小顶堆从小到大排序建大顶堆。这里有个容易绕晕的地方排序结果是升序用的是大顶堆每次把堆顶元素最大值换到数组末尾然后对剩下的部分重新调整堆。重点说一下下沉操作也就是heapify。它的作用是让某个节点顺着子节点中较大或较小的路径不断下移直到满足堆的性质。代码长这样void heapify(vectorint nums, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n nums[left] nums[largest]) largest left; if (right n nums[right] nums[largest]) largest right; if (largest ! i) { swap(nums[i], nums[largest]); heapify(nums, n, largest); } } void heapSort(vectorint nums) { int n nums.size(); for (int i n / 2 - 1; i 0; i--) { heapify(nums, n, i); } for (int i n - 1; i 0; i--) { swap(nums[0], nums[i]); heapify(nums, i, 0); } }建堆时为什么从n / 2 - 1开始因为数组下标从0开始最后一个非叶子节点的下标就是n / 2 - 1。叶子节点本身不用调整所以从最后一个非叶子节点往前逐个做下沉操作即可。我画了几次堆调整的图之后发现堆排序其实就像在维护一个动态的最大值池。每次取出最大值然后快速恢复堆结构。这个思路在解决TopK问题、合并K个有序链表、数据流中位数等问题时非常有用。2.2 一道堆排序能解的实战题为了检验堆的掌握情况今天顺手做了一道经典的LeetCode题目——数组中的第K个最大元素。题目要求找到数组中第K大的元素最直接的想法是排序后取下标但时间复杂度是O(n log n)。用堆来做可以维护一个大小为K的小顶堆遍历数组如果当前元素比堆顶大就替换堆顶并调整堆遍历结束后堆顶就是第K大的元素。int findKthLargest(vectorint nums, int k) { priority_queueint, vectorint, greaterint minHeap; for (int num : nums) { if (minHeap.size() k) { minHeap.push(num); } else if (num minHeap.top()) { minHeap.pop(); minHeap.push(num); } } return minHeap.top(); }C的priority_queue默认是大顶堆如果要小顶堆需要传入greaterint作为比较函数。这个细节很容易被忽略输出结果出来是错的才想起比较器写反了。用堆做这道题时间复杂度是O(n log k)当数组很大、K很小时比排序要快不少。这也是面试官比较喜欢看到的解法因为不仅考察了堆的知识还能看出你有没有空间敏感度。堆排序本身在工程中其实不常见因为它的缓存局部性不如快排而且不稳定。但堆这种数据结构本身太重要了优先级队列背后就是堆。今天我们写的堆排序等于是把堆的构建和调整过程完整过了一遍后面用优先级队列处理问题时就会踏实很多。3. 贪心算法实战跳跃游戏2今天最后的实战环节选了跳跃游戏2原因很简单这道题能很好地检验贪心思想有没有真正理解。题目描述大致是给定一个非负整数数组每个元素代表你在该位置可以跳跃的最大长度初始位置在下标0问到达最后一个下标需要的最少跳跃次数。3.1 贪心策略的直觉我第一次做这道题的时候想的是每次跳最远跳完之后再看当前位置能到哪结果发现不对。比如[2, 3, 1, 1, 4]如果第一次跳2步到下标2位置的值是1再跳只能到下标3下一步才能到下标4一共要跳3次。但是最优解是先跳到下标1再直接跳到终点只需要2次。贪心的核心是在当前能到达的范围内挑一个能让下一步覆盖范围最大的位置作为落脚点而不是简单地跳最远。换句话说每一步都关注这一步跳完之后下一步最大能覆盖到哪里。用一个变量curEnd表示当前这一步能到达的最远位置farthest表示在curEnd范围内遍历时能到达的全局最远位置。当遍历到curEnd时说明这一步已经没有更多选择了必须跳一步跳到farthest同时跳跃次数加一。3.2 代码实现与边界处理int jump(vectorint nums) { int n nums.size(); if (n 1) return 0; int jumps 0; int curEnd 0; int farthest 0; for (int i 0; i n - 1; i) { farthest max(farthest, i nums[i]); if (i curEnd) { jumps; curEnd farthest; } } return jumps; }注意循环的范围是i n - 1不是i n。第一次写的时候没有注意这个细节多算了一次跳跃。原因很简单最后一个位置不需要跳跃已经到达终点了。还有一个边界情况是数组长度只有1不需要跳跃直接返回0。这个解法的时间复杂度是O(n)空间复杂度O(1)是一个非常典型的贪心场景。每一步做当下看起来最优的选择——让下一步覆盖范围最大——最终得到全局最优解。贪心算法并不是所有问题都适用它需要问题具有贪心选择性质但跳跃游戏2恰好满足所以能用这个思路快速解决。做完之后再回看题目描述会发现贪心算法的思考方式其实很像我们日常做计划既然不可能精确知道后面每一步会发生什么那就优先选择未来选择余地最大的路线。这个思路和动态规划的区别在于贪心不会回头考虑多种可能性它每一步都锁定一个局部最优解。4. 今日踩坑与调试记录算法日记如果不能记录踩坑过程价值至少打了一半折扣。今天在写这几个算法时遇到了好几个问题有些是粗心导致的有些是对算法理解不够深入导致的。我按照问题类型整理成一个小表格方便以后回看。4.1 经典bug边界条件和数组越界今天遇到的第一个问题是归并排序里我在merge函数中忘了把临时数组复制回原数组。结果排序后数组没有变化白白跑了半天。排查方法很简单在关键位置打印中间结果发现左右两部分确实各自有序但合成后没有改变原数组才意识到少了最后一步复制。第二个问题是堆排序里的下标计算。孩子在数组中的下标是2i1和2i2这个公式本身没错但如果数组长度是偶数最后一个非叶子节点的计算就要特别小心。我写建堆循环时用的是n / 2 - 1这个在n0和n1的情况下会出现负下标手动加一层判断更稳妥。边界条件可以说是算法题中出错率最高的地方我的习惯是每次写完代码先手动跑几个特殊用例空数组、单元素数组、完全有序数组、完全逆序数组、有大量重复元素的数组。这几类用例能覆盖绝大多数边界问题。4.2 递归栈溢出的隐患归并排序和堆排序的递归版本都涉及递归调用当数组长度特别大时递归深度接近log n一般不会栈溢出。但如果递归终止条件写错递归无法正常返回栈溢出就会发生。我之前写归并排序时把终止条件写成if (left right) return;这在一半情况下没问题但有一种情况会出bug当left right时函数不会return会继续递归直到栈溢出。虽然正常递归过程中不会出现left right但防御性编程的思想还是要有的写成if (left right)能彻底避免这个隐患。另外递归函数里的临时数组如果每一层递归都申请会频繁触发内存分配性能损耗很大。更高效的做法是在递归函数外面一次性申请一个足够大的临时数组通过下标传入合并函数。这个优化在数据量小的时候看不出来数据量上到百万级别就能感受到差距了。4.3 复杂度分析与面试追问今天在复盘每个算法时我都额外做了一步用文字写清楚时间复杂度和空间复杂度是怎么推导的。冒泡排序最坏O(n²)最好O(n)平均O(n²)归并排序始终O(n log n)空间O(n)堆排序始终O(n log n)空间O(1)但不稳定。堆排序的空间复杂度看起来是O(1)因为它只用了swap操作不依赖额外数组。但要注意递归实现的堆排序函数调用栈也算空间所以严格来说递归版的堆排序空间复杂度是O(log n)。如果面试官追问这个问题能答出这个细节会加分。我还梳理了一个表格做速查算法最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度稳定性冒泡排序O(n)O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定这个表格看起来简单但要完全理解每一行的含义需要把每个算法都手写一遍、推导一遍才能真正记住。尤其是稳定性的问题很多初学者容易混淆为什么归并稳定而堆不稳定归并排序在合并时只有当左半部分的元素大于右半部分时才优先取右等于时取左所以相对顺序不变。堆排序在调整堆的过程中元素会跨越多个位置移动相同元素的相对位置很难保证所以不稳定。4.4 今日推荐的辅助工具和资源今天在推演堆排序时我用了算法可视化网站把随机数组的调整过程一帧一帧看了一遍比自己画图直观很多。个人比较推荐Visualgo和Algorithm Visualizer两者都支持常见排序算法的可视化能调速、能步进对理解算法执行过程帮助非常大。网上搜索时看到很多人问算法流程图和算法设计与分析其实这两个关键词背后代表的是两个层次的学习需求一是知道算法步骤二是理解算法为什么正确。我的建议是刷题之余花点时间看经典的教材比如数据结构与算法领域的几本经典著作把每个算法的正确性证明过一遍。不需要每个证明都严格写出来但至少知道它为什么对、依赖什么性质这能很大程度避免死记硬背。另外知乎和博客平台上有很多人整理了排序算法的对比分析从时间、空间、稳定性、应用场景多维度展开。选择一两篇写得好、有代码演示的存起来当作复习资料来用就够了。5. 写在后面的总结今天整体学下来最大的感受是算法学习不是背代码而是理解每一步为什么这么做。排序算法的各种花样看起来很多但核心就那几种思想——暴力、分治、堆调整。掌握了思想之后哪怕是没见过的新题目也能往这几个方向去靠。我自己踩过最深的坑就是贪心算法一开始总觉得贪心太聪明了不敢用怕局部最优不等于全局最优。后来多做几道题目后发现与其纠结贪心是否适用不如先用贪心想一个方案再用反例去验证它是否正确。跳跃游戏2就是很好的例子如果不去尝试贪心很可能会绕到动态规划里写出一堆不必要的代码。明天打算进入二分查找和KMP算法这两个也都是面试高频考点而且和今天的归并排序有很强的关联——二分查找本身就是不断缩小问题规模的分治思想KMP则是把匹配过程的回溯优化到了极致。到时候应该会有更多值得记录的内容。最后分享一个小技巧算法日记不一定要写得很长但一定要包含当天遇到的问题和当时的思考过程。我回看前两天的日记发现最有价值的恰恰是那些报错信息和debug过程而不是最终通过的代码。记录错误比记录正确更有意义。