c++ - 桶排序实现

Question

我必须实现桶排序，以便它对 size = 100 的数组进行排序，其中随机生成的数字介于 0 和 100 之间。我的桶如下所示:

Bucket0: (0<=x<10)
Bucket1: (10<=x<20)
.
.
.
Bucket9: (90<=x<100)

现在我了解了桶排序背后的理论，我将元素插入到每个单独的桶中，​​但我不明白如何实际创建桶。我是否创建了一个数组，比如 B，其中的桶本身就是数组？还是用整数实现桶排序的更标准方法？

我只需要朝着正确的方向轻推，感谢您的帮助!

Answer 1

是的。
你必须声明另一个长度为 101 的数组(我们可以说 b)。长度代表我们数字的范围。

现在您必须遍历第一个数组和每个单元格，当您找到每个数字 k (0 <= k <= 100) 时，您必须对 b[k] 进行++。像这样: b[a[i]]++;

现在我们有数组 b 代表每个数字 的次数k 出现在第一个数组中。我们可以覆盖第一个数组:

for(int i = 0; i <= RANGE; i++)
    for(int j = 0; j < b[i]; j++)
        a[p++] = i;

在您的情况下，RANGE 是 100。

复杂度:O(n)

请注意，我们可以用一个变量而不是使用数组来实现它，数组做的是同样的事情，但每次都是不同的数字。 节省的不是很多，而是节省了一点空间的复杂性。