有人能解释一下存储桶排序的实现是如何工作的吗？

Question

我很难理解存储桶排序的基本概念，我希望有人能向我澄清排序算法到底是做什么的，以及它如何在O(N)时间内完成期望的结果(对内部容器进行排序)。此外，由于这似乎相当快，其他排序算法(如冒泡、插入或选择)有什么优势，可以说服人们使用它们而不是桶排序？

这是我在网上找到的算法的一个实现。如果有人能在他们的解释中引用这一点，我将不胜感激。

void binsort(std::vector<std::size_t>& A){
    std::vector<std::vector<std::size_t>> B(MAX + 1);
    for(std::size_t i = 0; i < SIZE; ++i){
        B[A[i]].push_back(A[i]);
    }
    std::size_t current = 0;
    for(std::size_t i = 0; i < MAX; ++i){
        for(auto item : B[i]){
            A[current++] = item;
        }
    }
}

谢谢你的帮助。

Answer 1

这是Wikipedia提供的解释。我希望这就足够了。

存储桶排序是一种通过将数组划分为多个存储桶来实现的排序算法。然后，使用不同的排序算法或通过递归地应用桶排序算法，对每个桶进行单独排序。它是一种分布排序，在最高到最低有效数字中是基数排序的近亲。桶排序是归类排序的一种推广。由于桶排序不是比较排序，因此Ω( not )下限不适用。计算复杂性估计涉及到存储桶的数量。

存储桶排序的工作方式如下：

1. 设置一个最初为空的“bucket.
2. Gather：”数组。
3. 散布:遍历原始数组，将每个对象放入其存储桶中。
4. 对每个非空的存储桶进行排序。按顺序访问存储桶并将所有元素放回原始数组中。

Answer 2

给出的解释很酷。那么，如果我们有负数，我们该如何处理这种情况？一种方法是为负数保留一个单独的遗愿清单。

想象一下这样的数据集：{ -5，-6，5，3，6，-4 }

下面是我们的“遗愿清单”：

列表1：

0: {0}
1: {0}
2: {0}
3: {1}
4: {0}
5: {1}
6: {1}

存储桶列表2：

-1: {0}
-2: {0}
-3: {0}
-4: {1}
-5: {1}
-6: {1}

因此，如果我们的情况只涉及整数，我们的遗愿列表甚至不需要包含其他列表。它们可以只是列表。

Answer 3

要处理负数的情况，可以选择最小的负数，并将该数字添加到数组中的每个元素。{-5,-6,5,3,6,-4}具有最小的元素-6。将绝对值-6添加到数组中。数组现在是桶，然后用桶数组对其进行排序，桶数组变成{0,1,2,9,11,12}，为了得到最终结果，将-6添加到{1,0,11,9,12,2}，即{-6,-5,-4,3,5,6}。在性能方面，这是可以的，因为对数组的最低范围的减法和加法是O(N)。