c++ - 桶排序和计数排序的场景

Question

这让我困惑了一段时间。我想知道在桶排序中应该使用计数排序（或反之亦然）的场景。

Answer 1

这两个页面提供了有关这两种排序的一些信息。

• 计数排序
• 桶排序

关于计数排序：

因为计数排序使用键值作为数组的索引，所以它不是比较排序，比较排序的 Ω(n log n) 下限不适用于它。1桶排序可用于许多与计数排序相同的任务，具有相似的时间分析；然而，与计数排序相比，桶排序需要链表、动态数组或大量预分配的内存来保存每个桶内的项目集，而计数排序则在每个桶中存储单个数字（项目数）。 4]

关于桶排序：

桶排序可以看作是计数排序的推广；实际上，如果每个桶的大小为 1，那么桶排序会退化为计数排序。桶排序的可变桶大小允许它使用 O(n) 内存而不是 O(M) 内存，其中 M 是不同值的数量；作为交换，它放弃了计数排序的 O(n + M) 最坏情况行为。