不明白为什么初始检查不能阻止 "unsupported operand type(s) for +" 发生

Question

我在执行 Quicksort 时遇到了以下错误。我注意到大多数递归算法都在前面声明了 length == 1 检查。但为什么它在这种情况下不起作用？

def quicksort(array):
    if len(array)==1:
        return array
    elif len(array)>1:
        less=[]
        equal=[]
        greater=[]
        pivot=array[0]
        for x in array:
            if x<pivot:
                less.append(x)
            if x==pivot:
                equal.append(x)
            if x>pivot:
                greater.append(x)
            array=quicksort(less)+equal+quicksort(greater)
        return array

lst=[7,2,6,4,5,1,3,8]
quicksort(lst)

错误大约是 unsupported operand type(s) for +: 'NoneType' and 'list'。我不明白 NoneType 是从哪里来的。我认为它至少应该是一个空列表 [].

颠倒 length==1 和 length>1 案例的顺序解决了问题，但我不明白为什么。

Answer 1

问题在于您在 quicksort 中的 if-elif 语句。

本质上，当您首先使用 lst 运行 quicksort 时，如果您在 array=quicksort(less)+equal+quicksort(greater) 之前添加此代码：

print(less)
print(equal)
print(greater)

可以看到less和greater都是空列表。

当您将它们作为值递归传递给 quicksort 时，它们作为空列表的长度将为 0。您的 if-elif 语句仅涵盖数组长度恰好为 1 或大于 1 的情况。因为长度为 0，所以两个块都不会执行，因此您的函数将默认返回 None.

因此，这一行：

array=quicksort(less)+equal+quicksort(greater)

正在尝试这样做：

array=None+[7]+None

这会导致您的错误。

不明白为什么初始检查不能阻止 "unsupported operand type(s) for +" 发生

Don't understand why initial check doesn't prevent "unsupported operand type(s) for +" from occurring

python

algorithm

sorting

recursion

quicksort