存储桶排序实现

Question

我必须实现一个桶排序，以便它对带有随机生成的数字在 0 到 100 之间的size = 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;

在您的情况下，范围为 100。

复杂度：O（n）

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