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

Question

什么时候桶排序算法是用于排序的最佳方法？是否有基于数据结构的大小,类型使用它们的推荐指南？

Answer 1

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

存储桶排序的优点是,一旦将元素分配到存储桶中,每个存储桶就可以独立于其他存储桶进行处理.这意味着您经常需要将比较小的数组排序为后续步骤而不是原始数组.这也意味着您可以将所有存储桶彼此并行排序.缺点是,如果你在桶中分配不好,你可能最终会做大量的额外工作,没有任何好处或最小的好处.因此,当数据或多或少均匀分布时,或者根据输入数组提供快速启发式设置的智能方式选择存储桶时,存储桶排序效果最佳.如果您具有很大程度的并行性,则存储桶排序也很有效.

存储桶排序的另一个优点是可以将其用作外部排序算法.如果您需要对如此巨大的列表进行排序而无法将其放入内存中,则可以通过RAM流式传输列表,将项目分发到存储在外部文件中的存储桶中,然后单独对RAM中的每个文件进行排序.

以下是桶排序的一些缺点:

• 如上所述,您无法将其应用于所有数据类型,因为您需要一个良好的分组方案.
• 存储桶排序的效率对输入值的分布很敏感,因此如果您有紧密集群的值,则不值得.
• 在许多情况下你可以使用桶排序,你也可以使用另一种专门的排序算法,如基数排序,计数排序或burstsort,并获得更好的性能.
• 存储桶排序的性能取决于所选存储桶的数量,与其他算法相比,这可能需要一些额外的性能调整.

我希望这有助于您了解铲斗分类的相对优势和劣势.最终,确定它是否合适的最佳方法是将其与其他算法进行比较,看看它实际上是如何做的,尽管上述标准可能会帮助您避免花时间在不太可能正常工作的情况下进行比较.