Python快速排序处理重复值数据为何递归报错且效率极低？

我最近在Python里对比各类排序算法，发现自己实现的快速排序处理含重复值的输入时表现特别拉胯。先上我的实现代码：

def compare_asc(a, b): return a <= b
def partition(a, p, r, compare):
    pivot = a[r]
    i = p-1
    for j in range(p, r):
        if compare(a[j], pivot):
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[r] = a[r], a[i+1]
    return i + 1
def part_quick_sort(a, p, r, compare):
    if p < r:
        q = partition(a, p, r, compare)
        part_quick_sort(a, p, q-1, compare)
        part_quick_sort(a, q+1, r, compare)
def quick_sort(a, compare):
    part_quick_sort(a, 0, len(a)-1, compare)
    return a

测试代码是这样的：

import numpy as np
from timeit import default_timer as timer
import sys
test_list1 = np.random.randint(-10000, 10000, size=10000).tolist()
start = timer()
test_list1 = quick_sort(test_list1, compare_asc)
elapsed = timer() - start
print(elapsed)
test_list2 = np.random.randint(0, 2, size=10000).tolist()
start = timer()
test_list2 = quick_sort(test_list2, compare_asc)
elapsed = timer() - start
print(elapsed)

测试结果很奇怪：排序test_list1（随机整数，重复值少）耗时大概0.03秒，但排序test_list2（只有0和1，大量重复值）先是触发RecursionError: maximum recursion depth exceeded in comparison，我把sys.setrecursionlimit(1000000)调高之后，耗时居然长达5.5秒左右。

想请教两个问题：

1. 为什么只有排序第二个列表时会出现递归深度错误？
2. 两者耗时差异这么大的原因是什么？

问题1：为什么仅含大量重复值的列表会触发递归深度错误？ #

你的快速排序用的是Lomuto分区方案，而且固定选择当前子数组的最后一个元素作为基准值（pivot）。当列表里全是重复值（比如只有0和1）时，这个分区逻辑直接踩了大坑：

因为你的compare_asc函数判断的是a[j] <= pivot，当所有元素都等于pivot时，循环里的if条件会一直成立，i会从p-1一路递增到r-1。最后交换i+1和r的位置后，返回的q值就是r（当前子数组的最后一个索引）。

这意味着递归调用时：

• 第一个递归是part_quick_sort(a, p, q-1, compare) → 也就是处理除了最后一个元素之外的子数组，问题规模只减少了1
• 第二个递归是part_quick_sort(a, q+1, r, compare) → 因为q+1 = r+1 > r，直接不满足p < r的条件，相当于啥也没做

换句话说，每次递归只能把问题规模减少1。对于10000个元素的列表，递归深度会达到10000层，而Python默认的递归深度限制是1000左右，所以直接触发了RecursionError。

而test_list1里的元素重复率低，分区后q会落在子数组的中间附近，递归深度大概是log2(10000) ≈14层，远低于默认限制，所以完全不会报错。

问题2：为什么两者耗时差异巨大？ #

核心还是分区效率的天差地别：

• 对于test_list1，每次分区能把数组分成大小差不多的两部分，时间复杂度是O(n log n)，这是快速排序的最优情况，所以耗时很短。
• 对于test_list2，每次分区只能把数组规模减少1，相当于直接退化成了**冒泡排序级别的O(n²)**时间复杂度。10000个元素的话，需要执行大约1000010000/2=5000万次操作，这比O(n log n)的1000014≈14万次操作多了好几个数量级，耗时自然会暴涨到5秒多。

如何修复这个问题？ #

给你两个常用的改进方向，都能解决重复值场景下的性能问题：

1. 改用Hoare分区方案：这种分区方式在处理重复值时表现更好，能把重复的基准值分散到子数组的两边，避免出现极端的分区情况。
2. 三向切分快速排序：专门针对大量重复值的场景，把数组分成小于基准、等于基准、大于基准三部分，只递归处理小于和大于的部分，等于的部分直接跳过，效率会大幅提升。

比如三向切分的简化实现大概是这样：

def three_way_partition(a, p, r, compare):
    pivot = a[r]
    lt = p  # 小于pivot的区域末尾索引
    gt = r  # 大于pivot的区域开头索引
    i = p
    while i <= gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1
        else:
            i += 1
    return lt, gt

def three_way_quick_sort(a, p, r, compare):
    if p < r:
        lt, gt = three_way_partition(a, p, r, compare)
        three_way_quick_sort(a, p, lt-1, compare)
        three_way_quick_sort(a, gt+1, r, compare)

用这种方式处理全是重复值的列表时，递归深度会降到O(log n)，时间复杂度也会优化到O(n)（因为等于基准的部分不用递归处理）。

内容的提问来源于stack exchange，提问作者Arryyyy