在过去的3个小时里,我一直在努力构建一个计数排序算法。我理解这个概念,我可以在纸上使用计数排序算法对数组进行排序,没有任何问题。问题是,当试图将纸上的步骤转换为代码时,我的算法失败了。程序中断并显示错误消息"index of of bound“。为了理解错误,我使用打印函数来查看每次迭代的结果。结果是错误的。这个算法有什么问题?
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)
发布于 2018-10-30 05:25:47
这一行是一个问题: arrayi [sumCount[arrayi]- 1] =arrayi
我想你需要把arrayi下移一位?在示例的最后一次迭代中,array4 = 9,因此它尝试设置sortedArray[sumcount9 - 1]。sumcount的索引从0到8,所以9超出了范围。我认为更改为sortedArray[sumcount[arrayi-1]-1]应该可以解决这个问题。
嵌套列表增加了混乱,使其更难发现这一点。如果您遇到问题,请将其分解并使用变量,而不是尝试在一行中完成。更容易调试。添加打印语句以在每个步骤中打印值,以便知道哪个列表和索引会导致越界错误
my_length = len(array)
print(f'for i in range({my_length}):')
for i in range(my_length):
print(f'x = array[{i}]')
x = array[i]
print(f'y = sumCount[{x}] - 1')
y = sumCount[x] - 1
print(f'sortedArray[{y}] = {x}')
sortedArray[y] = x
发布于 2018-10-30 06:06:13
你需要更换
sortedArray[sumCount[array[i]] - 1] = array[i]
sumCount[array[i]] -= 1
通过
sortedArray[sumCount[array[i]-1]-1] = array[i]
sumCount[array[i]-1]-= 1
https://stackoverflow.com/questions/53053255
复制相似问题