快排 partition 三种写法的边界与死循环坑

很多人第一次写快排，排序小数组没问题，一跑几千个元素就 RecursionError，或者直接卡死。十有八九是 partition 的返回值和边界没搞对。这篇文章用 Python 把 Lomuto、Hoare 和三路划分的 partition 写清楚，并给出对应的错误写法和测试用例。代码可以直接复制运行。

partition 的契约：返回值到底代表什么

写 partition 之前，先定好它的契约：函数接收数组和区间 [lo, hi]，返回一个索引或索引对，然后递归调用必须根据这个返回值把区间切分，保证每个元素都被处理且不会无限递归。

三种常见划分的契约：

写法	返回值	左边	右边	递归调用
Lomuto	p，pivot 最终位置	[lo, p-1] 都 <= pivot	[p+1, hi] 都 > pivot	quicksort(lo, p-1)，quicksort(p+1, hi)
Hoare	j，分割点	[lo, j] 都 <= pivot	[j+1, hi] 都 >= pivot	quicksort(lo, j)，quicksort(j+1, hi)
三路	(lt, gt)	[lo, lt-1] 都 < pivot	[gt+1, hi] 都 > pivot	quicksort(lo, lt-1)，quicksort(gt+1, hi)，中间 [lt, gt] 全等于 pivot

关键差别：Hoare 返回的 j 不一定是 pivot 的位置，而且左右子区间都可能包含等于 pivot 的元素。如果按 Lomuto 的方式递归，就会漏掉元素或死循环。

先看一个能跑的正确三路划分版本，后面再逐个说坑。

import random
import sys

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return
    # 随机选 pivot 并放到 lo 位置，避免有序数组退化
    rand = random.randint(lo, hi)
    arr[lo], arr[rand] = arr[rand], arr[lo]
    lt, gt = three_way_partition(arr, lo, hi)
    quicksort(arr, lo, lt - 1)
    quicksort(arr, gt + 1, hi)

def three_way_partition(arr, lo, hi):
    pivot = arr[lo]
    lt = lo
    gt = hi
    i = lo
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[gt], arr[i] = arr[i], arr[gt]
            gt -= 1
            # 注意：i 不增加，因为从 gt 换过来的元素还没检查
        else:
            i += 1
    return lt, gt

测试：

if __name__ == '__main__':
    for case in [
        [],
        [1],
        [2, 1],
        [1, 2, 3, 4, 5],
        [5, 4, 3, 2, 1],
        [3, 3, 3, 3, 3],
        [random.randint(0, 100) for _ in range(1000)],
    ]:
        original = case[:]
        quicksort(case)
        assert case == sorted(original), f'排序失败: {original} -> {case}'
    print('所有测试通过')

这个三路划分处理全相等数组时，lt 会停在 lo，gt 会停在 hi，递归直接返回，复杂度 O(n)。如果你用 Lomuto 并且用 <= 比较，全相等数组会让每次划分只减少一个元素，递归深度 n，Python 默认递归限制 1000，1000 个相同元素就栈溢出。

Lomuto：简单，但别用 <=

Lomuto 是最容易理解的写法：选最后一个元素为 pivot，用一个指针 i 记录小于 pivot 的边界，遍历 j，遇到小于 pivot 的就交换。

正确写法（随机化 pivot）：

def lomuto_partition(arr, lo, hi):
    # 随机选 pivot 与 hi 交换
    rand = random.randint(lo, hi)
    arr[rand], arr[hi] = arr[hi], arr[rand]
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

def quicksort_lomuto(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return
    p = lomuto_partition(arr, lo, hi)
    quicksort_lomuto(arr, lo, p - 1)
    quicksort_lomuto(arr, p + 1, hi)

这段代码里 for j in range(lo, hi) 只遍历到 hi-1，最后把 arr[hi] 换到 i。边界没问题。

常见的错误写法：

# 错误示范 1：循环到 hi，最后又交换了一次
def bad_lomuto_1(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi + 1):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]  # 这里可能越界或者把已就位的元素又打乱
    return i

错误点：j 到 hi 时，arr[hi] 等于 pivot，<= 成立，会把自己交换到 i，然后最后又交换一次。结果 pivot 被换走，返回值 i 也不对。更严重的是，如果所有元素都 <= pivot，i 会变成 hi+1，最后 arr[i] 越界。

错误示范 2：用 <= 处理重复元素。

def bad_lomuto_2(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] <= pivot:  # 等于 pivot 的元素也放到左边
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

当数组全相等时，每次 arr[j] <= pivot 都成立，i 一直增加到 hi，最后返回 hi。递归调用 quicksort_lomuto(arr, lo, hi-1)，只缩小一个元素，递归深度 n。1000 个相同元素就会触发 RecursionError。实测在 CPython 3.11 下，2000 个全相等元素就炸了（默认递归限制 1000）。而三路划分处理 10 万个全相等元素毫无压力。

