我有一个关于这个算法的问题:
(幻灯片截取 from here. )
int N = a.length;
int[] count = new int[R];
for (int i = 0; i < N; i++)
count[a[i]+1]++;
for (int k = 1; k < 256; k++)
count[k] += count[k-1];
for (int i = 0; i < N; i++)
temp[count[a[i]++]] = a[i]
for (int i = 0; i < N; i++)
a[i] = temp[i];
有人可以详细说明我们将记录从 a[] 移动到 temp[] 的第三个 for 循环吗?
我知道在我们累积计数后它们应该是某种抵消。所以我们可以在temp[]中的适当位置插入字母。
我只是不确定 a[i]++ 在那里做什么。(<-主要问题)我知道引用计数数组中字母的位置,但为什么我们也增加字母?我们换字母了吗?谢谢。
感谢任何帮助。
最佳答案
它看起来像一个错字: 应该是:
temp[count[a[i]]++]
下一个元素应该进入下一个空白区域
在第 1 步中准备将 type_i
计数添加到 cnt_{i+1}
,这样可以为 type_i
元素腾出空间...
step2是计数的前缀
step3 使用计数作为R
索引指针并将所有元素从a
发送到它的最终目的地
在这一步保持不变量:
count[ x ]
指向下一个可以放置type_x
元素的空白区域(或者没有更多的x
元素输入)
关于java - 基数排序代码困惑,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18453886/