桶排序的近乎完美的分布模型

Question

我试图理解桶排序的算法，我突然想到，如果没有正确的分布模型，我们可以得到 O(n^2) 的复杂度。相当多的网站的桶数等于数组的大小（比如'n'）并使用算法

std::vector<float> bucket[n];
for (int i = 0; i<n; i++){
  bucket[(array[i]*n)/(MAX_ELEMENT_IN_INPUT_ARRAY+1)].push_back(array[i]);
}

我知道整数可以是随机的，没有完美的哈希算法，但我不太明白上述算法如何将元素平均分配到各自的桶中。我是否遗漏了一个直接的逻辑？

Answer 1

以上代码不保证均匀分布。例如，假设您有一个包含 n 个元素的输入数组，数字 1、2、4、8、16、32、...、2^n-1。现在，让我们考虑一下这些元素的最终位置。让我们选择一个元素，比如 2^k。它的桶索引由

给出

2^k · n / (2^n-1 + 1)

这里引起警报的原因是1 / (2ⁿ - 1) 与n 相比是一个非常非常小的数字。因此，我们预计大多数元素将被放入非常低的桶数中，并且我们的分散性会很差。

让我们在 1、2、4、8、16、32、64、128 上试试这个。我们将有 8 个桶。元素映射如下：

1 被放入存储桶 1 * 8 / 129 = 8 / 129 = 0
2 被放入存储桶 2 * 8 / 129 = 16 / 129 = 0
4 被放入存储桶 4 * 8 / 129 = 32 / 129 = 0
8 被放入桶中 8 * 8 / 129 = 64 / 129 = 0
16 被放入桶中 16 * 8 / 129 = 128 / 129 = 0
32 被放入桶中 32 * 8 / 129 = 256 / 129 = 1
64 被放入桶中 64 * 8 / 129 = 512 / 129 = 3
128 被放入桶中 128 * 8 / 129 = 1024 / 129 = 7

如您所见，这里的八个元素中有五个被放入桶 0，并且大部分桶都未使用。

更一般地说，如果您有 n 个元素具有此序列，则只有桶 n - 1、(n - 1) / 2、(n - 1) / 4、(n - 1) / 8 等会得到用过的。只有大约 log n 个这种形式的桶，这意味着大约 n - log n 个元素将被放入桶 0 中，只有大约 log n 个元素会在其他桶中。

据我所知，没有一种公式可以始终为您提供良好的分布。如果您假设数字在一个区间内均匀分布，则此处给出的公式很有效，并且如您所见，如果您给出指数分布的数字，您最终会得到非常糟糕的最坏情况行为。

桶排序的近乎完美的分布模型

Near perfect distribution model for Bucket Sort

sorting

algorithm

bucket-sort