HeapSort 代码适用于较小的数组，但不适用于较大的数组

Question

def heapSort(arr, end):
    '''Heap Sort Algorithm'''
    '''Average Case: O(n*log(n))'''
    '''Worst Case: Θ(n*log(n))'''
    '''Best Case: Ω(n*log(n))'''
    if end <= 0 or len(arr) <= 1: #algorithm ends when there's one element or less
        return arr
    buildHeap(arr, end)
    arr[0], arr[end] = arr[end], arr[0]
    end -= 1
    return heapSort(arr,end)
    


def buildHeap(arr, end):
    '''Builds the Max Heap'''
    if end <=0: #recursively max heap half of arr to the start
        return arr

    i = (end-1)//2 #parent
    while i >= 0: #index backwards, swapping the parent with the bigger of each child 
        leftChild = 2*i+1
        rightChild = 2*i+2

        if arr[leftChild] > arr[rightChild] and arr[leftChild] > arr[i] and rightChild <= end: #make sure right child is within our end bounds
            arr[i], arr[leftChild] = arr[leftChild], arr[i]

        elif arr[rightChild] > arr[leftChild] and arr[rightChild] > arr[i] and rightChild <= end:
            arr[i], arr[rightChild] = arr[rightChild], arr[i]
        i-=1
    end-=1 
    return buildHeap(arr, end)
from random import randint
A = [randint(1,100) for i in range(20)]
print(A)
print(heapSort(A, len(A)-1))

上面是我下面的堆排序代码，错误发生在我的buildHeap函数（if行）。在所有初始运行中，右边的 child 最终等于数组的长度（而不是 array-1 的长度），因此代码超出了索引范围。奇怪的是，我的 Python 算法实现适用于较小的列表。关于如何修复 and/or 改进我的代码的任何帮助？

Answer 1

您在以下语句中进行 within-bounds 检查为时已晚，因为在进行检查时您已经引用了 arr[rightChild]。你应该首先检查——作为守卫——然后才访问arr[rightChild]。所以替换：

if arr[leftChild] > arr[rightChild] and arr[leftChild] > arr[i] and rightChild <= end: #make sure right child is within our end bounds
    arr[i], arr[leftChild] = arr[leftChild], arr[i]

elif arr[rightChild] > arr[leftChild] and arr[rightChild] > arr[i] and rightChild <= end:
    arr[i], arr[rightChild] = arr[rightChild], arr[i]

与：

if arr[leftChild] > arr[i] and (rightChild > end or arr[leftChild] > arr[rightChild]): 
    arr[i], arr[leftChild] = arr[leftChild], arr[i]

elif rightChild <= end and arr[rightChild] > arr[i]:
    arr[i], arr[rightChild] = arr[rightChild], arr[i]

顺便说一句，您的堆构建函数效率不高。它的时间复杂度为 O(n²)，使用 O(n) 额外（堆栈）space，而这可以在线性时间和常数额外 space 中完成，使用 Floyd's method。

HeapSort 代码适用于较小的数组，但不适用于较大的数组

HeapSort code works on smaller arrays but not bigger ones

python

sorting

algorithm

heap