很多开发者第一次系统学习算法时都会把目光投向斯坦福大学 Tim Roughgarden 主讲的《Algorithm Specialization》。这套课程的第一部分《Divide and Conquer, Sorting and Searching, Randomized Algorithms》是公认的算法学习基石内容覆盖了从整数乘法到随机化快排的一整套经典内容。本文不是课程字幕的机械搬运也不是简单的听课总结而是一份可以对照学习的中文学习笔记 核心代码实战。我会把课程中最重要的几个模块拆开结合可运行的代码示例、复杂度推导思路和常见误区帮你把“听懂了”变成“会写了”。适合以下读者准备面试但算法基础不牢的开发者。想要系统补一遍算法设计与分析的同学。已经在刷题但对分治、排序、随机化的底层原理理解不深的人。读完这篇文章你会掌握分治策略的核心思想与递归分析方法。归并排序、快速排序的完整实现与复杂度推导。随机化算法为什么能避免最坏情况。逆序对计数、大整数乘法等分治经典问题的代码落地。一套用于判断算法复杂度的主定理Master Method工具。1. 分治策略不只是“拆开再合并”1.1 分治思想到底在讲什么分治Divide and Conquer是 Roughgarden 课程第一部分的第一个大主题。它的核心思路可以概括为三个步骤Divide分解把原问题拆成若干个规模更小的子问题。Conquer解决递归求解这些子问题直到子问题小到可以直接求解。Combine合并把子问题的解合并成原问题的解。这个思路看起来很简单但实际落地时有两个关键难点子问题怎么划分才合理直接影响复杂度。合并步骤往往是整个算法的性能瓶颈也是最容易写错的地方。举个例子线性查找一个数组中的最大值复杂度是 O(n)它没有分治而归并排序每次把数组从中间切开排好两个子数组后再合并复杂度是 O(n log n)这就是分治。1.2 为什么分治能提升效率分治之所以高效是因为它把问题规模降到了 log 级别。对规模为 n 的问题如果每次能拆成两个规模为 n/2 的子问题那么递归树的层数大约就是 log₂n每层的合并代价如果是 O(n)总复杂度就是 O(n log n)。课程里使用了一个非常直观的例子Karatsuba 乘法。普通整数乘法的复杂度是 O(n²)而 Karatsuba 通过减少乘法次数将复杂度降到了 O(n^1.585)。这个例子在面试中不常考但是对于理解“减少子问题数量比减少合并成本更关键”这一点非常有帮助。1.3 递归分析的必要工具递归树在课程的第一部分Roughgarden 反复用递归树来分析分治算法的复杂度。递归树的基本画法是每个节点代表一次递归调用。根节点是原问题规模 n。下一层是两个或更多个子问题。每层节点的总工作量加在一起就是从根到叶子每一层的成本。以归并排序为例第一层对规模 n 的数组做一次合并代价 O(n)。第二层两个规模 n/2 的合并总代价还是 O(n)。第三层四个规模 n/4 的合并总代价仍然是 O(n)。一直到叶子一共 log₂n 层。所以总复杂度是每层代价 O(n) × 层数 log₂n O(n log n)。这个分析套路是整门课贯彻始终的方法后面要学的随机化快排、Strassen 矩阵乘法都可以用它来分析。2. 归并排序最经典的分治案例2.1 算法思路归并排序Merge Sort是课程中第一个完整实现的分治算法。核心思路是把数组从中间拆成左半和右半。递归对左半排序。递归对右半排序。合并两个有序半边得到完整的有序数组。合并步骤非常关键维护两个指针分别指向左半和右半的起始位置每次选择较小的元素放入结果数组然后移动对应指针直到一方耗尽把剩余元素全部拷入。2.2 Python 实现与逐行解释下面是一个可以直接运行的 Python 实现。def merge_sort(arr): 归并排序实现 :param arr: 待排序数组 :return: 升序排列的新数组 n len(arr) # 递归终止条件当数组长度小于等于 1 时天然有序 if n 1: return arr # 1. Divide找到中间位置 mid n // 2 left arr[:mid] right arr[mid:] # 2. Conquer递归排序左右两半 left_sorted merge_sort(left) right_sorted merge_sort(right) # 3. Combine合并两个有序数组 return merge(left_sorted, right_sorted) def merge(left, right): 合并两个有序数组 result [] i j 0 # 比较两个数组当前元素较小的先放入结果 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 # 如果左半还有剩余直接追加 while i len(left): result.append(left[i]) i 1 # 如果右半还有剩余直接追加 while j len(right): result.append(right[j]) j 1 return result if __name__ __main__: test [38, 27, 43, 3, 9, 82, 10] print(排序前:, test) sorted_arr merge_sort(test) print(排序后:, sorted_arr)运行结果排序前: [38, 27, 43, 3, 9, 82, 10] 排序后: [3, 9, 10, 27, 38, 43, 82]注意merge_sort返回的是新数组没有修改原数组。如果希望原地排序就需要传入左右边界下标用辅助数组完成合并。2.3 归并排序的重要性质稳定性当左半元素右半元素时优先取左半因此相同元素的相对顺序不变归并排序是稳定排序。空间复杂度需要额外的 O(n) 空间这是它的主要劣势。时间复杂度始终是 O(n log n)不管输入已经有序还是逆序。3. 逆序对计数分治思想的第一个实战应用3.1 问题定义给定一个数组a如果i j且a[i] a[j]则称(i, j)是一个逆序对。逆序对的数量可以反映数组的“无序程度”。在课程里这个问题被用来演示如何利用归并排序的合并过程以 O(n log n) 的时间复杂度统计逆序对而不是用 O(n²) 的暴力枚举。3.2 核心思想在对左右两个有序子数组合并时当左半当前元素left[i]小于等于右半当前元素right[j]不产生逆序对。当右半当前元素right[j]小于左半当前元素left[i]说明左半从i开始到末尾的所有元素都大于right[j]这些元素都构成逆序对。所以只需要在合并时增加一条计数器逻辑即可。3.3 完整代码def count_inversions(arr): 统计数组中的逆序对数量 :param arr: 待统计数组 :return: (排序后的数组, 逆序对数量) n len(arr) if n 1: return arr, 0 mid n // 2 left, inv_left count_inversions(arr[:mid]) right, inv_right count_inversions(arr[mid:]) merged, inv_cross merge_and_count(left, right) total inv_left inv_right inv_cross return merged, total def merge_and_count(left, right): 合并两个有序数组并统计交叉逆序对数量 result [] i j 0 count 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: # 左半 i 之后的元素都大于 right[j] count len(left) - i result.append(right[j]) j 1 while i len(left): result.append(left[i]) i 1 while j len(right): result.append(right[j]) j 1 return result, count if __name__ __main__: arr [5, 4, 3, 2, 1] _, inv_count count_inversions(arr) print(数组:, arr) print(逆序对数量:, inv_count)运行结果数组: [5, 4, 3, 2, 1] 逆序对数量: 10一个完全逆序的 5 元素数组逆序对数量是4 3 2 1 10符合预期。这里最大的思维跳跃在于合并两个有序数组时能一次性统计出跨越左右两半的所有逆序对。如果你能独立写出这段逻辑说明对分治的理解已经到位了。4. 快速排序与随机化4.1 从固定主元到随机主元快速排序Quick Sort是很多语言标准库的底层排序算法之一。它的基本思路是选择一个主元pivot。把数组分成小于主元、等于主元、大于主元三部分实际实现常用两部分。递归对左右两部分排序。如果每次都选择第一个元素作为主元对于已经有序的输入复杂度会退化为 O(n²)。课程的解决方案是引入随机化随机选择一个元素作为主元。随机化的价值在于它让最坏情况的概率变得极低。不管输入如何恶意构造算法的时间复杂度在期望意义上都是 O(n log n)。4.2 两种经典分区方法Roughgarden 在课程中重点讲了Lomuto 分区和Hoare 分区。Lomuto 分区实现简单适合教学和演示import random def quicksort_lomuto(arr, low, high): 快速排序Lomuto 分区 随机主元 :param arr: 待排序数组原地修改 :param low: 起始下标 :param high: 结束下标 if low high: return # 随机选择主元并交换到末尾 random_index random.randint(low, high) arr[random_index], arr[high] arr[high], arr[random_index] pivot arr[high] i low - 1 # i 指向小于主元区间的末尾 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] # 把主元放到正确位置 arr[i 1], arr[high] arr[high], arr[i 1] pivot_pos i 1 # 递归排序左右两侧 quicksort_lomuto(arr, low, pivot_pos - 1) quicksort_lomuto(arr, pivot_pos 1, high) if __name__ __main__: test [3, 6, 8, 10, 1, 2, 1] print(排序前:, test) quicksort_lomuto(test, 0, len(test) - 1) print(排序后:, test)Hoare 分区性能更好但实现时指针移动的边界条件容易写错。核心逻辑是从两端同时扫描左指针找大于等于主元的元素右指针找小于等于主元的元素然后交换直到两个指针相遇。def quicksort_hoare(arr, low, high): 快速排序Hoare 分区 随机主元 if low high: return random_index random.randint(low, high) arr[random_index], arr[low] arr[low], arr[random_index] pivot arr[low] left low - 1 right high 1 while True: left 1 while arr[left] pivot: left 1 right - 1 while arr[right] pivot: right - 1 if left right: break arr[left], arr[right] arr[right], arr[left] # 此时 right 是分区点递归排序两段 quicksort_hoare(arr, low, right) quicksort_hoare(arr, right 1, high) if __name__ __main__: test [10, 7, 8, 9, 1, 5] print(排序前:, test) quicksort_hoare(test, 0, len(test) - 1) print(排序后:, test)4.3 为什么随机化能起作用在快排中如果主元恰好是当前区间的最小值或最大值那么划分极不平衡一侧为空另一侧是 n-1 个元素复杂度退化为 O(n²)。随机化之后虽然理论上仍可能出现这种最坏情况但概率极低。更精确地说随机化快排的期望时间复杂度是 O(n log n)。期望这个词的意思是在所有可能的随机选择下时间复杂度的平均值是 O(n log n)。Roughgarden 在课程中用概率分析证明了这一点核心是定义一个“比较指示器”变量计算任意两个元素被互相比较的概率再通过期望的线性性质求和。这个证明思路在面试中遇到“为什么随机化快排期望复杂度是 O(n log n)”时可以直接复述。5. 主定理快速判断分治复杂度5.1 主定理内容课程在讲解完多个分治算法的分析后总结了主定理Master Theorem。当递归式形如T(n) a * T(n/b) O(n^d)其中a 是子问题个数。b 是子问题规模缩小的比例。d 是合并阶段的指数。比较d与log_b(a)的大小如果log_b(a) d则 T(n) O(n^(log_b(a)))。如果log_b(a) d则 T(n) O(n^d log n)。如果log_b(a) d则 T(n) O(n^d)。5.2 用主定理分析经典算法算法abdlog_b(a)复杂度归并排序2211O(n log n)二分查找1200O(log n)Karatsuba321log₂3 ≈ 1.585O(n^1.585)Strassen722log₂7 ≈ 2.807O(n^2.807)主定理的价值在于不需要花时间画递归树可以直接套公式得到复杂度结果。但前提是递归式确实满足主定理的适用条件如果合并成本不是 n^d 这种幂函数形式就不能硬套。5.3 常见误解一个容易混淆的点是主定理的三条规则为什么是这样比较。直观解释是如果 log_b(a) d说明递归树的叶子节点数量增长比每层合并成本快总成本主要由叶子层决定。如果 log_b(a) d每一层的成本都差不多总成本是层数和单层成本的乘积。如果 log_b(a) d根节点的合并成本增长过快总成本由第一层的合并成本决定。面试时如果能用这个直觉讲清楚比单纯背诵公式更有说服力。6. 从课程到实战一个综合示例6.1 题目描述我们来做一道结合了分治、排序、随机化的综合题给定一个长度为 n 的整数数组求出第 k 小的元素k 从 1 开始计数。这个问题用快速排序的随机化分区思路可以做到期望 O(n) 时间复杂度这就是著名的随机化选择算法Randomized Selection也叫做 Quickselect是《Divide and Conquer, Sorting and Searching, Randomized Algorithms》课程的重点内容之一。6.2 算法思路随机选择一个主元。用 Lomuto 分区把数组分成小于主元和大于主元两部分。如果主元的下标正好等于 k-1直接返回主元。如果 k-1 小于主元的下标递归在左半部分查找。否则递归在右半部分查找。注意这里不需要对数组完全排序因此避免了 O(n log n) 的成本。6.3 完整代码import random def quickselect(arr, low, high, k): 随机化选择算法找出第 k 小的元素 :param arr: 数组会被修改 :param low: 起始下标 :param high: 结束下标 :param k: 第 k 小从 1 开始 :return: 第 k 小的元素值 if low high: return arr[low] # 随机选主元并交换到末尾 random_index random.randint(low, high) arr[random_index], arr[high] arr[high], arr[random_index] pivot arr[high] i low - 1 # Lomuto 分区 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] # 主元放到正确位置 arr[i 1], arr[high] arr[high], arr[i 1] pivot_pos i 1 # 判断 k 在哪个区间 if pivot_pos k - 1: return arr[pivot_pos] elif pivot_pos k - 1: return quickselect(arr, low, pivot_pos - 1, k) else: return quickselect(arr, pivot_pos 1, high, k) if __name__ __main__: data [7, 10, 4, 3, 20, 15] k 3 print(数组:, data) print(f第 {k} 小的元素:, quickselect(data, 0, len(data) - 1, k))运行结果因为随机选主元元素位置可能有变化但结果稳定数组: [7, 10, 4, 3, 20, 15] 第 3 小的元素: 7排序后的数组是[3, 4, 7, 10, 15, 20]第 3 小确实是 7。这个算法本质上是“只递归处理包含目标的一侧”所以期望复杂度是 O(n)。在数据量大、只需要找中位数或 Top-K 元素的场景下性能远优于先整体排序再取下标。7. 常见问题与排查思路7.1 归并排序合并时丢失元素问题现象常见原因解决思路排序结果长度小于原数组合并时只写了两个 while 之一或者把等于情况遗漏两个 while 都要保留确保左半和右半所有剩余元素都被追加相同元素顺序变了合并时优先取了右半元素条件写成left[i] right[j]而不是原数组没有被修改返回了新数组调用方没有重新赋值原地修改时要传入low和high用辅助数组回填7.2 快速排序栈溢出快排在极端输入下递归深度接近 nJava/Python 默认递归深度有限可能造成栈溢出。如果使用随机主元概率极低但不能保证 100%。在生产环境可以引入“三数取中”策略降低退化概率。对递归深度有严格要求时可以考虑用迭代版本或改用堆排序。7.3 主定理套用失败有时递归式是T(n) 2*T(n/2) n^2看起来符合主定理但实际合并过程中可能有嵌套循环。主定理只适用于合并成本可以表示为 O(n^d) 的情形如果合并步骤本身包含递归需要重新列式。排查建议先画出递归树确认每层成本是否真的符合a * (n/b)^d的形态再套主定理。7.4 随机化算法结果不确定随机化选择算法每次运行可能修改数组顺序但返回值一定正确。如果读者测试时发现主元位置不同这是正常现象。如果要求不修改原数组可以复制一份到新数组再调用。8. 学习建议与最佳实践8.1 跟着课程做题时注意什么Roughgarden 的课程配有编程作业比如实现基于分治的整数乘法、统计逆序对、实现快排并统计比较次数。建议不要直接看答案而是先自己实现再用随机小数组和暴力法对照验证。一个实用的验证方法是写一个简单的暴力函数随机生成数据后反复对比结果能快速暴露边界条件问题。import random def brute_force_inversions(arr): 暴力统计逆序对用于验证分治实现 count 0 for i in range(len(arr)): for j in range(i 1, len(arr)): if arr[i] arr[j]: count 1 return count def test(): for _ in range(1000): arr [random.randint(-100, 100) for _ in range(random.randint(1, 100))] _, count1 count_inversions(arr) count2 brute_force_inversions(arr) if count1 ! count2: print(验证失败:, arr) return print(全部通过) if __name__ __main__: test()8.2 三个最适合深入的方向学完第一部分后可以按兴趣选择以下方向随机化算法的概率分析研究“为什么期望复杂度是 O(n log n)”的数学推导这对面试讲原理很有帮助。分治法在其他数据结构的应用比如线段树、分治 FFT 等。排序算法的稳定性与工程实现研究 Java 的DualPivotQuicksort和 Python 的Timsort为什么混合使用多种排序策略。8.3 工程中的实用建议不需要重复造轮子理解原理后优先使用语言内置排序。如果自己实现排序务必处理空数组、单元素数组、全相等数组三种边界。随机化算法中随机种子可以固定方便测试复现。生产环境涉及大数据排序时关注空间复杂度和是否稳定而不只是时间复杂度。9. 小结与下一步计划斯坦福算法专项的第一部分表面上是“分治、排序、随机化”三个主题实际上是在训练你两件事看到一个问题能不能想到用分治来降低复杂度。对递归式能快速判断复杂度并用概率工具分析不确定性。归并排序是理解分治的钥匙逆序对计数是分治合并阶段的经典变体快速排序则是随机化思想最好的载体。从这些内容延伸出去后续课程还会讲到图算法、贪心、最短路径和动态规划。如果你把第一部分的证明思路和编码实战都弄扎实后面的学习会顺畅很多。最后强调一点算法学习不是看会的是写会的。建议把文中的代码手动敲一遍再用随机数据测试边界情况遇到疑问可以再回头看这节课对应的原版视频。如果这篇文章对你有帮助建议收藏备用后续我还会继续整理斯坦福算法专项其他部分的实战笔记。
