python - 快速排序返回递归深度错误

Question

我有一个简单的快速排序实现，但它返回了超出递归深度的错误，我正在对少于 30 个元素的列表进行测试。此外，几天前我的实现正在处理 10,000 个列表，我唯一改变的是将它从一个类移动到一个全局函数。有人看到可能是什么原因造成的吗？

def quickSort(m, left, right):
    if len(m[left:right]) <= 1:
        return m
    pivot = m[left]
    i = left + 1
    j = left + 1
    for j in range(j, right):
        if m[j] <= pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
    m[left], m[i-1] = m[i-1], m[left]
    m = quickSort(m, left, i)
    m = quickSort(m, i, right)
    return m

Answer 1

您的递归调用之一导致异常（您可能已经猜到了:-)，还请注意您对列表进行了排序，因此没有必要返回列表

def quickSort(m, left, right):
    if right - left  <= 1:
        return

    pivot = m[left]
    i = left + 1 
    j = left + 1 
    for j in range(j, right):
        if m[j] <= pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
    m[left], m[i-1] = m[i-1], m[left]
    quickSort(m, left, i-1)
    quickSort(m, i, right)