0

我在这里使用这个程序作为参考，看看算法是如何实现的。除了这一部分，我理解了大部分内容： 

/*
 * update all the buckets. If bucket[8] has 2,
 * then there are 2 elements present till bucket 8
 */
for (i = 1; i < 10; i++)
        bucket[i] = bucket[i] + bucket[i-1];

我不明白作者在那个循环中在做什么。有人可以解释发生了什么吗？
是的，我正在用纸笔看看发生了什么。只是想我可以澄清一下

4

2 回答 2

2

这个函数是取累积和，现在 bucket[i] 包含它自己和它之前的所有桶的累积和。评论的意思是 bucket[8] == 2 意味着桶 0 到 8 的总和 = 2

编辑：我个人认为http://www.youtube.com/watch?v=Nz1KZXbghj8&noredirect=1有一个很好的基数排序解释。

于 2013-09-18T07:16:17.850 回答
1

如果您对该行感到困惑，您可以阅读有关计数排序的内容。了解有关基数排序的重要事项之一是它不会自行排序。有一个必须使用的子算法，它通常是计数排序。

您提供的链接并没有说明这一点，我认为这是一个重要的混淆。当你阅读

“在第一次通过时，根据最低有效位对所有数据进行排序”

它没有告诉你如何排序。您可以使用任何其他稳定排序进行排序，并且代码会发生巨大变化。

所有这一切都是说，如果这是您不理解的唯一行，那么您就已经弄清楚了基数排序。阅读有关计数排序以了解它的工作原理，并确保您了解为什么它是作为基数排序的子程序的好选择。

于 2013-09-18T07:32:05.167 回答