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

Question

桶排序和基数排序是密切相关的算法；桶排序从高位到低位排序，而基数排序可以在"LSD"或者"MSD"方向进行排序。这两个算法是如何工作的，特别是它们有什么区别？

- Lazarus

Answer 1

< p > RadixSort 和 BucketSort 的初步处理是完全相同的。根据最大数字的位数，将元素放入递增范围的bucket（或bin）中（例如0-10、11-20、... 90-100）。

然而，在下一轮中，BucketSort 对这些“桶”进行排序并将它们附加到一个数组中。然而，RadixSort 将桶进行附加而未进一步排序，并且基于数字的第二位（十位），重新将其装入桶中。因此，BucketSort 在处理“密集”数组时更有效率，而 RadixSort 可以很好地处理稀疏(不算非常稀疏但分散)数组。

- Akash

---

你能否详细说明这两种方法的时间复杂度为什么不同？即为什么桶排序的时间复杂度是O(n+k)，但基数排序的时间复杂度是O(nk)？ - Shaun Budhram

@ShaunBudhram 这是一个老问题，但如果有人正在阅读并想知道答案。从描述中可以看出，桶排序对N进行一次排序，然后合并K个桶（桶内顺序是任意的）。而基数排序对每个桶进行一次排序，这里我认为字符串的排序会是更好的例子，因此您需要进行K次复杂度为N的排序。 - Vojtěch Kaiser

“BucketSort orders up these 'buckets'”是什么意思？每个桶是否都使用不同的算法进行排序？因为如果按10个一组分组，每个桶并没有完全排序。 - mpen

因此，BucketSort 对于“密集”数组更有效率，而 RadixSort 能够很好地处理稀疏数组。为什么会这样呢？ - Shuklaswag

Answer 2

桶排序和基数排序是类似的排序算法，因为它们都不是比较排序，并且它们的一般思想相似。此外，它们在实现上都有点抽象。

基数排序：

• 基数指的是进制（二进制、八进制、十进制等）。因此，这种排序适用于数字（也用于字符串）。当每个元素 E 像 e_k...e₂e₁e₀ 时，其中 e_i 在某个范围内（通常是 0 到一个基数，如十进制中的 0-9 或 ASCII 字符中的 0-255）。

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

• 可以从最高位或最低位开始，因为每次排序都会打乱每个数字（从 k 到 0 或从 0 到 k）。

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

桶排序：

• 它将数组分成小组或桶，并使用子排序算法或对自身的递归调用来逐个对其进行排序，然后合并结果。例如，通过将球员添加到他们团队的桶中，然后按照球衣号码对他们进行排序，或者将从 1-30 范围内的数字排序到三个范围为 1-10、11-20 和 21-30 的桶中。

• 合并步骤是微不足道的（不像归并排序）。只需将每个桶的元素复制回原始数组，或将每个桶的头与前一个桶的尾连接在一起（在链表的情况下）。

基数/进制可以被视为在排序数字时将数字分组/放置的类型/实例。因此，您可以将 MSD 基数排序视为改进版的桶排序。

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

- dev_ankit

---

一个小提示 - 一些 MSD 基数排序的实现不是稳定的。 - Miljen Mikic