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

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