问存储桶排序和计数排序的场景

EN

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

• Counting sort
• Bucket sort

关于计数排序的：

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

关于存储桶排序的：

桶排序的可变桶大小允许它使用O(n)内存而不是O(M)内存，其中M是不同值的数量；作为交换，它放弃了计数排序的O(n + M)最坏情况行为。