Personal Field Archive / Received 2026.09.22
分治与快速排序｜LeetCode 第一轮复盘
从问题切分、子问题收敛与结果合并出发，复盘快速排序、Quickselect 和最大子数组的统一分治结构。
章节状态：已完成 4/4。目前 LC 912、169、215、53、53 已完成并复盘。当前主要训练目标不是记住 Quick Sort、Quickselect 或某个递归模板，而是理解 Divide and Conquer 中“如何切分问题、为什么子问题会缩小、Combine 阶段如何恢复整体答案”，并能区分 partition strategy、pivot selection、time complexity 与 space complexity。
一、第 4 组题目清单
| 顺序 | LeetCode | 难度 | 题目 | 核心训练 | 当前状态 |
|---|---|---|---|---|---|
| 20 | 912 | 中等 | Sort an Array | 独立实现快速排序、in-place partition、随机 pivot、three-way partition | 已复盘 |
| 21 | 169 | 简单 | Majority Element | 分治候选、Combine 阶段、局部 majority 与整体 majority | 已复盘 |
| 22 | 215 | 中等 | Kth Largest Element in an Array | 从 Quick Sort 迁移到 Quickselect、只递归目标所在一侧 | 已复盘 |
| 23 | 53 | 中等 | Maximum Subarray | 分治三种位置关系、跨中点 Combine、递归正确性 | 已复盘 |
二、分治的统一心智模型
Divide and Conquer 的核心不是“出现递归”，而是：
原问题
↓
Divide：拆成更小子问题
↓
Conquer：递归解决
↓
Combine：恢复整体答案检查重点：
- 子问题是否严格缩小；
- Base Case 是否能终止；
- 子问题是否与原问题同构；
- Combine 是否必要；
- 如果没有显式 Combine，是否因为结果已经原地形成。
三、LC 912. Sort an Array
1. 最初方案：三个数组实现 Quick Sort
最开始：
smaller = []
equal = []
greater = []
pivot = nums[0]
for n in nums:
if n == pivot:
equal.append(n)
elif n < pivot:
smaller.append(n)
else:
greater.append(n)
left_sorted = self.sortArray(smaller)
right_sorted = self.sortArray(greater)
return left_sorted + equal + right_sorted结构：
< pivot | == pivot | > pivot
↓ ↓
递归排序 递归排序这是标准的 Divide / Conquer / Combine。
2. 第一个错误：smaller = equal = greater = []
一开始写成：
smaller = equal = greater = []这不是创建三个 list，而是让三个变量引用同一个 mutable list。
所以任何：
append(...)都会修改同一个对象。
这会破坏递归最基本条件：
recursive call 必须处理严格更小的子问题。
修正为：
smaller = []
equal = []
greater = []3. 第二版：逻辑正确，但 Memory Limit Exceeded
三个 list 独立以后，算法正确，但每层递归都会创建：
smaller
equal
greater返回时：
left_sorted + equal + right_sorted还会继续创建新的 list。
因此会产生大量 temporary lists；如果 partition 又极度不平衡，递归栈和中间数组会一起放大内存压力。
4. 第二次优化：In-Place Partition
于是改成不创建子数组，而是在原数组中通过 swap partition。
def partition(left, right):
pivot = nums[right]
boundary = left
for i in range(left, right):
if nums[i] < pivot:
nums[boundary], nums[i] = nums[i], nums[boundary]
boundary += 1
nums[boundary], nums[right] = nums[right], nums[boundary]
return boundary这里：
i
→ 扫描指针
boundary
→ 下一个 < pivot 的元素应该放的位置维护：
[left ... boundary-1] < pivot
[boundary ... i-1] >= pivot
[i ... right-1] unknown
[right] pivot然后递归：
quicksort(left, pivot_index - 1)
quicksort(pivot_index + 1, right)因为数组已被原地修改，所以不需要显式 Combine。
5. 新问题：固定 pivot 导致 O(n²)
如果固定：
pivot = nums[right]对于有序数组：
[1,2,3,4,5]会不断产生：
n → n-1 → n-2 → ...于是：
T(n) = T(n-1) + O(n)最终：
O(n²)6. 第三次优化：Random Pivot
改成：
pivot_index = random.randint(left, right)Random Pivot 无法消灭理论 worst case，但能显著降低输入顺序稳定制造坏 partition 的概率，因此 expected time complexity 为：
O(n log n)7. 新问题：大量 duplicate values 仍然 TLE
例如：
[2,2,2,2,2,...]随机选谁都是：
pivot = 2Two-Way Partition 只有：
< pivot | >= pivot所有 == pivot 的元素都会留在同一侧，于是递归仍然：
n → n-1 → n-2 → ...再次退化到：
O(n²)8. 第四次优化：Three-Way Partition
升级为：
< pivot | == pivot | > pivot也就是 Dutch National Flag partition。
维护：
[left ... lt-1] < pivot
[lt ... i-1] == pivot
[i ... gt] unknown
[gt+1 ... right] > pivot核心：
lt = left
i = left
gt = right
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[i], nums[gt] = nums[gt], nums[i]
gt -= 1
else:
i += 1结束后只递归：
quicksort(left, lt - 1)
quicksort(gt + 1, right)中间 == pivot 区域不再进入递归。
9. 912 完整演进
三个新数组
→ Python 引用错误
→ 修正为三个独立 list
→ Memory Limit Exceeded
→ In-Place Partition
→ 固定 pivot 导致 O(n²)
→ Random Pivot
→ duplicates 仍然 TLE
→ Three-Way Partition核心结论：
Random Pivot
→ 解决 pivot selection 风险
Three-Way Partition
→ 解决 duplicate values 风险四、LC 169. Majority Element
1. 第一反应：Hash Map
最初思路：
num → frequency正确写法：
count_map = {}
for num in nums:
if num not in count_map:
count_map[num] = 0
count_map[num] += 1
for num, count in count_map.items():
if count > len(nums) // 2:
return num复杂度：
Time：O(n)
Space：O(n)2. 分治关键性质
如果一个元素是整个数组的 majority，它不一定同时是左右两边的 majority，但它至少必须是其中一边的 majority。
如果它左右两边都不是 majority：
count_left <= L/2
count_right <= R/2那么：
count_total <= (L+R)/2这与 majority 必须严格超过一半矛盾。
因此整个区间的 majority 只可能来自：
left_candidate
或
right_candidate3. Divide / Conquer / Combine
class Solution:
def majorityElement(self, nums: List[int]) -> int:
def majority(left, right):
if left == right:
return nums[left]
mid = (left + right) // 2
left_candidate = majority(left, mid)
right_candidate = majority(mid + 1, right)
if left_candidate == right_candidate:
return left_candidate
left_count = 0
right_count = 0
for i in range(left, right + 1):
if nums[i] == left_candidate:
left_count += 1
elif nums[i] == right_candidate:
right_count += 1
return left_candidate if left_count > right_count else right_candidate
return majority(0, len(nums) - 1)这里：
Divide：
切左右两半
Conquer：
递归得到两个 candidate
Combine：
统计两个 candidate 在当前区间的出现次数复杂度：
T(n) = 2T(n/2) + O(n)
= O(n log n)递归栈：
O(log n)Hash Map 解法时间更优，但 Divide and Conquer 更能训练“局部答案如何组合成整体答案”。
五、LC 215. Kth Largest Element in an Array
1. 第 k 大对应哪个 index
如果升序排列：
[1,2,3,4,5,6]第 k 大对应：
target = len(nums) - k因为目标右边正好有 k-1 个更大的元素。
2. 从 Quick Sort 迁移到 Quickselect
Quick Sort：
partition
→ 左边递归
→ 右边递归Quickselect：
partition
→ 看 target 在哪边
→ 只递归那一边如果：
pivot_index == target直接返回。
如果：
pivot_index < target目标在右边。
否则目标在左边。
3. 完整代码
from typing import List
import random
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
target = len(nums) - k
def partition(left: int, right: int) -> int:
pivot_index = random.randint(left, right)
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
pivot = nums[right]
boundary = left
for i in range(left, right):
if nums[i] < pivot:
nums[boundary], nums[i] = nums[i], nums[boundary]
boundary += 1
nums[boundary], nums[right] = nums[right], nums[boundary]
return boundary
def quickselect(left: int, right: int) -> int:
pivot_index = partition(left, right)
if pivot_index == target:
return nums[pivot_index]
if pivot_index < target:
return quickselect(pivot_index + 1, right)
return quickselect(left, pivot_index - 1)
return quickselect(0, len(nums) - 1)4. 为什么平均 O(n)
Quick Sort：
T(n) = 2T(n/2) + O(n)Quickselect：
T(n) = T(n/2) + O(n)展开：
n + n/2 + n/4 + ...所以平均：
O(n)最坏仍然可能：
O(n²)5. 本题核心
Quickselect 的本质是：
我只关心一个目标位置，因此没必要把整个数组全部排好。
这是从 Quick Sort 到 selection algorithm 的关键迁移。
六、Partition 之后到底得到了什么：从“会切分”到“会使用切分结果”
这一轮 912 和 215 暴露出的共同问题，并不在 Dutch National Flag 的代码本身，而在于：
partition 完成之后，它到底给了我什么信息，以及我要怎么利用这些信息？
Three-Way Partition 完成后，真正得到的不是“数组已经有序”，而是一个结构性保证：
[left ... lt-1 | lt ... gt | gt+1 ... right]
< pivot == pivot > pivot也就是说：
[left, lt-1]
→ 每个元素都 < pivot
→ 但内部不一定有序
[lt, gt]
→ 每个元素都 == pivot
→ 这个区域已经不需要继续处理
[gt+1, right]
→ 每个元素都 > pivot
→ 但内部不一定有序例如：
[3, 1, 4, 2 | 5, 5 | 8, 7, 9, 6]partition 能证明：
3,1,4,2 < 5
8,7,9,6 > 5但它没有证明：
3,1,4,2内部已经有序，也没有证明：
8,7,9,6内部已经有序。
这是因为 partition 比较的核心问题始终只是：
当前元素与 pivot 的关系是什么？而不是：
左侧元素彼此之间是什么顺序？
右侧元素彼此之间是什么顺序？因此，partition 的职责是建立区域之间的关系，而不是完成区域内部的所有工作。
Quick Sort：partition 后还有两个 subproblem
Quick Sort 的目标是：
让整个区间完全有序partition 后：
[ < pivot | == pivot | > pivot ]
↑ ↑ ↑
内部未排序 已完成 内部未排序因此还剩两个没有解决的子问题：
quick_sort(left, lt - 1)
quick_sort(gt + 1, right)这里不需要继续处理 [lt, gt]，因为其中所有元素都等于 pivot。
而左区间和右区间虽然内部还没有排序，但它们之间的相对位置已经永久确定。对于任意左侧元素 L 和右侧元素 R：
L < pivot < R因此一定有：
L < R所以之后只需要分别解决左边内部和右边内部，不需要再让左右两边互相比较。
Quick Sort 的思考方式应该是：
partition
↓
哪些部分已经完成？
哪些部分内部仍然没有完成？
↓
把所有仍未完成的子问题继续递归Quickselect：partition 后只需要一个 subproblem
Quickselect 的目标不同：
不是让整个数组有序
而是找到 target index 上最终应该出现的元素Three-Way Partition 后：
[left ... lt-1 | lt ... gt | gt+1 ... right]
↑
target 在哪里？所以真正应该判断的是：
if target < lt:
return quick_select(left, lt - 1)
elif target <= gt:
return pivot
else:
return quick_select(gt + 1, right)这里不能继续使用最初随机选择 pivot 时的：
pivot_index因为 pivot_index 只表示：
partition 之前 pivot 从哪里被选出来经过 swap 后，原来的 pivot_index 已经没有结构意义。
Three-Way Partition 真正产生的是：
[lt, gt]这个 pivot region。
因此使用 Dutch National Flag 后，思维必须从：
pivot 最初在哪个 index？转换成：
partition 最终建立了哪些区域？
target 落在哪个区域？Quick Sort 与 Quickselect 的统一
两者可以使用完全相同的 Three-Way Partition：
partition
↓
[ < pivot | = pivot | > pivot ]
↓ ↓ ↓
未排序 已确定 未排序
│ │
└──────────┬──────────┘
↓
根据最终目标决定
下一步处理什么如果目标是：
整个数组有序那么：
Quick Sort
→ 左右两个未排序区域都要继续解决如果目标是：
只找到 target那么：
Quickselect
→ target 在哪一个区域，就只继续解决那一个区域
→ 如果 target 落在 == pivot 区域，直接结束因此：
Quick Sort：
T(n) = T(left) + T(right) + O(n)
Quickselect：
T(n) = T(one side) + O(n)这也是为什么二者共享 partition，却有不同的 expected time complexity。
这一轮真正 miss 的点
这一轮的问题可以总结成：
已经能够写出“如何 Divide”，但 partition 完成后，还需要进一步判断“Divide 给了我哪些已经确定的信息，以及为了当前目标还剩哪些 subproblem 必须解决”。
以后写 partition-based algorithm 时，不应该在 while 结束后立刻进入代码，而应该先停下来写出：
1. partition 结束后的 invariant 是什么？
2. 哪些区域已经完成？
3. 哪些区域只是满足某种关系，但内部仍未完成？
4. 当前算法的最终目标是什么？
5. 为了这个目标，我需要继续解决几个 subproblem？对应到当前两题：
912 Quick Sort
→ 左右内部都还未排序
→ recurse 两边
215 Quickselect
→ 只关心 target 所在区域
→ recurse 一边；落在 equal region 则直接返回因此，真正需要建立的习惯不是背：
quick_sort(left, lt - 1)
quick_sort(gt + 1, right)或者：
if target < lt:
...而是每次 partition 后都主动问：
“现在我已经知道了什么？为了最终目标，我还不知道什么？”
七、LC 53. Maximum Subarray
1. 问题本质
题目要求：
在数组中找到一个连续子数组，使它的元素之和最大。例如：
nums = [-2,1,-3,4,-1,2,1,-5,4]最大连续子数组是：
[4,-1,2,1]其和为：
6这里训练的重点不是 Kadane’s Algorithm，而是先用 Divide and Conquer 分析：
一个区间内的 maximum subarray，和中点
mid的位置关系只有三种。
2. Divide：最大子数组只有三种情况
对当前区间：
nums[left ... right]取：
mid = (left + right) // 2最大连续子数组只可能是：
Case 1：完全位于左半边
Case 2：完全位于右半边
Case 3：跨过中点也就是：
left -------- mid | mid+1 -------- right如果最大子数组记作：
nums[i ... j]那么必然满足三种情况之一：
j <= mid
i > mid
i <= mid < j所以这三个 case 是完整且互斥的，不存在第四种位置关系。
3. Conquer：为什么 solve(left, mid) 能得到 left_max
代码：
left_max = solve(left, mid)
right_max = solve(mid + 1, right)这两行本身并不是“直接算出”左右答案，而是：
把同一个 Maximum Subarray 问题交给更小的区间继续解决。
例如：
nums = [4, -1, 2, 1]第一次：
solve(0,3)拆成：
solve(0,1)
solve(2,3)其中：
solve(0,1)仍然不知道答案，所以继续拆：
solve(0,0)
solve(1,1)这时到达 Base Case：
if left == right:
return nums[left]所以：
solve(0,0) -> 4
solve(1,1) -> -1然后 solve(0,1) 在返回阶段比较：
left_max
right_max
cross_max得到：
solve(0,1) -> 4同理：
solve(2,3) -> 3因此最外层才真正获得：
left_max = 4
right_max = 3递归结构：
solve(0,3)
/ \
solve(0,1) solve(2,3)
/ \ / \
solve(0,0) solve(1,1) solve(2,2) solve(3,3)
↓ ↓ ↓ ↓
4 -1 2 1
\ / \ /
\ / \ /
solve(0,1) solve(2,3)
↓ ↓
4 3因此必须区分：
调用阶段：
不断把问题缩小
返回阶段：
利用更小问题的答案，逐层恢复更大问题的答案Base Case 只负责回答最小问题，并不单独负责整个算法。
4. Base Case
最简单的区间是：
left == right此时区间只有一个元素：
[x]它的 maximum subarray 只能是自己。
所以：
if left == right:
return nums[left]5. Combine：跨中点最大子数组怎么求
如果 maximum subarray 跨过 mid，它必须满足：
左半部分以 mid 结尾
右半部分以 mid+1 开始因此分别计算：
以 mid 结尾的最大 suffix sum
以 mid+1 开始的最大 prefix sum例如：
[4, -1 | 2, 1]左边从 mid 向左扫：
-1 -> -1
4 + -1 -> 3得到：
best_left = 3右边从 mid+1 向右扫：
2 -> 2
2 + 1 -> 3得到：
best_right = 3所以：
cross_max = 3 + 3 = 66. 完整 Divide and Conquer 代码
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def solve(left, right):
if left == right:
return nums[left]
mid = (left + right) // 2
left_max = solve(left, mid)
right_max = solve(mid + 1, right)
current_sum = 0
best_left = float("-inf")
for i in range(mid, left - 1, -1):
current_sum += nums[i]
best_left = max(best_left, current_sum)
current_sum = 0
best_right = float("-inf")
for i in range(mid + 1, right + 1):
current_sum += nums[i]
best_right = max(best_right, current_sum)
cross_max = best_left + best_right
return max(left_max, right_max, cross_max)
return solve(0, len(nums) - 1)7. 为什么这个递归是正确的
需要维护的语义是：
solve(left, right)返回：
nums[left:right+1] 内的 maximum subarray sum证明结构是递归正确性 / mathematical induction。
Base Case：
left == right只有一个元素，答案显然是：
nums[left]递归步骤中，假设更小区间：
solve(left, mid)
solve(mid+1, right)都能正确返回各自区间内的 maximum subarray。
那么当前区间的 maximum subarray 只有：
完全在左边
完全在右边
跨过中点分别由：
left_max
right_max
cross_max覆盖。
因此：
max(left_max, right_max, cross_max)一定是当前区间的正确答案。
8. 复杂度
每一层递归中，为了计算 cross_max，当前层所有区间加起来总共扫描约：
O(n)递归每次把问题规模减半：
n
n/2
n/4
...
1递归深度：
O(log n)所以：
Time：O(n log n)
Space：O(log n)其中 Space 主要来自 recursion call stack。
9. 本题的核心训练
LC 53 在 Divide and Conquer 中最重要的不是记住代码，而是理解：
Divide：
按中点切成左右两半
Conquer：
递归求左右区间的 maximum subarray
Combine：
单独计算跨中点的 maximum subarray以及一个关键认知：
left_max = solve(left, mid)并不是“这一行直接算出了 left_max”，而是进入更小的同构问题，直到 Base Case 后，再通过递归返回阶段逐层恢复答案。
这与前面 169 的 Divide / Conquer / Combine 很相似，但 53 的 Combine 更明显，因为必须额外处理“跨越分界线”的第三种情况。
八、当前暴露出的共性问题
1. 需要持续检查递归规模
不要只看 Base Case，还要看：
n → n-1还是：
n → n/2这直接决定复杂度。
2. Partition strategy 会直接影响复杂度
Two-Way：
< pivot | >= pivot
Three-Way：
< pivot | == pivot | > pivot大量重复值时差异非常大。
3. Pivot Selection 与 Partition Strategy 是两个问题
Random Pivot 与 Three-Way Partition 不能混为同一个优化。
4. Divide 后不一定要解决所有子问题
Quick Sort 递归两边；Quickselect 只递归目标一边。
5. Combine 在不同题里不同
912：in-place，Combine 隐式完成。
169：必须比较左右 candidate。
215：只保留一个子问题，因此无需显式 Combine。
九、统一检查清单
- 当前问题如何 Divide？
- 每个子问题是否严格缩小？
- Base Case 是否正确？
- 需要递归一个分支还是多个分支？
- Combine 是否必要？
- partition invariant 是什么？
- pivot 是否已处于最终位置？
- pivot selection 是否可能被输入结构击穿？
- duplicate values 如何影响 partition？
- 当前递归规模更接近
n-1还是n/2？ - 是否分别分析 Time 与 Space？
- 是否创建了大量 temporary arrays？
- 是否可以改成 index range？
- 如果只关心一个目标位置，是否还需要解决全部子问题？
- 局部答案为什么足以构成整体答案？
十、延迟重做安排
3～7 天后从空白重做：
912、169、215完成标准不仅是通过测试，还应该能够解释：
- 912 的每次优化分别解决什么；
- Two-Way / Three-Way Partition 的 invariant；
- Random Pivot 与 Three-Way Partition 的区别；
- 169 的 majority 性质证明；
- 169 的 Combine 为什么只需要两个 candidate；
- 215 为什么不需要完整排序；
- Quickselect 为什么只递归一边；
- Quick Sort 与 Quickselect 的递归式为什么分别得到 expected
O(n log n)与 expectedO(n)； - 53 为什么必须考虑 left / right / cross 三种情况；
solve(left, mid)为什么能在递归返回阶段得到左半区间的正确答案；- 53 的 Divide and Conquer 为什么是
O(n log n)。