python - 最大递归深度误差，与列表理解符号有某种关系

Question

我是 Python 的新手，我被以下问题难住了。

作为速成类(class)的一部分，我使用列表理解编写了一个quicksort 函数，如下所示:

data = [78,3,3526,-12244,9,2,8,6,-84,3642,1,-1234, 234, 23, -1, -11, 34]
pivot = data[0]

def quicksort(lst):
    if len(lst) <= 1:
        return lst
    lessThanPivot = [x for x in lst if x < pivot]
    greaterThanPivot = [x for x in lst if x >= pivot]
    return quicksort(lessThanPivot) + [pivot] + quicksort(greaterThanPivot)

print(quicksort(data))

这会产生以下输出:

Traceback (most recent call last):
File "C:\Program Files (x86)\Microsoft Visual Studio 12.0\Common7\IDE\Extensions\Microsoft\Python Tools for Visual Studio\2.1\visualstudio_py_util.py", line 106, in exec_file
exec_code(code, file, global_variables)
File "C:\Program Files (x86)\Microsoft Visual Studio 12.0\Common7\IDE\Extensions\Microsoft\Python Tools for Visual Studio\2.1\visualstudio_py_util.py", line 82, in exec_code
exec(code_obj, global_variables)
File "C:\Users\user\documents\visual studio 2013\Projects\PythonApplication1\PythonApplication1\quickSortExercise.py", line 12, in <module>
print(quicksort(data))
[...]
File "C:\Users\user\documents\visual studio 2013\Projects\PythonApplication1\PythonApplication1\quickSortExercise.py", line 3, in quicksort
def quicksort(lst):
RuntimeError: maximum recursion depth exceeded

但以下工作正常:

data = [78,3,3526,-12244,9,2,8,6,-84,3642,1,-1234, 234, 23, -1, -11, 34]
pivot = data[0]

def quicksort(lst):
    if len(lst) <= 1:
        return lst
    lessThanPivot = [x for x in lst[1:] if x < pivot]
    greaterThanPivot = [x for x in lst[1:] if x >= pivot]
    return quicksort(lessThanPivot) + [pivot] + quicksort(greaterThanPivot)
print(quicksort(data))

唯一的区别是 lst[1:] 而不是 lst

关于列表理解的文档似乎没有解决这个问题。

Answer 1

您永远不会在第一个片段中更改您的数据中心，因此 lessThanPivot 的“小于”分区再次是 lessThanPivot(即等效列表)和“greaterThanPivot 的“大于”分区再次为 greaterThanPivot，导致无限递归。

您的第二个代码段“有效”，因为 lst[1:] 不断修剪列表的第一个元素，因此每次重复时列表都会变小，最终导致基本情况。然而，最终的答案是不正确的。

简而言之，在每个 分区之前选择一个新的主元。