计数排序 - 不明白为什么我的算法不起作用

Question

在过去的 3 个小时里，我正在努力构建计数排序算法。我理解这个概念，我可以在纸上使用计数排序算法对数组进行排序，没有问题。问题是当试图将纸上的步骤翻译成代码时，我的算法失败了。程序因错误消息“索引超出范围”而中断。为了理解错误，我使用了打印函数来查看每次迭代的结果。结果不正确。算法有什么问题？

def count_sort(array):

    minArr = min(array)

    maxArr = max(array)

    sumArray = [0 for _ in range(minArr, maxArr+1)]

    for i in range(len(array)):

        sumArray[array[i] - 1] += 1

    print(sumArray)

    sumCount = []

    sumCount.append(sumArray[0])

    for i in range(1, len(sumArray)):

        sumCount.append(sumArray[i] + sumCount[i-1])

    print(sumCount)

    sortedArray = [0 for _ in range(len(array))]

    for i in range(len(array)):

        sortedArray[sumCount[array[i]] - 1] = array[i]

        sumCount[array[i]] -= 1

    print(sortedArray)

Answer 1

你需要更换sortedArray[sumCount[array[i]] - 1] = array[i]sumCount[array[i]] -= 1经过sortedArray[sumCount[array[i]-1]-1] = array[i]sumCount[array[i]-1]-= 1