跳至主要內容

快速排序

周子力大约 18 分钟教学文档算法设计与分析递归与分治递归分治法排序Python

快速排序

中等 分治与划分 Python

选出一个基准,先把元素分到它的两侧,为什么两侧排好后就不需要再次合并?

本节学习目标

  • 会建模: 定义闭区间上的排序任务,说明基准两侧各自满足的关系。
  • 会追踪: 根据扫描指针与区域边界,完成一次划分并确定后续递归区间。
  • 会核对: 区分划分与排序,核对重复值、最坏情况和递归栈空间。

前置知识:列表下标、交换与递归;可对照合并排序理解两种分治排序。

题目描述

给定一个整数列表 nums,使用快速排序将它按非递减顺序排列,即允许相邻元素相等。不得调用 sort()、sorted() 等内置排序函数。

本题采用原地修改列表的方式:排序完成后,nums 本身已经有序,排序函数不返回新的列表。输入可以为空,也可以包含单个元素、重复值或负数;列表下标从0开始,不要求长度为2的幂。

参数、结果与适用范围

  • 主调用为 quicksort(nums, 0, len(nums) - 1)。
  • 内部用闭区间 [low, high] 表示待排序部分,两个端点都包含在内;非空区间的下标必须有效。
  • low >= high 表示空区间或单元素区间,直接结束;空列表的主调用区间为 [0, -1]。
  • 每次选择当前区间最后一个元素为基准,用 <= 将元素归入左侧,返回基准落定后的下标。
  • 本实现不保证稳定性,也不保证对任意输入都达到 O(nlog⁡n)O(n\log n)。需要分析均衡划分、平均情况与最坏情况的差别。

这是用于理解划分与递归的基础实现。Python 对递归深度有限制,较长的有序列表或全相等列表可能触发 RecursionError;学习时先使用可手工追踪的小规模数据。若任务要求最坏时间保证为 O(nlog⁡n)O(n\log n),可对照合并排序。

贯穿示例

输入: [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]

基准不再参与子调用,因此两个子区间的长度都严格小于当前区间。设当前长度为 nn,左侧有 kk 个元素,则右侧有 n−k−1n-k-1 个元素,运行时间满足:

T(n)=T(k)+T(n−k−1)+O(n),T(0),T(1)=O(1). T(n)=T(k)+T(n-k-1)+O(n),\qquad T(0),T(1)=O(1).

这里的 kk 取决于数据与基准,不一定接近 n/2n/2。

用扫描指针维护两个已处理区域

本实现采用末尾基准的单向扫描划分,常称为 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],比较调用树的深度与比较次数。

单步观察末尾基准划分,联动查看调用树、代码高亮和过程表。下标从0开始。

第一次划分:扫描与交换

输入为 [4, 2, 5, 1, 3],low = 0、high = 4、pivot = 3,初始 i = -1。表中的 i 是本轮操作后的值;小值区、大值区均为本轮扫描后的已处理区域,不包括末尾基准。

