快速排序
快速排序
中等 分治与划分 Python选出一个基准,先把元素分到它的两侧,为什么两侧排好后就不需要再次合并?
本节学习目标
- 会建模: 定义闭区间上的排序任务,说明基准两侧各自满足的关系。
- 会追踪: 根据扫描指针与区域边界,完成一次划分并确定后续递归区间。
- 会核对: 区分划分与排序,核对重复值、最坏情况和递归栈空间。
前置知识:列表下标、交换与递归;可对照合并排序理解两种分治排序。
题目描述
给定一个整数列表 nums,使用快速排序将它按非递减顺序排列,即允许相邻元素相等。不得调用 sort()、sorted() 等内置排序函数。
本题采用原地修改列表的方式:排序完成后,nums 本身已经有序,排序函数不返回新的列表。输入可以为空,也可以包含单个元素、重复值或负数;列表下标从0开始,不要求长度为2的幂。
参数、结果与适用范围
- 主调用为
quicksort(nums, 0, len(nums) - 1)。 - 内部用闭区间
[low, high]表示待排序部分,两个端点都包含在内;非空区间的下标必须有效。 low >= high表示空区间或单元素区间,直接结束;空列表的主调用区间为[0, -1]。- 每次选择当前区间最后一个元素为基准,用
<=将元素归入左侧,返回基准落定后的下标。 - 本实现不保证稳定性,也不保证对任意输入都达到 。需要分析均衡划分、平均情况与最坏情况的差别。
这是用于理解划分与递归的基础实现。Python 对递归深度有限制,较长的有序列表或全相等列表可能触发 RecursionError;学习时先使用可手工追踪的小规模数据。若任务要求最坏时间保证为 ,可对照合并排序。
贯穿示例
输入: [4, 2, 5, 1, 3]
输出: [1, 2, 3, 4, 5]
输入: [5, 1, 1, 2, 0, 0]
输出: [0, 0, 1, 1, 2, 5]
输入: [3, -1, 2, -1, 0]
输出: [-1, -1, 0, 2, 3]
全文使用第一个例子演示。第一次以3为基准,划分后得到 [2, 1, 3, 4, 5];3的位置已经确定,但左侧的 [2, 1] 仍需排序。
题目分析
核心结论
先划分,再递归。一次划分将基准放在下标 p,使左侧元素都不大于基准、右侧元素都大于基准。随后只排序 [low, p - 1] 与 [p + 1, high];两侧完成后整体有序,无须合并两个有序列表。
从按位置拆分到按大小划分
合并排序先按位置将列表均分,左右分别有序后,再通过线性合并确定跨段元素的顺序。
快速排序先选择一个基准值,重新排列元素,在递归之前就建立两侧的大小关系。左右两侧内部仍然无序,但可以分别排序:左侧的任何元素都不会越过基准排到右侧,右侧同理。
这里的“分”不保证均分。即使选择区间中间位置的元素作为基准,也不能据此断言基准值接近中位数。本文固定选择末尾元素,便于让代码、过程表和课堂推演保持一致。
定义函数、区间与边界
定义 quicksort(arr, low, high):将原列表中闭区间 [low, high] 的元素原地排好序,区间之外的元素保持不变。函数通过修改列表完成任务,正常返回值为 None。
当 low >= high 时,无须继续划分。否则调用 partition(arr, low, high),得到基准位置 p,再分别排序:
左侧闭区间:[low, p - 1]
已经落定: p
右侧闭区间:[p + 1, high]
基准不再参与子调用,因此两个子区间的长度都严格小于当前区间。设当前长度为 ,左侧有 个元素,则右侧有 个元素,运行时间满足:
这里的 取决于数据与基准,不一定接近 。
用扫描指针维护两个已处理区域
本实现采用末尾基准的单向扫描划分,常称为 Lomuto 划分。令 pivot = arr[high],用两个下标维护区域:
| 区域或变量 | 每轮扫描开始前的含义 |
|---|---|
i | 小值区域的最后一个下标,初始为 low - 1 |
闭区间 [low, i] | 已处理且小于等于基准的元素,可以为空 |
半开区间 [i + 1, j) | 已处理且大于基准的元素,可以为空 |
半开区间 [j, high) | 尚未处理的元素 |
arr[high] | 暂存的基准,不参与这一轮扫描 |
j 从 low 扫描到 high - 1,每次分两种情况:
arr[j] <= pivot:先令i += 1,再交换arr[i]与arr[j],将当前元素纳入小值区域。arr[j] > pivot:不交换;下一轮j右移后,它自然归入已处理的大值区域。
遇到小值时,如果 i + 1 与当前 j 之间存在大值,交换会把其中一个大值移到当前扫描位置;它仍属于已经处理的大值区域,所以区域关系得以保持。若交换的是同一位置,结果也正确。
扫描完成后,[low, i] 都不大于基准,[i + 1, high) 都大于基准。将 arr[i + 1] 与 arr[high] 交换,返回 p = i + 1,就得到:
[ 不大于基准的元素 | 基准 | 大于基准的元素 ]
low ... p-1 p p+1 ... high
重复值会进入左侧,因此可能有多个等于基准的元素;基准占据最终有序结果中对应值的一个合法位置。
为什么结果正确
先看划分。 初始时两个已处理区域都为空。上述两种扫描操作都保持区域关系;扫描结束并交换基准后,大小关系成立。整个过程只交换元素,不会丢失或新增元素。
再看递归。 长度不超过1的区间已经有序。假设更小区间都能正确排序,左右子调用完成后,左侧内部有序且所有值不大于基准,右侧内部有序且所有值大于基准,因此当前整个区间有序。
每个子区间都排除了基准位置,规模严格缩小,最终到达边界。由此同时保证终止与排序结果正确。
实现代码
Python 原地递归实现
以下代码可以完整复制到 Python 文件中运行。划分规则与第5次课讲义一致,不创建左右子列表。
def partition(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
def quicksort(arr, low, high):
"""原地排序闭区间 [low, high],不返回新列表。"""
if low >= high:
return
# 基准位置 p 不再参与后续递归
p = partition(arr, low, high)
quicksort(arr, low, p - 1)
quicksort(arr, p + 1, high)
if __name__ == "__main__":
cases = [
[4, 2, 5, 1, 3],
[5, 1, 1, 2, 0, 0],
[3, -1, 2, -1, 0],
[],
[7],
]
for nums in cases:
original = nums.copy() # 仅供展示排序前的数据
quicksort(nums, 0, len(nums) - 1)
print(f"{original} -> {nums}")
输出:
[4, 2, 5, 1, 3] -> [1, 2, 3, 4, 5]
[5, 1, 1, 2, 0, 0] -> [0, 0, 1, 1, 2, 5]
[3, -1, 2, -1, 0] -> [-1, -1, 0, 2, 3]
[] -> []
[7] -> [7]
original = nums.copy() 只用于保留示例输入,不属于排序函数所需的存储。实际使用时,可以直接调用 quicksort(nums, 0, len(nums) - 1),随后读取 nums;不能写成 nums = quicksort(...),因为函数返回的是 None。
算法执行过程
观察任务
| 阶段 | 观察任务 |
|---|---|
| 划分前 | 标记末尾基准3,并预测它最终会落在哪个下标 |
| 逐步扫描 | 核对 i、j 与小值区、大值区,注意交换不一定发生在相邻元素之间 |
| 递归处理 | 写出排除基准后的两个闭区间,检查它们是否严格缩小 |
| 排序完成 | 核对全部元素、重复值与最终顺序,并区分划分次数和比较次数 |
交互动画
动画默认输入为 [4, 2, 5, 1, 3],与正文过程表一致:采用末尾基准、<= 归左侧和闭区间递归。柱子下方是从0开始的下标,i 表示小值区末端,j 表示当前扫描位置;i = low - 1 时小值区为空。
紫色表示基准,黄色表示正在比较,蓝色和橙色分别表示已处理的小值区与大值区,灰色表示待处理或当前区间之外的元素,绿色表示位置已落定。过程表记录本轮操作后的状态,因此扫描行的大值区写为闭区间 [i + 1, j];它与正文“下一轮开始前”的半开区间写法对应。
支持上一步、下一步、播放与暂停、速度调节、进度拖动、重置、随机数据和全屏演示。自定义输入限最多12个整数,每个值在 -99 到999之间,用逗号或空格分隔;留空后点击“应用”可以观察空列表。无效输入会提示修改,保留当前演示。这里的数量与数值限制用于便于观察,不是 Python 主实现的参数限制。
柱高按当前输入的最小值与最大值归一化,实际数值以柱顶标签为准,负数也可以演示。动画省略同一下标的自交换,“交换”计数仅统计不同下标的交换;它与 Python 代码的排序状态、比较次数和划分结果一致。
先逐步观察第一次划分,再拖到末尾核对结果:默认示例共3次划分、6次元素与基准比较。随后尝试 [2, 2, 2, 2, 2],比较调用树的深度与比较次数。
第一次划分:扫描与交换
输入为 [4, 2, 5, 1, 3],low = 0、high = 4、pivot = 3,初始 i = -1。表中的 i 是本轮操作后的值;小值区、大值区均为本轮扫描后的已处理区域,不包括末尾基准。
| 本轮操作 | 比较结果 | 操作后的 i | 整个数组 | 已处理的小值区 | 已处理的大值区 |
|---|---|---|---|---|---|
j = 0,检查4 | 4 <= 3 为假 | -1 | [4, 2, 5, 1, 3] | 空 | [4] |
j = 1,检查2 | 2 <= 3 为真 | 0 | [2, 4, 5, 1, 3] | [2] | [4] |
j = 2,检查5 | 5 <= 3 为假 | 0 | [2, 4, 5, 1, 3] | [2] | [4, 5] |
j = 3,检查1 | 1 <= 3 为真 | 1 | [2, 1, 5, 4, 3] | [2, 1] | [5, 4] |
扫描结束后,将下标2处的5与末尾基准3交换:
[2, 1 | 3 | 4, 5]
p=2
左右内部是否有序,并不是一次划分的保证。例如此时左侧 [2, 1] 仍无序。右侧恰好有序,也仍会按代码继续递归检查。
递归调用:排除已经落定的基准
闭区间调用树如下,空区间和单元素区间都直接返回:
quicksort(0, 4),基准3落在 p=2
├── quicksort(0, 1),基准1落在 p=0
│ ├── quicksort(0, -1) → 空区间,返回
│ └── quicksort(1, 1) → 单元素,返回
└── quicksort(3, 4),基准5落在 p=4
├── quicksort(3, 3) → 单元素,返回
└── quicksort(5, 4) → 空区间,返回
执行顺序与代码一致:先完成整个左侧调用,再处理右侧。
| 划分次序 | 当前闭区间 | 基准 | 返回位置 p | 本次划分后的整个数组 | 元素与基准比较次数 |
|---|---|---|---|---|---|
| 1 | [0, 4] | 3 | 2 | [2, 1, 3, 4, 5] | 4 |
| 2 | [0, 1] | 1 | 0 | [1, 2, 3, 4, 5] | 1 |
| 3 | [3, 4] | 5 | 4 | [1, 2, 3, 4, 5] | 1 |
共3次划分、6次元素与基准的比较。这里仅统计 arr[j] <= pivot,不包含循环条件与递归边界判断。
重复值与稳定性:相等不代表可以停止
对 [2, 2, 2],第一次基准为2,两个扫描元素都满足 <=,基准仍落在末尾。下一次继续处理前两个元素。因此,“所有元素相等”不会让本文实现立即结束,反而会造成极不均衡的划分。
原地交换也可能改变相等元素的相对顺序。给两个相等的2加上身份标记,仅按数值比较:
输入: [2甲, 2乙, 1]
第一次划分后: [1, 2乙, 2甲]
最终结果: [1, 2乙, 2甲]
第一次把末尾基准1与第一个元素交换,两个2的先后就改变了,因此该实现不稳定。身份标记仅用于说明顺序,不是让 Python 比较这些标记字符串。
与合并排序、二分答案比较
| 比较对象 | 快速排序 | 合并排序 | 木材加工 |
|---|---|---|---|
| 缩小什么 | 基准两侧的元素区间 | 按位置均分的元素区间 | 候选段长区间 |
| 两侧是否都要处理 | 是,空区间直接结束 | 是 | 否,依据单调性排除一侧 |
| 主要工作在哪里 | 递归之前进行划分 | 递归之后合并有序段 | 每轮扫描原木,判定候选长度 |
| 是否保证均衡缩小 | 不保证 | 保证按位置约减半 | 候选长度区间每轮约减半 |
快速排序用基准建立两侧的大小关系,不能据此丢掉一侧的排序任务;木材加工则利用可行性的单调性排除不可能产生更优答案的候选。
复杂度分析
先看结论
设待排序元素数为 ,按整数比较、赋值与交换为单位成本。以下均针对本文的原地递归版本,排序辅助空间不包含输入列表。
| 情况或任务 | 时间复杂度 | 辅助空间复杂度 | 条件或说明 |
|---|---|---|---|
| 一次非平凡区间划分 | 扫描区间内除基准外的元素 | ||
| 持续均衡划分 | 两侧规模保持均衡,空间主要来自调用栈 | ||
| 平均情况 | 期望 | 互异元素的所有排列等可能 | |
| 最坏情况 | 每次基准都落在区间端点,例如有序或全相等输入 | ||
| 空列表或单元素列表 | 不执行划分 |
上表的对数级结论针对 ;均衡和平均情况下,若计入示例程序保存原列表副本的展示开销,程序总存储还包含这份 副本。
时间复杂度
长度为 的区间进行一次划分,恰好比较 次元素与基准,额外交换次数至多为线性级,因此划分时间为 。
均衡划分时: 同层各区间的总长度至多为 ,每层工作为 ,共 层,得到 。
最坏划分时: 每次只排除一个基准,其余元素全部进入同一侧,比较次数为:
因此最坏时间为 。例如 [1, 2, 3, 4, 5] 的末尾元素每次都是最大值,比较次数为 ;全相等输入因 <= 分支也有相同的规模变化。
平均情况: 当互异元素的输入排列等可能时,基准的秩在各位置等可能,可得平均时间为 。这个结论带有输入分布假设,不能当作固定末尾基准对所有数据的保证。
随机选择基准可以在互异元素输入上分析期望时间,但本文代码没有执行随机选择。对于这里的二路 <= 划分,仅随机选基准仍不能解决全相等数据的退化;大量重复值可进一步考虑三路划分,将等于基准的一整段排除在后续递归之外。
辅助空间复杂度
partition 只保存基准和固定数量的下标,辅助空间为 ;没有创建左右子列表。
完整排序还包含递归栈。均衡时栈深为 ,最坏时为 。左右调用虽然都要执行,但按先后顺序运行,不会同时保存整棵调用树。
原列表存储为 ,示例程序中的 original 副本也为 。它们与排序函数的辅助空间应分开说明。最坏复杂度描述的是递归能够完整执行时的算法成本,Python 实际还可能先遇到递归深度限制。
易错点
| 易错点 | 正确理解 |
|---|---|
| 认为一次划分后两侧都已经有序 | 只保证与基准的大小关系,两侧仍需分别排序 |
| 把左侧描述为“严格小于基准” | 本文使用 <=,相等元素进入左侧,右侧才是严格大于 |
扫描到 high,把基准也当作普通元素 | 本划分循环使用 range(low, high),最后再放置基准 |
| 忘记最后交换基准 | 扫描结束时基准仍在末尾,要交换到 i + 1 并返回该位置 |
使用 [low, p] 再次处理基准 | 左侧应为 [low, p - 1],右侧应为 [p + 1, high],确保规模缩小 |
用 low == high 作为唯一边界 | 还可能出现空区间,应该判断 low >= high |
写成 nums = quicksort(...) | 排序直接修改原列表,返回值为 None |
| 认为原地交换就没有额外空间 | 划分为常数辅助空间,完整递归还要计入调用栈 |
| 看到分为两侧就写成 | 要检查划分是否均衡,最坏时间仍为 |
| 认为随机基准一定解决重复值问题 | 全相等元素在该二路划分中仍会全部进入左侧,可进一步研究三路划分 |
| 认为交换排序一定稳定 | [2甲, 2乙, 1] 可以改变两个2的相对顺序 |
课堂练习
先独立作答,再逐题展开答案核对。
基础核对
1. 空列表与 [7] 的主调用区间分别是什么?为什么都不进入 partition?quicksort 的返回值是什么?
参考答案
空列表对应 [0, -1],单元素列表对应 [0, 0]。两者都满足 low >= high,直接返回 None,不会读取无效的基准位置;排序结果仍保存在原列表中。
2. 在 [3, 1, 3, 2, 3] 上执行第一次划分,基准落在哪个位置?之后需要处理哪些区间?
参考答案
基准为末尾的3,前四个元素都满足 <= 3,数组保持不变,返回 p = 4。后续区间为 [0, 3] 和空区间 [5, 4]。基准左侧仍有等于3的元素,不能将左侧称为“严格小于基准”。
过程推演
3. 对 [3, 1, 4, 2] 执行第一次划分,写出扫描中的交换、最终数组、基准下标和后续区间。
参考答案
基准为2,初始 i = -1。扫描3时不交换;扫描1时令 i = 0,交换3与1,得到 [1, 3, 4, 2];扫描4时不交换。最后交换下标1处的3与末尾的2,得到 [1, 2, 4, 3],返回 p = 1。
继续处理闭区间 [0, 0] 与 [2, 3]。右侧 [4, 3] 仍需排序,整体结果为 [1, 2, 3, 4]。
4. 对 [1, 2, 3, 4, 5] 与 [2, 2, 2, 2, 2],完整排序分别需要多少次元素与基准比较?为什么?
参考答案
两者都是 次。每次基准都落在当前区间末尾,右侧为空,左侧长度仅减少1。前者因末尾元素最大而退化,后者因全部满足 <= 而退化。
进阶思考
5. 如果把基准改为“当前区间中间位置的元素”,是否一定得到两个规模相近的子问题?改变基准选择后,能否直接保留本文全部过程表?
参考答案
不能保证。位置居中不等于数值居中,例如 [4, 3, 1, 2, 5] 的中间元素是最小值1,按它划分仍会极不均衡。
若继续使用本文的 partition,需先将选中的基准交换到 high,再进行末尾基准划分。更换基准会改变后续交换与区间,因此必须重新核对执行过程,不能直接沿用原表。
6. 快速排序与合并排序都需要处理左右两个子问题,为什么前者不需要再合并?两者的稳定性有什么差别?
参考答案
快速排序在递归前已建立“左侧不大于基准、右侧大于基准”的关系,两侧内部有序后整体自然有序。合并排序只按位置拆分,左右仍可能交错,需要归并确定整体顺序。
本文快速排序的非相邻交换不保证稳定性;课程中的合并排序在相等时先取左侧元素,因而保持稳定性。
继续学习: 对照合并排序比较分治排序,再阅读最长公共前缀理解返回摘要与合并;课堂串联见2026年秋第5次课。
