52

桶排序和基数排序是近亲。桶排序从 MSD 到 LSD，而基数排序可以在两个“方向”（LSD 或 MSD）上进行。两种算法如何工作，特别是它们有何不同？

4

2 回答 2

48

两者的初始传递RadixSort和BucketSort完全相同。根据最大数字中的位数，将元素放入buckets（或bins）增量范围（例如 0-10、11-20、... 90-100）中。

然而，在下一轮中，BucketSort将这些“桶”排序并将它们附加到一个数组中。但是，RadixSort在不进一步排序的情况下附加存储桶，并根据数字的第二个数字（十位）“重新存储”它。因此，BucketSort 对于“密集”数组更有效，而 RadixSort 可以很好地处理稀疏（嗯，不完全稀疏，但间隔）数组。

于 2011-01-06T15:19:45.010 回答
26

Bucket Sort 和 Radix Sort 类似于姐妹排序算法，因为它们不是比较排序，并且总体思路相似。而且，它们在实现上都有点抽象。

基数排序：

  • 基数表示基数（二进制、八进制、十进制等）。因此，此排序适用于数字（也用于字符串）。这适用于每个元素 E 类似于 e k ...e 2 e 1 e 0，其中 e i在某个范围内。（通常从 0 到十进制的 0-9 或 ASCII 字符的 0-255）

  • 然后它使用 k 次稳定子排序算法（它必须是稳定的，否则基数排序将不起作用）对数字进行排序。这种子排序算法通常也是计数排序或桶排序，但它本身不能是基数排序。

  • 您可以从最高有效数字或最低有效数字开始，因为它会随机播放每遍中的每个数字（从 k 到 0 或从 0 到 k）

  • 是一种稳定的排序算法。

桶排序：

  • 它将数组分成更小的组或桶，并使用子排序算法或对自身的递归调用对它们进行单独排序，然后组合结果。例如，通过将球员添加到球队的存储桶中，然后按球衣号码对他们进行排序，或者将数字从 1-30 排序到 1-10、11-20、21-30 的 3 个存储桶中。

  • 合并步骤很简单（与合并排序不同）。只需将每个桶的元素复制回原始数组或将每个桶的头部与前一个桶的尾部连接（在链表的情况下）

  • 在对数字进行排序时，基数/基数可以是组/桶的类型/实例。因此，您可以将 MSD 基数视为桶排序的修改实例

  • 桶排序不是就地但稳定的排序算法。但是，桶排序的某些变体可能不稳定（如果您使用不稳定的子排序算法）

于 2015-05-15T22:30:12.517 回答