2026年秋第5次课

把问题分成两部分之后，为什么可以继续求解？哪些工作必须做，哪些候选可以排除？

上一次课通过合并排序与逆序对，讨论了如何利用两个有序子问题的结果。本课先用快速排序比较另一种排序分治方式，再回到木材加工，深入理解二分答案的判定与边界，最后通过最长公共前缀学习如何为子问题设计足够的返回信息。

本讲义用于串联课堂思路；各题的完整 Python 代码、详细过程与已有动画，可通过对应题目链接阅读。

学习目标

本课需要回答的四个问题

• 分的是什么？ 区分数组元素的划分、候选答案区间的缩小和字符串列表的分组。
• 为什么能分？ 分别说明基准两侧的大小关系、可行性的单调性和公共前缀的合并性质。
• 子问题提供什么？ 区分原地完成排序、返回一次可行性判断和返回一个前缀字符串。
• 工作量怎样计算？ 同时检查子问题数量、规模是否均衡以及每层的扫描成本。

课后应能手工完成一次快速排序划分，写出木材加工的二分更新规则，并根据最长公共前缀的递归树追踪返回结果。

本课路线

顺序	题目与详细题解	本课重点	与已有知识的联系
1	快速排序	先按基准划分，再分别排序	与合并排序比较：关键工作发生在递归之前还是之后
2	木材加工	将最优化问题转为单调的可行性判断	复习二分答案，说明为什么只需保留一侧候选
3	最长公共前缀	分组求前缀，再合并两个摘要	从合并有序数组推广到合并字符串信息

每题按“明确任务 → 定义子问题 → 说明缩小或合并依据 → 跟踪示例 → 核对复杂度”的顺序讲解。木材加工在上次课已经引入，本次重点检查单调性与循环边界，而不是重新逐行抄写代码。

题目串联

一、快速排序：先建立大小关系，再分别求解

题解与 Python 实现：快速排序。复习对照：合并排序。

从合并排序提出新问题

合并排序按位置将数组分成两半，左右分别有序之后，还需要合并，因为左半部分的元素不一定都小于右半部分。

快速排序换一个顺序：先选择基准并重新排列元素，使基准左侧不大于它、右侧大于它，再分别排序两侧。 两侧都排好后，整体已经有序，不再进行合并有序数组的操作。

这里沿用题解中的 Python 原地递归实现：处理闭区间 [low, high]，选择末尾元素 arr[high] 为基准，扫描时把小于等于基准的元素放到左侧。本课的下标与空间分析均针对这一版本。

一次划分到底保证了什么

设基准为 pivot，扫描下标为 j，左侧区域的末尾下标为 i。每次扫描开始前保持以下关系：

• [low, i] 中的元素都小于等于 pivot，初始可以为空。
• [i + 1, j) 中的元素都大于 pivot。
• [j, high) 尚未检查，基准暂存在 high 位置。

遇到 arr[j] <= pivot，先将 i 加1，再把该元素交换到左侧区域；否则只继续扫描。扫描结束后，将基准与 arr[i + 1] 交换，得到返回下标 p = i + 1。

此时成立：

$$\text{左侧元素}\leq arr[p]<\text{右侧元素}.$$

上式表示对两侧所有元素分别成立的大小关系；某一侧也可以为空。一次划分只确定基准的位置与两侧的关系，并不保证两侧内部有序。 有重复值时，基准可以占据有序结果中对应值的一个合法位置。

以课堂示例 [4, 2, 5, 1, 3] 为例，基准为3，下标从0开始：

操作	数组状态	已处理部分的含义
扫描4，大于3	[4, 2, 5, 1, 3]	左侧小值区仍为空
扫描2，交换到左侧	[2, 4, 5, 1, 3]	左侧小值区为 [2]
扫描5，大于3	[2, 4, 5, 1, 3]	4、5都处于大值区
扫描1，交换到左侧	[2, 1, 5, 4, 3]	左侧小值区为 [2, 1]
将基准放入下标2	[2, 1, 3, 4, 5]	返回 p = 2，两侧仍需分别处理

之后递归排序 [0, 1] 和 [3, 4]，得到 [1, 2, 3, 4, 5]。不要再次将 p 包含在子区间中，否则可能无法使递归规模严格减小。

为什么正确，为什么不总是快

