桶排序和基数排序有什么区别？

桶排序和基数排序是亲密的表亲;桶排序从MSD到LSD，而基数排序可以在“方向”（LSD或MSD）中进行。两种算法如何工作，特别是它们有何不同？桶排序和基数排序有什么区别？

2010-12-16 Lazarus

RadixSort和BucketSort的初始合格完全相同。取决于最大数字中的位数，这些元素被放入增量范围（例如0-10,11-20，... 90-100）的buckets（或bins）中。

然而，在下一回合中，BucketSort将这些“桶”排序并将它们附加到一个数组中。然而，RadixSort追加没有进一步排序的桶，并基于数字的第二个数字（十位）来“重新桶”。因此，BucketSort对于'Dense'数组更有效，而RadixSort可以很好地处理稀疏（很好，不完全稀疏但间隔开）数组。

来源

2011-01-06 15:19:45 Akash

您能否扩展此答案以解释为什么这两种方法的时间复杂性不同？即为什么是桶排序O（n + k），但基数排序是O（nk）？ – 2015-02-23 09:24:51

@ShaunBudhram这是一个老问题，但如果有人读这个想知道。从描述中可以看出，桶排序在N上传递一次，然后合并K个桶（桶内的顺序是任意的）。尽管基数排序对每个桶都有一个传递，但在这里我认为排序字符串会是更好的例子，因此您需要执行复杂度为N的K遍。 – 2016-02-28 12:15:11

“BucketSort命令这些”桶“是什么意思？每个桶是用不同的算法或者什么排序的？因为如果您按10秒分组，每个存储桶都没有完全分类。 – mpen 2017-10-24 20:11:34

桶排序和基数排序就像姐妹排序算法，因为它们不是比较排序，总体思路是相似的。而且，它们在实现上都有点抽象。

基数排序：

沙参装置基（二进制，八进制，十进制，等等）。因此，这种排序是为数字（也用于字符串）。这工作时各元件E是像电子_ķ ... E ëË，其中e _我是在一定范围内。（通常为0至在ASCII字符等以十进制0-9或0-255的基座）
然后，它使用稳定子排序算法的k个道次（它必须是稳定否则基数排序赢得不工作）对数字进行排序。这种子排序算法通常是Counting排序或Bucket排序，但是它不能是基数排序本身。
可以从最高有效数位或最低有效位，因为它混洗在每一通（从k以0或0至k）的每个数字
它是一种稳定排序算法开始。

桶排序：

它分离阵列分成更小的组或桶，并将它们个别地使用子排序算法或递归调用自身排序，然后组合结果。例如，通过将球员加入队伍中，然后根据他们的球衣号码排序球员，或将球队从1-30分成1到1-10,11-20,21-30三个球队等类别来排序球员。
组合步骤很简单（与合并排序不同）。只复制每个桶的元件返回到原始排列或与以前的桶的尾加入每个桶的头部（在链表的情况下）
基数/碱可以是一个类型/实例的组/桶的同时排序数字。因此，你能想到MSD基数作为排序
桶排序桶的修改实例不就地但稳定排序算法。但是，某些桶类的变体可能不稳定（如果使用不稳定的子分类算法）

来源

2015-05-15 22:30:12

一些比较好的:) – 2016-05-07 14:17:29

桶排序和基数排序有什么区别？

回答

相关问题