计数排序--我不明白为什么我的算法不能工作
计数排序--我不明白为什么我的算法不能工作
提问于 2018-10-30 04:22:03
在过去的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)回答 2
Stack Overflow用户
发布于 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] = xStack Overflow用户
发布于 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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53053255
复制相关文章
相似问题
腾讯云开发者