本轮操作比较结果操作后的 i整个数组已处理的小值区已处理的大值区
j = 0,检查44 <= 3 为假-1[4, 2, 5, 1, 3]空[4]
j = 1,检查22 <= 3 为真0[2, 4, 5, 1, 3][2][4]
j = 2,检查55 <= 3 为假0[2, 4, 5, 1, 3][2][4, 5]
j = 3,检查11 <= 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]32[2, 1, 3, 4, 5]4
2[0, 1]10[1, 2, 3, 4, 5]1
3[3, 4]54[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 比较这些标记字符串。

与合并排序、二分答案比较

比较对象快速排序合并排序木材加工
缩小什么基准两侧的元素区间按位置均分的元素区间候选段长区间
两侧是否都要处理是,空区间直接结束是否,依据单调性排除一侧
主要工作在哪里递归之前进行划分递归之后合并有序段每轮扫描原木,判定候选长度
是否保证均衡缩小不保证保证按位置约减半候选长度区间每轮约减半

快速排序用基准建立两侧的大小关系,不能据此丢掉一侧的排序任务;木材加工则利用可行性的单调性排除不可能产生更优答案的候选。

复杂度分析

先看结论

设待排序元素数为 nn,按整数比较、赋值与交换为单位成本。以下均针对本文的原地递归版本,排序辅助空间不包含输入列表。

情况或任务时间复杂度辅助空间复杂度条件或说明
一次非平凡区间划分O(n)O(n)O(1)O(1)扫描区间内除基准外的元素
持续均衡划分O(nlog⁡n)O(n\log n)O(log⁡n)O(\log n)两侧规模保持均衡,空间主要来自调用栈
平均情况O(nlog⁡n)O(n\log n)期望 O(log⁡n)O(\log n)互异元素的所有排列等可能
最坏情况O(n2)O(n^2)O(n)O(n)每次基准都落在区间端点,例如有序或全相等输入
空列表或单元素列表O(1)O(1)O(1)O(1)不执行划分

上表的对数级结论针对 n≥2n\geq2;均衡和平均情况下,若计入示例程序保存原列表副本的展示开销,程序总存储还包含这份 O(n)O(n) 副本。

时间复杂度

长度为 m≥2m\geq2 的区间进行一次划分,恰好比较 m−1m-1 次元素与基准,额外交换次数至多为线性级,因此划分时间为 O(m)O(m)。

均衡划分时: 同层各区间的总长度至多为 nn,每层工作为 O(n)O(n),共 O(log⁡n)O(\log n) 层,得到 O(nlog⁡n)O(n\log n)。

最坏划分时: 每次只排除一个基准,其余元素全部进入同一侧,比较次数为:

(n−1)+(n−2)+⋯+1=n(n−1)2. (n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}.

因此最坏时间为 O(n2)O(n^2)。例如 [1, 2, 3, 4, 5] 的末尾元素每次都是最大值,比较次数为 4+3+2+1=104+3+2+1=10;全相等输入因 <= 分支也有相同的规模变化。

平均情况: 当互异元素的输入排列等可能时,基准的秩在各位置等可能,可得平均时间为 O(nlog⁡n)O(n\log n)。这个结论带有输入分布假设,不能当作固定末尾基准对所有数据的保证。

随机选择基准可以在互异元素输入上分析期望时间,但本文代码没有执行随机选择。对于这里的二路 <= 划分,仅随机选基准仍不能解决全相等数据的退化;大量重复值可进一步考虑三路划分,将等于基准的一整段排除在后续递归之外。

辅助空间复杂度

partition 只保存基准和固定数量的下标,辅助空间为 O(1)O(1);没有创建左右子列表。

完整排序还包含递归栈。均衡时栈深为 O(log⁡n)O(\log n),最坏时为 O(n)O(n)。左右调用虽然都要执行,但按先后顺序运行,不会同时保存整棵调用树。

原列表存储为 O(n)O(n),示例程序中的 original 副本也为 O(n)O(n)。它们与排序函数的辅助空间应分开说明。最坏复杂度描述的是递归能够完整执行时的算法成本,Python 实际还可能先遇到递归深度限制。

易错点

易错点正确理解
认为一次划分后两侧都已经有序只保证与基准的大小关系,两侧仍需分别排序
把左侧描述为“严格小于基准”本文使用 <=,相等元素进入左侧,右侧才是严格大于
扫描到 high,把基准也当作普通元素本划分循环使用 range(low, high),最后再放置基准
忘记最后交换基准扫描结束时基准仍在末尾,要交换到 i + 1 并返回该位置
使用 [low, p] 再次处理基准左侧应为 [low, p - 1],右侧应为 [p + 1, high],确保规模缩小
用 low == high 作为唯一边界还可能出现空区间,应该判断 low >= high
写成 nums = quicksort(...)排序直接修改原列表,返回值为 None
认为原地交换就没有额外空间划分为常数辅助空间,完整递归还要计入调用栈
看到分为两侧就写成 O(nlog⁡n)O(n\log n)要检查划分是否均衡,最坏时间仍为 O(n2)O(n^2)
认为随机基准一定解决重复值问题全相等元素在该二路划分中仍会全部进入左侧,可进一步研究三路划分
认为交换排序一定稳定[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],完整排序分别需要多少次元素与基准比较?为什么?

参考答案

两者都是 4+3+2+1=104+3+2+1=10 次。每次基准都落在当前区间末尾,右侧为空,左侧长度仅减少1。前者因末尾元素最大而退化,后者因全部满足 <= 而退化。

进阶思考

5. 如果把基准改为“当前区间中间位置的元素”,是否一定得到两个规模相近的子问题?改变基准选择后,能否直接保留本文全部过程表?

参考答案

不能保证。位置居中不等于数值居中,例如 [4, 3, 1, 2, 5] 的中间元素是最小值1,按它划分仍会极不均衡。

若继续使用本文的 partition,需先将选中的基准交换到 high,再进行末尾基准划分。更换基准会改变后续交换与区间,因此必须重新核对执行过程,不能直接沿用原表。

6. 快速排序与合并排序都需要处理左右两个子问题,为什么前者不需要再合并?两者的稳定性有什么差别?

参考答案

快速排序在递归前已建立“左侧不大于基准、右侧大于基准”的关系,两侧内部有序后整体自然有序。合并排序只按位置拆分,左右仍可能交错,需要归并确定整体顺序。

本文快速排序的非相邻交换不保证稳定性;课程中的合并排序在相等时先取左侧元素,因而保持稳定性。

继续学习: 对照合并排序比较分治排序,再阅读最长公共前缀理解返回摘要与合并;课堂串联见2026年秋第5次课。

上次编辑于:
贡献者: zilizhou,zlzhou