超过了快速排序最大递归深度

Question

我已经实现了一个快速排序算法来练习Python，下面是我的代码：

def sort(array):   
    if len(array) > 1:
        pivot = array[0]
        left = []
        right = []
        equal = []
        for x in array:
            if x < pivot:
                left.append(x)
            elif x == pivot:
                equal.append(x)
            else:
                right.append(x)
        return sort(left)+equal+sort(right)
    return array

现在，算法运行得很好，但如果我删除equal列表并像这样循环：

    for x in array:
        if x < pivot:
            left.append(x)
        else:
            right.append(x)
    return sort(left) + sort(right)

当我尝试对right列表进行排序时，我得到了最大递归深度错误。这并不是因为这个列表也包含相等的元素，我用非常小的列表测试了它。我觉得这对我来说将是一个非常愚蠢的错误，但到目前为止我还没有找到它。

Answer 1

它看起来可能不需要equal列表，但它的存在至关重要。通过将到达那里的元素放入right列表中，可以强制算法将sort()保留为已排序的元素。这就是为什么超过了递归限制的原因。

通过在函数的开头添加print "sorting", array，您可以看到发生了什么：

>>> sort([3,1,2])
('sorting ', [3, 1, 2])
('sorting ', [1, 2])
('sorting ', [])
('sorting ', [1, 2])
('sorting ', [])
('sorting ', [1, 2])
('sorting ', [])
... etc. until crash

Answer 2

枢轴始终作为第零个元素进入right，并在right上递归时再次被选中。由于right还包含等于或大于该值的所有元素，因此下一个调用将把所有当前元素放入新的right中。

如果pivot是列表中唯一最大的项目，它只会减少到一个元素-这最终意味着，在中，除了您的列表没有重复并且已经按降序排序之外的任何其他情况，您都将无限期地递归。

您不需要有一个equal列表，但您至少需要从递归中去掉所选的枢轴，所以下一次调用会选择一个不同的枢轴。所以选择这种方式：

pivot = array.pop(0)

并调整排序列表的重建：

return sort(left) + [pivot] + sort(right)