长度不超过1的区间天然有序。对于更长区间，划分保存全部元素，并建立基准两侧的大小关系；若左右子调用都正确完成排序，拼在基准两侧的结果自然整体有序。这给出了递归正确性的归纳依据。

设当前区间有 $n$ 个元素，基准左侧有 $k$ 个元素，则：

$$T(n)=T(k)+T(n-k-1)+O(n).$$

划分需要线性扫描，但 $k$ 由数据和基准决定，不保证接近 $n/2$：

• 持续均衡划分： 时间为 $O(n\log n)$，递归栈为 $O(\log n)$。
• 持续极不均衡： 一侧为空，另一侧只有一个元素被排除，时间为 $O(n^2)$，递归栈为 $O(n)$。
• 平均或期望结论要说明条件： 对互异元素的均匀随机排列，固定末尾基准的平均时间为 $O(n\log n)$；随机选基准时，对任意固定的互异元素输入可分析期望时间。当前代码并未随机选择基准。

对于当前的末尾基准与 <= 划分，有序数组和全相等数组都会触发极不均衡划分。仅将基准改为随机选择，仍不能消除这种二路划分在全相等输入上的退化；处理大量重复值可以进一步学习三路划分。

复杂度与实现必须对应

原地划分只需要常数个额外变量，但完整递归算法仍需要调用栈。不能把“原地交换”直接写成总辅助空间 $O(1)$，也不能把快速排序写成最坏时间保证为 $O(n\log n)$ 的排序算法。

衔接木材加工： 快速排序中，基准两侧通常都需要递归求解。什么条件允许我们根据一次判断，直接排除一侧候选？

二、木材加工：从寻找最优值转为判断可行性

详细题解与代码：木材加工。课堂演示：木材加工交互动画。

先区分优化问题与判定问题

给定若干根原木，需要切出至少 $k$ 段等长木材，求最大的正整数段长；不足以切出所需段数时返回0。剩余木材不能拼接，允许多切后只取所需段数，本题忽略锯缝损耗。

“最大的长度是多少”不容易直接回答，可以先回答“长度 $x$ 是否可行”。设原木长度为 $L_1,\ldots,L_n$，则对 $x\geq1$：

$$C(x)=\sum_{i=1}^{n}\left\lfloor\frac{L_i}{x}\right\rfloor, \qquad P(x)=[C(x)\geq k].$$

当 $x$ 增大时，每一项都不增，所以 $C(x)$ 单调不增。可行长度构成从1开始的一段连续整数，也可能一个都没有。目标是找到这段可行区域的最右端。

二分的对象是整数段长组成的候选答案区间，不是原木列表。原木无须排序。

用不变式解释更新方向

沿用题解中的闭区间实现：left = 1、right = max(woods)、answer = 0。循环条件为 left <= right。

每轮开始时，answer 是已经确认的最大可行长度；若存在比它更大的可行长度，这些候选仍在 [left, right] 内。取中点 mid 后：

判定结果	可以确认的事实	更新规则
C(mid) >= k	mid 可行，更优长度只能在其右侧	记录 answer = mid，令 left = mid + 1
C(mid) < k	mid 及更大的长度都不可行	令 right = mid - 1

每轮都严格缩小区间，又不会排除尚未检查的更优可行长度。区间为空时，不再存在比 answer 更大的可行候选，因此返回值最优。0只作为无可行正长度时的返回值，不参与除法判定。

对于 [232, 124, 456]、$k=7$，最终可用相邻长度核对边界：

候选长度	各原木可切段数	总段数	判断
114	2 + 1 + 4	7	可行
115	2 + 1 + 3	6	不可行

结合单调性可知答案为114。这里核对的是最终边界，并不表示二分只检查这两个数。

“恰好够”还不是停止条件

原木 [10]、$k=2$ 时，长度4和5都恰好切出2段。即使在长度4处得到 C(4) == k，仍要继续向右找，最终答案为5。判定函数可能出现平台，不能按等式成立就提前返回。

把判定成本计入总时间

设 $M$ 为最长原木长度。二分有 $O(\log(M+1))$ 轮，每轮最多扫描 $n$ 根原木。采用整数除法等基本运算为常数时间的计数模型，总时间为 $O(n\log(M+1))$；判定与二分循环的辅助空间为 $O(1)$，不包括输入列表。

