在Python中实现堆排序算法在运行时接收递归错误

Question

我试图实现堆排序算法来对列表进行排序，但是接收到以下错误代码: RecursionError:最大递归深度超过了请告诉我，如果发现任何问题，我将在下面发布函数和助手函数如下：

def heap_sort(A):
    heap_size = _build_max_heap(A)
    for i in range(heap_size // 2, -1):
        A[0], A[i] = A[i],A[0]
        heap_size = heap_size - 1
        _max_heapify(A,heap_size, I)

def _build_max_heap(A):
    heap_size = len(A)
    for i in range(heap_size // 2):
        _max_heapify(A,heap_size, I)
    return heap_size

def _left(I):
    return (2*i)+1

def _right(i):
    return (2*i)+2

def _max_heapify(A, heap_size, i ):
     l = _left(i)
    r = _right(i)
    if l < heap_size and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r < heap_size and A[largest] < A[r]:
        largest = r
    if largest != i:
       A[i], A[largest] = A[largest], A[i]
    _max_heapify(A,heap_size, largest)

Answer 1

您的问题是由于您的_max_heapify函数递归地调用了自己，并且不管作为参数传递给它的是什么，它总是调用自己。要使递归工作，必须有这样一个条件，即递归函数不调用自己。您需要修改您的逻辑，以便这是case...so，在某些情况下，通过执行不调用自己的_max_heapify来停止递归。