所以 Lomuto 不是不能用，但你要知道它的弱点：重复元素多的时候会退化。如果一定要用，至少把 <= 改成 <，并且把等于 pivot 的元素均匀分到两边？单靠 < 并不能解决所有相等的情况，因为等于 pivot 的元素全留在右边，当数组全相等时，i 一直是 lo，返回 lo，递归 quicksort(arr, lo+1, hi)，仍然每次只减少一个元素。所以 Lomuto 对重复元素天生不友好。

Hoare：性能好，但返回值最容易搞错

Hoare 划分用两个指针从两端向中间走，遇到逆序就交换。它比 Lomuto 少一些交换次数，平均性能更好。但它的返回值 j 不是 pivot 的位置，递归调用也和 Lomuto 不同。

经典实现（pivot 取 arr[lo]）：

def hoare_partition(arr, lo, hi):
    pivot = arr[lo]
    i = lo - 1
    j = hi + 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]

注意这里内层 while 没有写边界检查，因为 pivot = arr[lo] 充当了哨兵：i 最多走到 lo 就会停（arr[lo] == pivot，不满足 < pivot），j 最多走到 lo 也会停（arr[lo] == pivot，不满足 > pivot）。所以不会越界。但如果你把 pivot 改成 arr[(lo+hi)//2]，就必须加边界检查，否则 i 或 j 可能跑出区间。

递归调用：

def quicksort_hoare(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return
    j = hoare_partition(arr, lo, hi)
    quicksort_hoare(arr, lo, j)
    quicksort_hoare(arr, j + 1, hi)

注意递归用的是 quicksort_hoare(arr, lo, j) 和 quicksort_hoare(arr, j + 1, hi)，不是 j-1。这是最容易错的地方。如果写成 quicksort_hoare(arr, lo, j-1)，就会漏掉 j 位置的元素；如果写成 quicksort_hoare(arr, j+1, hi) 和 quicksort_hoare(arr, lo, j-1)，当 j == lo 时，quicksort_hoare(arr, lo, lo-1) 直接返回，但 quicksort_hoare(arr, lo+1, hi) 可能漏掉 lo 位置的元素？实际上 Hoare 返回的 j 满足 arr[lo..j] <= pivot 和 arr[j+1..hi] >= pivot。所以左区间是 [lo, j]，右区间是 [j+1, hi]。如果错写成 [lo, j-1]，j 位置的元素就丢了，排序结果可能不对。这个错误在小数组上很难发现，因为漏掉一个元素可能恰好顺序是对的。

举个具体的错误例子：

# 错误：递归区间写错
def bad_quicksort_hoare(arr, lo, hi):
    if lo >= hi:
        return
    j = hoare_partition(arr, lo, hi)
    bad_quicksort_hoare(arr, lo, j - 1)  # 错误！应该用 j
    bad_quicksort_hoare(arr, j + 1, hi)

测试 [3, 1, 2]：

• hoare_partition(arr, 0, 2)：pivot=3，i 从 -1 开始，i=0 时 arr[0]=3 不小于 3，停；j 从 3 开始，j=2 时 arr[2]=2 不大于 3，停；i=0 < j=2，交换 arr[0] 和 arr[2]，数组变 [2, 1, 3]。继续：i=1，arr[1]=1 < 3，i=2，arr[2]=3 不小于 3，停；j=1，arr[1]=1 不大于 3，停；i=2 >= j=1，返回 j=1。数组是 [2, 1, 3]。
• 按错误写法：左区间 [0, 0]，右区间 [2, 2]。中间索引 1 的元素 1 被漏掉了！最终排序可能还是 [2, 1, 3]？左区间 [0,0] 只有一个元素 2 不动，右区间 [2,2] 元素 3 不动，结果 [2, 1, 3]，没排好。正确应该左区间 [0, 1]，右区间 [2, 2]，然后左区间会继续排序 [2, 1]。

这个例子说明 Hoare 的递归边界非常容易错。写的时候最好把契约写在注释里。

另外，Hoare 的内层 while 如果用 <= 或 >=，也会出问题。比如 while arr[i] <= pivot，当数组全相等时，i 会一直增加，直到越界。必须用严格的小于和大于。

三路划分：重复元素的解药

当数组中存在大量重复元素时，Lomuto 和 Hoare 都可能退化成 O(n^2)。三路划分把数组分成三块：小于 pivot、等于 pivot、大于 pivot。递归时只处理小于和大于的部分，等于的部分直接跳过。

上面已经给出了三路划分的实现。这里重点说几个坑。

坑 1：交换后 i 的移动

elif arr[i] > pivot:
    arr[gt], arr[i] = arr[i], arr[gt]
    gt -= 1
    # 这里不能 i += 1

从 gt 位置换过来的元素还没有检查过，它可能小于 pivot，也可能等于。如果直接 i += 1，就会漏掉这个元素。正确做法是 i 不动，下一轮循环继续检查同一个位置。

坑 2：循环条件 i <= gt

如果写成 i < gt，会漏掉最后一个元素。因为 gt 指向的是当前未处理区间的右边界，当 i == gt 时，这个位置的元素还没有被检查。必须用 i <= gt。

坑 3：pivot 的选择

如果直接取 arr[lo] 作为 pivot，并且没有随机化，在有序数组上仍然会退化。比如数组已经是升序 [1, 2, 3, ..., n]，取 arr[lo] 为 pivot，那么 lt 会停在 lo，gt 会一直减到 lo，递归 quicksort(lo, lt-1) 为空，quicksort(gt+1, hi) 处理剩下的 n-1 个元素，递归深度 n。所以三路划分也要随机化 pivot，或者用三数取中。

随机化方式：在划分前随机选一个下标与 lo 交换。

rand = random.randint(lo, hi)
arr[lo], arr[rand] = arr[rand], arr[lo]

坑 4：lt 和 gt 的初始值

lt = lo，gt = hi，i = lo。不要写成 lt = lo - 1 或 gt = hi + 1，那样会引入额外的边界判断。

三路划分处理全相等数组时，lt 和 gt 会在扫描过程中变成 lo 和 hi，然后递归调用 quicksort(lo, lo-1) 和 quicksort(hi+1, hi) 都直接返回，整体只遍历一遍数组，O(n)。

用对拍和递归深度检测你的 partition

写完 partition 后，不要只用几个小数组测试。下面这段脚本可以帮你发现很多问题：随机数组对拍、全相等数组、已排序数组、逆序数组，并且捕获递归深度。

import random
import sys

def check_partition(sort_func, n=1000):
    # 随机数组对拍
    for _ in range(100):
        arr = [random.randint(0, 100) for _ in range(n)]
        original = arr[:]
        try:
            sort_func(arr)
        except RecursionError:
            print(f'递归深度爆炸，数组长度 {n}，内容前10个: {original[:10]}')
            return False
        if arr != sorted(original):
            print(f'排序错误: {original[:10]} -> {arr[:10]}')
            return False

    # 全相等数组
    arr = [7] * n
    try:
        sort_func(arr)
    except RecursionError:
        print(f'全相等数组递归爆炸，长度 {n}')
        return False
    if arr != [7] * n:
        print('全相等数组排序错误')
        return False

    # 已排序数组
    arr = list(range(n))
    try:
        sort_func(arr)
    except RecursionError:
        print(f'已排序数组递归爆炸，长度 {n}')
        return False
    if arr != list(range(n)):
        print('已排序数组排序错误')
        return False

    # 逆序数组
    arr = list(range(n, 0, -1))
    try:
        sort_func(arr)
    except RecursionError:
        print(f'逆序数组递归爆炸，长度 {n}')
        return False
    if arr != list(range(1, n + 1)):
        print('逆序数组排序错误')
        return False

    print('partition 检查通过')
    return True

你可以把 sort_func 换成 quicksort（三路）、quicksort_lomuto、quicksort_hoare 分别跑。注意：quicksort_lomuto 如果不随机化，在已排序数组上会递归深度 n，直接报错。quicksort_hoare 如果递归边界写错，会在随机数组对拍中暴露出来。

另外，Python 默认递归限制是 1000，可以用 sys.setrecursionlimit(10000) 临时提高，但这只是掩盖问题，不是解决办法。生产环境应该用迭代版或者切换到标准库的 list.sort()（Timsort），它在实际数据上更稳。

什么时候不该手写快排

如果你是在做业务开发，直接用语言自带的排序。Python 的 list.sort() 和 sorted() 是 Timsort，稳定且对部分有序数据有优化；Java 的 Arrays.sort() 对基本类型用双轴快排，对对象用 Timsort；C++ 的 std::sort 是内省排序（快排+堆排+插入排序）。这些实现都经过了大量测试，比手写的 partition 可靠得多。

但你需要理解 partition，因为：

• 面试会问。
• 读源码时会遇到。
• 实现快速选择（Quickselect）求第 k 大时，partition 是核心。
• 调试别人写的快排时，能快速定位是边界问题还是 pivot 选择问题。

如果非要手写，记住三点：

1. 先写清楚 partition 的契约，返回什么，递归区间怎么切。
2. 用随机化 pivot 或三数取中，避免有序数组退化。
3. 小数组（比如长度小于 16）切换到插入排序，减少递归调用。

最后，测试时一定要包含全相等数组和两个元素的数组。很多 partition 的 bug 就藏在这两种情况下。比如两个元素 [2, 1]，Hoare 划分返回 j=0，递归 [0,0] 和 [1,1]，正确；但如果返回 j=0 后你写成了 [0, -1] 和 [1, 1]，就会漏掉第一个元素。全相等数组则能直接暴露 <= 导致的退化。