快速排序划分后要处理两侧不同的元素；木材加工利用单调性排除候选，每轮只保留一个区间，不需要合并左右答案。严格区分“分治求解多个子问题”与“减治保留一个子问题”时，二分答案属于后一种结构。

衔接最长公共前缀： 如果不能通过单调性排除一组输入，就要分别求解两组。子问题是否必须返回全部原始数据？能否只返回足以完成合并的信息？

三、最长公共前缀：为子问题设计足够的返回信息

详细题解与 Python 实现：最长公共前缀。

先说清楚前缀与子问题

给定字符串列表，返回所有字符串从首字符开始共有的最长连续部分。例如 ['flower', 'flow', 'flight'] 的答案为 'fl'。前缀不是任意位置的公共子串：'abc' 与 'xbc' 的公共前缀为空。

沿用题解约定：比较区分大小写；空列表返回 ''，单字符串列表返回该字符串；列表含空字符串时，整体公共前缀为空。

定义 solve(lo, hi) 返回半开区间 [lo, hi) 内所有字符串的最长公共前缀。按列表中点分成左右两组，分别返回 left_prefix 和 right_prefix，再求这两个字符串的最长公共前缀。

分的是字符串列表，不是将每个字符串切成两半。 单字符串是递归边界；合并时从下标0逐字符比较，遇到不同字符或较短字符串结束就停止。

为什么两个前缀就足够

用 $F(S)$ 表示非空字符串组 $S$ 的最长公共前缀，用 $\operatorname{lcp}(u,v)$ 表示两个字符串的最长公共前缀。将当前组分成两个非空组 $S_L$、$S_R$，有：

$$F(S_L\cup S_R)=\operatorname{lcp}\bigl(F(S_L),F(S_R)\bigr).$$

这个等式需要同时说明两个方向：

1. 两组前缀的公共部分，是左组每个字符串与右组每个字符串共有的前缀，所以它是一个合法的整体公共前缀。
2. 整体的任何公共前缀，都必须是两组各自最长公共前缀的前缀，所以不可能比合并结果更长。

因此，每组只返回一个前缀字符串，已经足以计算整体答案。合并排序返回整个有序段，本题返回压缩后的摘要；两者都依赖“子问题返回的内容足以支持当前层”的性质。

沿调用与返回两个方向追踪

按题解代码的半开区间，三个字符串的分组与返回过程为：

solve(0, 3)
├── solve(0, 1) → 'flower'
└── solve(1, 3)
    ├── solve(1, 2) → 'flow'
    └── solve(2, 3) → 'flight'
    合并 'flow' 与 'flight' → 'fl'
整体合并 'flower' 与 'fl' → 'fl'

当前合并	字符比较	停止原因	返回值
'flow' 与 'flight'	f=f、l=l、o≠i	首次字符不同	'fl'
'flower' 与 'fl'	f=f、l=l	较短字符串结束	'fl'

本例有5次 solve 调用、2次合并、5次字符相等比较。调用次数与字符比较次数只是恰好相同，代表不同的工作量。

递归层数与合并成本要分别计算

设字符串个数为 $n$，最长字符串长度为 $\ell$。分组树深度为 $O(\log(n+1))$，但仍要处理所有叶子与内部节点。对 $n\geq1$，有 $n$ 个叶子与 $n-1$ 次合并；每次合并最多扫描、复制 $O(\ell)$ 个字符。

计入节点本身的常数开销，时间上界为 $O(n(\ell+1))$；空列表直接返回。不能仅凭树高写成 $O(\log n)$，也不能把字符串合并当作常数操作。

辅助空间也要区分：递归栈为 $O(\log(n+1))$；Python 实现还可能保留、生成中间前缀字符串。对 $n\geq2$，将这些字符串计入后的辅助空间上界可写为 $O((\ell+1)\log(n+1))$，不包含输入。实际前缀可能很短，这些是上界，不表示每次合并都扫描到最长字符串末尾。

方法比较

比较角度	快速排序：原地版本	木材加工：二分答案	最长公共前缀：分组合并
缩小的对象	基准两侧的数组区间	整数段长的候选区间	字符串列表的下标区间
划分依据	元素与基准的大小关系	可行性随长度单调变化	按字符串个数分成两组
是否分别求解两侧	是，空区间可直接结束	否，根据判定排除一侧	是，题解实现分别处理两组
子问题的结果	原数组对应区间已经有序	某个候选长度是否可行	一组字符串的最长公共前缀
当前层主要工作	递归之前线性划分	扫描原木，计算可切段数	递归之后逐字符合并前缀
规模是否均衡	由数据与基准决定，不保证	候选区间每轮约减半	字符串个数按中点均分
时间结论	均衡时 $O(n\log n)$，最坏 $O(n^2)$	$O(n\log(M+1))$	$O(n(\ell+1))$ 上界，$n\geq1$

