之前整理斯坦福算法专项课时，很多同学都会把关注点放在课程的口音、字幕和作业上，但实际上真正值得反复消化的，是“分治、排序、随机化”这条主线。Roughgarden 老师在课程里把这些基础算法讲得非常透，尤其是随机化视角下的快排与顺序统计，几乎重构了我对“平均复杂度”的理解。本文围绕这门课的核心内容，把分治范式、归并排序、快速排序、随机化快速选择串成一条可落地的学习链，并提供完整的 Python 代码示例、复杂度推导和排错经验。无论你是刚刷完数据结构想进阶算法，还是准备面试但总觉得“排序都会、分析不会”，这份笔记都能帮你把零散的知识点连成体系。
1. 背景与核心概念
1.1 为什么算法学习要先啃分治、排序、随机化
算法体系庞大，但大部分高阶内容，比如图算法、动态规划、字符串匹配，底层都在反复使用两个基本能力：把一个复杂问题拆成独立子问题的“分治能力”，以及对数据进行有效组织的“排序能力”。斯坦福算法专项课把分治、排序、随机化放在第一门课，不是因为它简单，而是因为它们是分析复杂度的最佳训练场。
举个很直观的例子：你学归并排序，表面上只是在学会一种排序方法，但实际上你同时学会了递归树、主定理（Master Theorem）、以及如何分析递推方程。你学随机化快速排序，表面上只是在给快排加一个随机扰动，但实际上你开始理解“期望复杂度”和“最坏复杂度”的区别。这种分析能力一旦建立，后面学图算法、学随机算法、学近似算法都会顺畅很多。
随机化算法在工程里也随处可见。比如快速排序和快速选择，在标准库和数据库排序中广泛使用；再比如哈希表中随机化处理恶意输入、在线算法中的随机采样、分布式系统中的随机分区，都依赖“随机化”这个工具。因此，这一门课程其实是在为后续所有算法章节打下地基。
1.2 三个核心概念的边界
分治是一种自顶向下的问题拆解策略，核心是三步：分解（Divide）、解决（Conquer）、合并（Combine）。它的关键是子问题要相互独立，并且规模不断缩小，直到可以直接解决。
排序是将一组元素按某种次序排列的过程。算法领域讨论的排序通常指“比较排序”，即基于两个元素之间的比较来确定相对顺序。比较排序的理论下界是 O(n log n)，归并排序和堆排序都达到了这个下界，而快速排序虽然最坏情况是 O(n²)，但随机化后期望性能非常优秀。
随机化并不是一种独立的数据结构，而是一种算法设计思路。它允许算法在运行过程中使用随机数做出决策。根据分析方式，可以分为 Las Vegas 算法（结果一定正确，运行时间随机）和 Monte Carlo 算法（运行时间确定，结果可能有小概率错误）。随机化快速排序属于 Las Vegas 类型：无论随机数如何产生，排序结果一定正确，但运行时间是一个随机变量。
这三个概念在课程中并不是孤立出现的。分治提供了分析框架，排序是分治的天然应用，随机化则用来解决确定性算法中最坏情况的问题。三者结合，构成了算法设计的基础工具箱。
1.3 Roughgarden 课程的讲解视角
Roughgarden 在课程中特别强调“用最少的数学做最清晰的复杂度分析”。他不会一上来就抛主定理，而是先通过归并排序的递归树让你直观看到 log n 层，再总结出更通用的主定理。这种讲法非常适合自学。
另一个特点是课程极度注重“算法为什么设计成这个样子”。比如讲快速排序时，他会专门分析为什么随机化 pivot 能消除最坏输入，而不是简单告诉你“随机化可以平均一下”。这堂课对学生最大的帮助，是把“能写代码”提升到“能证明和评估代码”的层次。
2. 环境准备与工具
2.1 Python 环境版本
本文所有代码均使用 Python 3.9+ 语法，主要在 Jupyter Notebook 和命令行脚本中运行。算法实现本身不依赖任何第三方库，只需要标准库random、time和sys。如果你使用的是旧版本 Python，请至少保证 Python 3.6 以上，因为类型注解和 f-string 在旧版本中的体验会差很多。
python --version建议在项目目录下创建一个虚拟环境：
mkdir algorithm-notes cd algorithm-notes python -m venv venv source venv/bin/activate # Windows 下为 venv\Scripts\activate2.2 项目结构
为了方便测试不同算法，建议采用这样的目录结构：
algorithm-notes/ ├── sort_algorithms/ │ ├── __init__.py │ ├── merge_sort.py │ ├── quick_sort.py │ └── quick_select.py ├── tests/ │ ├── test_sort.py │ └── test_select.py └── main.py这样每个算法独立成一个文件，测试文件通过 unittest 或 pytest 管理。本文为了演示完整可运行代码，会把所有函数写在一个main.py里，但你实际工程中最好拆开。
2.3 测试工具
推荐使用 Python 标准库的unittest或者更简洁的pytest。本文示例直接写if __name__ == "__main__"的测试逻辑，方便你在命令行运行。如果追求更专业的验证，可以安装 pytest：
pip install pytest3. 分治算法核心原理
3.1 分治范式拆解
分治算法的核心思想可以用一个递归函数抽象出来：
- 如果问题规模足够小，直接解决。
- 否则把原问题分解成若干个规模较小的独立子问题。
- 递归求解每个子问题。
- 把子问题的解合并得到原问题的解。
这个过程在代码上体现为一个递归函数。判断是否“足够小”的条件，叫作“基本情况”或“递归基”；合并过程是整个算法的难点，因为分解和递归过程往往是模板化的，但合并过程决定了算法的效率。
比如归并排序的合并过程需要将两个有序数组合并为一个有序数组，这个操作是线性时间的。而快速排序的合并过程几乎不需要额外工作，因为它选择 pivot 并把数组分成两大部分后，左部分永远小于右部分，递归完成后自然整体有序。这就是为什么快速排序的常数更小。
分治复杂度分析的通用方法是写出递推方程。如果一个问题规模为 n，分解成 a 个子问题，每个子问题规模为 n/b，合并成本为 O(n^d)，那么递推方程是：
T(n) = a·T(n/b) + O(n^d)
根据主定理，结果分为三种情况：
- 如果 a < b^d，则 T(n) = O(n^d)
- 如果 a = b^d，则 T(n) = O(n^d log n)
- 如果 a > b^d，则 T(n) = O(n^(log_b a))
归并排序中，a = 2，b = 2，d = 1，此时 a = b^d，所以复杂度为 O(n log n)。这个分析过程看似简单，却是理解很多复杂算法的基础。
3.2 归并排序：分治的典型代表
归并排序是分治算法最标准的例子。它先把数组从中间切分为左右两半，递归排序两半，最后合并两个有序数组。合并过程需要额外的辅助数组，因此空间复杂度是 O(n)，这一点在工程中需要注意。
下面是一个最基础的归并排序实现：
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i = j = 0 result = [] 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 result.extend(left[i:]) result.extend(right[j:]) return result这个实现非常直观，但每次切片arr[:mid]都会产生新的列表，导致空间复杂度上升。更严谨的做法是传入左右边界，在原数组上使用辅助数组进行合并，这样可以显著减少内存占用。
归并排序的稳定性取决于合并时相同元素的先后顺序。如果left[i] <= right[j]时取左元素，那么相同元素会保持原顺序，所以归并排序是稳定的。这在排序对象是复杂结构时非常重要。
3.3 递归树与复杂度分析
为了直观理解 O(n log n) 是怎么来的，可以画递归树。每一层递归中，所有子问题的总规模都是 n，而归并排序的递归深度是 log n，因为每层都把规模减半。每一层合并的总成本是 O(n)，所以总成本是 O(n log n)。
如果不用递归树，也可以用主定理直接得到结果。归并排序的递推方程是：
T(n) = 2T(n/2) + O(n)
带入主定理的第二种情况，得到 T(n) = O(n log n)。
值得注意的是，这里的 O(n log n) 是渐进时间复杂度，实际运行时间还取决于常数因子。归并排序的常数比快速排序大，因为合并过程需要额外的数组赋值。所以在很多编程语言的标准库中，混合排序（比如 Timsort）会比纯归并排序性能更好。
4. 排序算法进阶：快速排序
4.1 快速排序的 partition 思路
快速排序的核心是 partition 操作。给定一个数组和选定的 pivot，partition 把小于等于 pivot 的元素移动到左边，大于 pivot 的元素移动到右边，最后返回 pivot 在数组中的最终位置。
经典的 Lomuto partition 写法如下：
def partition_lomuto(arr, low, high): pivot = arr[high] i = low - 1 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] return i + 1另一种是 Hoare partition，它的交换次数更少，但实现边界更复杂：
def partition_hoare(arr, low, high): pivot = arr[(low + high) // 2] i = low - 1 j = high + 1 while True: i += 1 while arr[i] < pivot: i += 1 j -= 1 while arr[j] > pivot: j -= 1 if i >= j: return j arr[i], arr[j] = arr[j], arr[i]两种 partition 的最终效果都是把数组分成两个区间：一个区间中的元素都小于等于 pivot，另一个区间中的元素都大于等于 pivot。二者的区别在于返回索引的含义不同，直接套用会造成边界错误。
4.2 确定性快速排序的性能陷阱
如果每次选择数组的最后一个元素作为 pivot，那么当输入已经有序或逆序时，partition 会把数组分成 n-1 和 0 两部分，递归深度变成 n，时间复杂度退化为 O(n²)。
例如对[1, 2, 3, 4, 5]进行排序，每次 pivot 都是当前区间最后一个元素，左边区间一次只减少一个元素，递归树的层数变成了 n 层。虽然代码逻辑正确，但实际运行会极慢，甚至导致栈溢出。
这就是确定性快速排序的痛点：最坏情况不是理论上存在，而是非常容易触发。很多工程场景中，输入数据可能恰好是近乎有序的，使用固定 pivot 的快排性能会急剧恶化。因此，必须在选 pivot 时引入随机性。
4.3 随机化快速排序的思路
随机化快速排序在选择 pivot 时不使用固定位置，而是从当前区间内随机选取一个索引。这样做的效果是：任何固定输入都不再对应固定的递归树，最坏情况发生的概率极低。
基于 Lomuto partition 的随机化快排实现如下：
import random def quick_sort_random(arr, low, high): if low < high: # 随机选 pivot 并与末尾元素交换 rand_idx = random.randint(low, high) arr[rand_idx], arr[high] = arr[high], arr[rand_idx] p = partition_lomuto(arr, low, high) quick_sort_random(arr, low, p - 1) quick_sort_random(arr, p + 1, high)随机化后的期望时间复杂度是 O(n log n)，证明思路基于每个元素被选为 pivot 的概率，计算每种划分比例的期望成本。虽然最坏情况仍然是 O(n²)，但对于任意给定输入，最坏情况的出现概率是指数级小的。
需要明确一个概念：随机化快速排序的“期望时间复杂度”是指随机数产生的期望，而不是对输入分布的期望。这意味着无论输入是什么，只要随机源足够好，算法的平均运行时间都是 O(n log n)。这一点在算法设计中有很重要的意义。
5. 线性时间选择：随机化与顺序统计
5.1 问题定义：找第 k 小元素
顺序统计的问题是：给定一个长度为 n 的数组和一个整数 k，要求找出数组中第 k 小的元素。排序后取第 k 个当然可以，但代价是 O(n log n)。我们希望更快。
如果 k = 1 或 k = n，最小值或最大值只需要 O(n)。但对于一般的 k，需要更复杂的方法。
快速选择算法利用了快速排序的 partition 操作：经过一次 partition 后，pivot 被放到了它的最终位置。如果 pivot 的位置恰好是 k，那么 pivot 就是答案；如果 pivot 的位置大于 k，则在左区间继续搜索；如果小于 k，则在右区间搜索 k 减掉左侧长度后的新索引。
5.2 基于快速选择的期望 O(n) 实现
下面是随机化快速选择的完整实现：
def quick_select(arr, low, high, k): """ 返回 arr 中第 k 小的元素，k 从 0 开始计数 """ if low == high: return arr[low] # 随机选取 pivot rand_idx = random.randint(low, high) arr[rand_idx], arr[high] = arr[high], arr[rand_idx] p = partition_lomuto(arr, low, high) if p == k: return arr[p] elif p > k: return quick_select(arr, low, p - 1, k) else: return quick_select(arr, p + 1, high, k)注意这里 k 是从 0 开始的。如果要找第 3 小的元素，传k = 2。快速选择每次递归只进入一个区间，不像快速排序需要递归两个分支，所以期望复杂度是 O(n)，而不是 O(n log n)。
为什么是 O(n) 而不是 O(n log n)？因为在随机 pivot 情况下，每次 partition 的期望划分比例是一个常数，比如平均每层减小到原来的 3/4 左右。于是总代价是 n + 3n/4 + (3/4)²n + ... = O(n)。这是一个非常漂亮的结果，也是随机化算法威力的集中展示。
5.3 为什么随机化能避免最坏情况
如果快速选择固定使用第一个或最后一个元素作为 pivot，那么输入有序时同样会退化到 O(n²)。而随机化 pivot 后，对于任意输入，每次 partition 的期望效果都接近均匀划分，所以整体期望是线性的。
随机化在这里的真正作用是消除了“对手输入”的威胁。在算法设计竞赛中，测试数据可能是精心构造的；在工程中，输入数据也可能存在某种规律。如果算法是确定性的，那么攻击者完全可以构造最坏输入。而随机化使得最坏输入难以构造，因为算法的行为取决于随机种子。
但这也不是银弹。如果随机数生成器本身可预测，攻击者依然可以反向构造输入。因此在安全敏感的场景下，需要使用加密安全的随机数生成器，而不是默认的伪随机数生成器。这是工程实现中需要特别注意的点。
6. 完整实战：用 Python 实现分治排序与随机化选择
6.1 实现归并排序
为了让归并排序的空间效率更高，我们使用辅助数组和左右边界，避免切片：
def merge_sort_inplace(arr, left=0, right=None): if right is None: right = len(arr) - 1 if left >= right: return mid = (left + right) // 2 merge_sort_inplace(arr, left, mid) merge_sort_inplace(arr, mid + 1, right) # 合并两个有序区间 temp = [] i, j = left, mid + 1 while i <= mid and j <= right: if arr[i] <= arr[j]: temp.append(arr[i]) i += 1 else: temp.append(arr[j]) j += 1 while i <= mid: temp.append(arr[i]) i += 1 while j <= right: temp.append(arr[j]) j += 1 arr[left:right + 1] = temp这种写法比切片版更能体现原数组上的分治操作，也会让你更容易发现边界条件的重要性。
6.2 实现随机化快速排序
我们在前面已经实现了 partition 和 quick_sort_random。现在把它们整合到一个链式调用中：
def quick_sort(arr, low=0, high=None): if high is None: high = len(arr) - 1 if low < high: rand_idx = random.randint(low, high) arr[rand_idx], arr[high] = arr[high], arr[rand_idx] p = partition_lomuto(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p + 1, high)这里random.randint包括上下界，所以不会产生越界问题。如果想在测试中复现结果，可以设置随机种子：
random.seed(42)但注意，设置随机种子后，不同运行之间的结果相同，但这在算法测试中更有用，在真实排序中则没有必要。
6.3 实现随机化快速选择
快速选择可以独立于快速排序实现，也可以复用 partition 函数。为了避免复制代码，我们把 partition 抽取出来供两者使用。下面是完整的选择函数：
def quick_select(arr, k, low=0, high=None): if high is None: high = len(arr) - 1 if low == high: return arr[low] rand_idx = random.randint(low, high) arr[rand_idx], arr[high] = arr[high], arr[rand_idx] p = partition_lomuto(arr, low, high) if p == k: return arr[p] elif p > k: return quick_select(arr, k, low, p - 1) else: return quick_select(arr, k, p + 1, high)注意这个函数会修改原数组。如果你希望不修改原数组，可以先复制一份。但工程上通常允许就地修改以换取效率。
6.4 测试与验证
写一个简单的测试脚本，分别验证三种算法的正确性和基本性能：
import time def test_sort(): for n in [10, 100, 1000, 10000]: arr = list(range(n)) random.shuffle(arr) start = time.time() arr_sorted = merge_sort_inplace(arr.copy()) merge_time = time.time() - start start = time.time() quick_sort(arr.copy()) quick_time = time.time() - start assert arr_sorted == sorted(arr) assert arr.copy() == sorted(arr) print(f"n={n}: merge={merge_time:.5f}s, quick={quick_time:.5f}s") def test_select(): arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] sorted_arr = sorted(arr) for k in range(len(arr)): assert quick_select(arr.copy(), k) == sorted_arr[k] print("quick_select tests passed!") if __name__ == "__main__": random.seed(0) test_sort() test_select()运行结果会显示不同规模下的耗时。注意排序时间受随机种子影响，如果需要稳定对比，可以固定随机种子。
7. 常见问题与排查思路
7.1 递归深度报错
当输入数据规模较大且算法退化时，快速排序的递归深度可能超过 Python 默认递归限制，报错RecursionError: maximum recursion depth exceeded。
可能原因：确定性的快速排序在有序输入下退化到 O(n²)，递归深度达到 n。随机化快速排序虽然概率极低，但遇到特别差的随机序列仍可能发生。
解决思路：
- 改用随机化快速排序，而不是固定 pivot。
- 将递归改成迭代，使用显式栈模拟递归。
- 增大递归限制
sys.setrecursionlimit(1000000)，但治标不治本。 - 在排序超大数组时，优先使用归并排序或 Python 内置的 Timsort。
7.2 partition 边界条件出错
Lomuto partition 的常见错误是循环范围和索引初始值不对。例如for j in range(low, high)漏掉了最后一个元素，或者i的初始值设为了low而不是low - 1，都会导致 partition 结果不正确。
排查方法：打印每次 partition 后的数组和返回索引，用小型数组手动模拟。例如[3, 1, 2]，预期 pivot 在中间，可以逐行检查。
另外，Hoare partition 返回的是j，使用时需要以j为分界点，而不是j + 1。如果直接照搬 Lomuto 的递归区间，会漏掉元素或无限递归。
7.3 随机化结果可复现性
测试时希望每次结果一致，但随机算法的输出可能不同。解决方法是设置种子：
random.seed(123)但要注意，种子设置只在同一个 Python 进程内有效。如果你在测试中多次调用随机函数，种子会影响后续所有随机序列。建议每个测试用例单独设置种子，避免交叉影响。
7.4 复杂度误导
看到一个算法复杂度是 O(n log n)，就认为它一定比 O(n²) 快，这是初学者常见的误区。当 n 很小时，O(n²) 的常数优势可能更大，例如插入排序在小数组上往往比快排快。所以 Python 的 Timsort 会在数据量较小时切换为插入排序。
另一个误区是把随机化快速排序的“期望”理解为“平均输入”。期望是针对随机数而言的，不是对输入分布做平均。简单地说，即使输入是最坏输入，随机算法的期望性能仍然是 O(n log n)，但具体运行时间可能因随机种子不同而变化。
8. 最佳实践与工程建议
8.1 什么时候用哪种排序
在实际项目中，不建议重复造轮子。Python 内置list.sort()和sorted()基于 Timsort，它是归并排序和插入排序的结合，具有很好的稳定性和对部分有序数据的高效处理。大多数场景应该直接使用内置排序。
当你需要自定义对象排序时，用key参数而不是修改比较逻辑，性能会更好。如果必须手写排序算法，那么：
- 数据量小、基本有序：插入排序。
- 数据量中等、对稳定性有要求：归并排序。
- 数据量极大、内存充足：随机化快速排序（注意最坏情况）。
- 外部排序、大数据排序：归并排序思路。
8.2 随机化算法的工程注意
在工程中使用随机化算法，首先需要评估随机数的质量。普通random模块是伪随机数生成器，适用于大多数算法场景，但不适用于加密或安全关键场景。如果算法结果会影响资金、权限等，应改用secrets模块。
其次，随机化算法会使问题变得难以复现。线上问题排查时，如果排序结果异常，需要记录随机种子。可以在生产环境日志中输出种子，以便复现。
最后，随机化算法不总是最优解。如果数据规模固定，可以考虑确定性算法配合好的分流策略。工程上需要权衡随机化的收益和代价。
8.3 性能测试与调优
性能测试需要关注三方面：最坏情况输入、随机输入、接近有序输入。不同的输入分布考验算法的不同能力。
def benchmark(): random.seed(42) n = 100000 arr_random = [random.random() for _ in range(n)] arr_sorted = sorted(arr_random) arr_reversed = sorted(arr_random, reverse=True) for name, arr in [("random", arr_random), ("sorted", arr_sorted), ("reversed", arr_reversed)]: start = time.time() sorted(arr) # 内置排序，作为基准 base_time = time.time() - start start = time.time() quick_sort(arr.copy()) quick_time = time.time() - start print(f"{name}: builtin={base_time:.5f}s, quick_sort={quick_time:.5f}s")调优方向包括：对小区间使用插入排序、三数取中法（在随机化基础上进一步稳定 pivot）、消除尾递归等。但大多数情况下，内置排序已经足够好，不要过度优化。
8.4 学习路线建议
学完分治、排序、随机化之后，可以按以下顺序继续进阶：
- 掌握主定理，并能够对多种分治算法进行复杂度分析。
- 学习堆排序和基于堆的优先队列，为图算法打基础。
- 学习快速选择算法的去随机化版本（Median of Medians），对比随机化和确定性的优劣。
- 进入分治算法经典问题，如逆序对计数、最近点对、Karatsuba 乘法。
- 开始接触随机化进阶内容，如 Miller-Rabin 素性测试、Min-Cut 随机算法。
每一步都建议配合代码实现和复杂度证明，避免只看不练。
如果你正在跟斯坦福算法专项课程，完成这门课后，可以直接把本文的代码和笔记作为第一单元的复盘材料，再进入图算法和贪心策略的学习。分治、排序、随机化不是终点，而是整套算法体系的起跑线。希望这份笔记能帮你把基础打扎实，后面无论是应付面试还是做工程，都会觉得轻松不少。
