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

Question

这让我困惑了一段时间。我想知道应该使用桶内排序的场景过度计数排序(或反之亦然)。

Answer 1

这两个页​​面提供了关于这两种类型的一些信息。

• Counting sort
• Bucket sort

关于计数排序:

Because counting sort uses key values as indexes into an array, it is not a comparison sort, and the Ω(n log n) lower bound for comparison sorting does not apply to it.1 Bucket sort may be used for many of the same tasks as counting sort, with a similar time analysis; however, compared to counting sort, bucket sort requires linked lists, dynamic arrays or a large amount of preallocated memory to hold the sets of items within each bucket, whereas counting sort instead stores a single number (the count of items) per bucket.[4]

关于桶排序:

Bucket sort can be seen as a generalization of counting sort; in fact, if each bucket has size 1 then bucket sort degenerates to counting sort. The variable bucket size of bucket sort allows it to use O(n) memory instead of O(M) memory, where M is the number of distinct values; in exchange, it gives up counting sort's O(n + M) worst-case behavior.