使用基数排序进行排序

Question

我正在阅读 radix sort 来自 this site 我在第 3 次感到困惑 for loop:

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 到那时才是正确的位置。

使用基数排序进行排序

Sorting using radix sort

java

radix-sort