Laz*_*rus 44 language-agnostic sorting algorithm radix-sort bucket
铲斗分类和基数排序是近亲; bucket sort从MSD到LSD,而radix sort可以同时进入"方向"(LSD或MSD).两种算法如何工作,特别是它们有何不同？
小智 42
两者的初始通RadixSort和BucketSort是完全一样的.元素放入buckets(或bins)增量范围(例如0-10,11-20,... 90-100),具体取决于最大数字中的位数.
然而,在下一次传递中,BucketSort命令这些"桶"并将它们附加到一个阵列中.但是,RadixSort根据数字的第二个数字(十个位置),在没有进一步排序的情况下附加存储桶并"重新存储"它.因此,BucketSort对于'Dense'阵列更有效,而RadixSort可以很好地处理稀疏(井,不完全稀疏但间隔开)的阵列.
dev*_*kit 21
Bucket Sort和Radix Sort就像姐妹排序算法,因为它们不是比较排序,一般的想法是类似的.而且,它们在实现中都有点抽象.
基数排序:
基数表示基数(二进制,八进制,十进制等).因此,此排序用于数字(也用于字符串).这适用于每个元素E类似于e k ... e 2 e 1 e 0,其中e i在某个范围内.(通常为0到十进制的基数,如十进制的0-9或ASCII字符的0-255)
然后它使用稳定的子排序算法的k遍(它必须是稳定的,否则Radix排序将不起作用)来对数字进行排序.这种子排序算法通常也是Counting sort或Bucket sort,但它不能是Radix排序本身.
您可以从最高有效数字或最低有效数字开始,因为它会将每个传递中的每个数字混洗(从k到0或0到k)
这是一种稳定的排序算法.
铲斗分类:
它将数组分成较小的组或桶,并使用子排序算法或对其自身的递归调用对它们进行单独排序,然后组合结果.例如,通过添加到他们团队的桶中对玩家进行排序,然后根据他们的球衣号码或者将数字从1-30分类到1-10,11-20,21-30的3个桶中进行排序.
该组合的步骤是微不足道的(不像归并排序).只需将每个桶的元素复制回原始数组,或者将每个桶的头部与前一个桶的尾部相连(如果是链接列表)
在对数字进行排序时,基数/基数可以是组/桶的类型/实例.因此,您可以将MSD基数视为桶排序的修改实例
铲斗排序不是就地而是稳定的排序算法.但是,存储桶排序的某些变化可能不稳定(如果使用不稳定的子排序算法)