2

我对此算法有疑问:

在此处输入图像描述

(幻灯片取自这里。

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]++ 在那里做什么。(<-main question)我知道在计数数组中引用字母的位置,但是为什么我们也要增加字母呢?我们换了字母吗?谢谢。

感谢任何帮助。

4

1 回答 1

1

它看起来像一个错字:它应该是:

temp[count[a[i]]++]

下一个元素应该进入下一个空白区域

在 step1 准备添加type_i计数cnt_{i+1},这样为type_i元素腾出空间......

step2 是计数的前缀

step3 使用计数作为R索引指针并将所有元素从其发送a到其最终目的地

在这一步保持不变:

  • count[ x ]指向下一个type_x可以放置元素的空白空间(或者x输入中没有更多元素)
于 2013-08-26T22:21:48.890 回答