为什么这个python版本的快速排序会出现运行时错误

Question

def quickSort(x):
if len(x) <= 1:
return x
mid = x[0]
l = filter(lambda k: k<=mid, x)
r = filter(lambda k: k>mid, x)
return quickSort(l)+quickSort(r)
b = [3,2,1,5,4]
quickSort(b)

然后我得到了这个错误：

运行时错误：超过的最大递归深度

Answer 1

您需要从两个较小的部分中取出分区元素：

def quickSort(x):
if len(x) <= 1:
return x
mid = x[0]
l = filter(lambda k: k<mid, x)
r = filter(lambda k: k>mid, x)
return quickSort(l) + [mid] + quickSort(r)

否则，您可以获得无限递归，因为子问题不会变得更小。