什么时候我应该选择桶排序而不是其他排序算法？

Question

桶排序算法什么时候是最好的排序方法？根据数据结构的大小和类型，有没有推荐的使用指南？

Answer 1

存储桶排序是一种基于非比较的排序算法，它假设可以创建一个存储桶数组，并按索引将要排序的项分配到这些存储桶中。因此，作为首先使用存储桶排序的先决条件，您需要有某种方法来获得每个项目的索引。这些索引不能仅仅来自哈希函数；它们需要满足这样的特性:如果任何对象x出现在任何对象y之前，那么x的存储桶索引不能大于y的存储桶索引。许多对象都有这个属性-可以通过查看数字的一些位来对整数进行排序，也可以通过查看前几个字符来对字符串进行排序-但许多对象不这样做。

存储桶排序的优点是，一旦元素被分配到存储桶中，每个存储桶就可以独立于其他存储桶进行处理。这意味着作为后续步骤，您通常需要对比原始数组小得多的数组进行排序。这也意味着你可以对所有的存储桶进行并行排序。缺点是，如果你得到了一个糟糕的分发到桶中，你可能最终会做大量的额外工作，而没有好处或最小的好处。因此，当数据或多或少是均匀分布的，或者存在一种智能的方法来选择基于输入数组的启发式快速集合时，存储桶排序的效果最好。如果有很大程度的并行性，存储桶排序也能很好地工作。

存储桶排序的另一个优点是您可以将其用作外部排序算法。如果你需要对一个大到无法放入内存的列表进行排序，你可以通过RAM对该列表进行流式处理，将这些项目分配到存储在外部文件中的存储桶中，然后对RAM中的每个文件分别进行排序。

以下是存储桶排序的一些缺点：

存储桶排序如上所述，您不能将其应用于所有数据类型，因为您需要一个好的分组方案。

• 存储桶排序的效率对输入值的分布很敏感，因此如果您具有紧密聚集的值，则不值得这么做。

• 在许多情况下，您可以使用存储桶排序，您也可以使用另一种专用排序算法，如基数排序、计数排序或突发排序，以获得更好的存储桶排序performance.

• The性能取决于所选存储桶的数量，与其他算法相比，这可能需要一些额外的性能调整。

我希望这能帮助您了解存储桶排序的相对优点和缺点。最终，确定它是否适合的最好方法是将其与其他算法进行比较，看看它实际效果如何，尽管上面的标准可能会帮助您避免在不太可能工作良好的情况下花费时间进行比较。