java - 使用基数排序进行排序

Question

我正在阅读 this site 中的基数排序我对第三个 for 循环感到困惑:

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

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

Answer 1

因为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 这是正确的位置。