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

Question

我的快速排序实现遇到了以下错误。我注意到大多数递归算法都将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语句。

实际上，当你第一次运行quicksort和lst时，如果你在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

导致错误。