algorithm - 什么是桶排序的好散列函数？

Question

首先，大多数声称实现了桶排序的地方实际上都是在实现计数排序。我的问题是关于在 Geek Viewpoint 上实现的桶排序和 Wikipedia .我真的不了解/喜欢 Geek Viewpoint 上的散列函数，我也不了解维基百科上的散列函数。有人可以解释一种更简单的方法来为桶排序创建一个好的哈希函数吗？一般人都能理解和记住的东西。

Answer 1

我认为没有普遍适用的哈希函数，这是桶排序的陷阱。如果散列生成大小大致相等的存储桶，则该散列很好，但这显然取决于您要排序的值的分布。这就是为什么当您对分布有先验知识时，桶排序会如此有效，例如，当您必须按高度对人的记录进行排序时。

此外，桶排序的最坏情况不是计数排序，正如 Geekview 链接错误地暗示的那样。最坏的情况(关于时间复杂度)是所有元素都进入同一个桶。

当然，计数排序是一种桶排序，特别是哈希h(x) = x的桶排序。计数排序的不同之处在于，一旦您知道您的桶将永远只保存一个值，您实际上并不需要桶来存储元素本身，只需要它们的计数。