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

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 个元素会在其他桶中。

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