java - 使用基数排序排序

我正在从this site读取radix sort，在第三个for loop中我感到困惑：

for (i = n - 1; i >= 0; i--) {
    output[freq[(arr[i] / place) % range] - 1] = arr[i];
    freq[(arr[i] / place) % range]--;
}

为什么当我尝试从0开始时，它们从头开始，却给了我错误的答案？任何解释或解决方案将不胜感激。

最佳答案

因为freq包含范围中每个位置的元素累积数量。也就是说，对于i = 0-9的范围，freq[i]包含放置在位置0, ..., i上的位数。

该算法使用freq跟踪每个位置从初始数组到输出数组需要绘制多少项。

假设输入10,21,17,34,44,11,654,123，对第一个无效数字进行计数排序：

0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:

freq将为：

0: 1
1: 3
2: 3
3: 4
4: 7
5: 7
6: 7
7: 8
8: 8
9: 8

因此，该数组变为10,21,11,123,34,44,654,17。

您需要向后循环，以保持数字的原始顺序具有相同的数字，因为freq是如何构建的。假设您要将34放置在输出的正确位置。根据freq数组，如果向前循环，则将其放置在错误的第7个位置。如果向后循环，则在到达34之前已经放置了654和44，因此freq[4]=5才是正确的位置。

关于java - 使用基数排序排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45997009/