表中 $n$ 在三列分别表示元素个数、原木根数和字符串个数；$M$ 是最长原木长度，$\ell$ 是最长字符串长度。相同符号的含义必须随题目明确。

回到本课的共同问题

先找出结构，再决定如何缩小问题：快速排序建立大小关系，木材加工利用单调性，最长公共前缀保留可合并的摘要。证明时要说明缩小后的任务仍然覆盖所需答案；分析效率时，要把划分、判定和合并的成本一并计入。

课堂任务

任务一：一次划分是否等于完成排序

对 [4, 2, 5, 1, 3] 使用本课的末尾基准划分，写出返回下标、划分后的数组及下一步的两个递归区间。整个排序共进行了多少次“当前元素与基准”的大小比较？

参考答案

第一次划分后为 [2, 1, 3, 4, 5]，返回下标2。后续区间为闭区间 [0, 1] 和 [3, 4]，不能包含下标2。

第一次扫描比较4次，左侧 [2, 1] 比较1次，右侧 [4, 5] 比较1次，共6次。这里不计循环条件、递归边界判断等其他比较。

任务二：检查快速排序的退化

对于 [1, 2, 3, 4, 5]，仍选末尾元素作为基准，每次划分得到的两侧规模是多少？元素与基准共比较多少次？若所有元素都等于1，会有什么变化？

参考答案

非平凡区间长度依次为5、4、3、2，每次划分的右侧为空，左侧规模依次为4、3、2、1，共比较 $4+3+2+1=10$ 次。

全相等时，由于判断条件为 <=，所有扫描到的元素也都会进入左侧，基准仍落在当前区间末尾，规模与比较次数相同。这说明数据是否重复、如何处理相等值，都会影响划分质量。

任务三：找出二分更新的理由

原木为 [11, 21]、$k=6$。从闭区间 [1, 21] 开始，记录每轮中点、可切段数和更新后的区间。为什么不能在中点可行时直接返回？

参考答案

当前区间	中点	可切段数	更新后区间	已记录答案
[1, 21]	11	1 + 1 = 2	[1, 10]	0
[1, 10]	5	2 + 4 = 6	[6, 10]	5
[6, 10]	8	1 + 2 = 3	[6, 7]	5
[6, 7]	6	1 + 3 = 4	[6, 5]	5

区间为空后返回5。长度5可行、长度6不可行，结合单调性可验证最优性。中点可行只说明它是一个候选答案，仍需排除右侧存在更优解的可能；即使段数恰好为 $k$，也不能省略这一步。

任务四：分组返回什么信息

对 ['flower', 'flow', 'flight', 'flute'] 按中点分组，写出两个子组的返回值与整体答案。若最后一个字符串改为空字符串，结果如何？能否用每组“最短字符串的长度”代替前缀字符串进行合并？

参考答案

左组 ['flower', 'flow'] 返回 'flow'，右组 ['flight', 'flute'] 返回 'fl'，整体返回 'fl'。若最后一个字符串为空，右组与整体都返回 ''。

只返回最短长度不够，因为字符内容决定公共前缀。例如 ['ab', 'ac'] 与 ['ab', 'ab'] 的最短长度都为2，但公共前缀分别是 'a' 与 'ab'。摘要必须保留完成合并所需的信息。

任务五：判断复杂度说法

判断并修正三句话：“快速排序原地交换，所以总辅助空间为常数”“木材加工二分，所以总时间为对数级”“最长公共前缀递归树高为对数级，所以总时间也是对数级”。

参考答案

三句话都不成立。

• 快速排序还要计入调用栈：均衡划分时为对数级，最坏为线性级。
• 木材加工每轮还要扫描原木，总时间为 $O(n\log(M+1))$。
• 最长公共前缀要处理两组子问题，并逐字符合并；按本课参数，时间上界为 $O(n(\ell+1))$，$n\geq1$。

完整的分析应明确输入规模、每层工作与同时保留的存储，不能只看某一个循环或树的高度。