方案爲水桶排序和計數排序

Question

這一直困惑了我一段時間。我想知道在桶類別應該使用 超過計數排序（或副詩）的情況。

Answer 1

這兩頁提供了兩種排序信息。

• Counting sort
• Bucket sort

關於計數排序：

由於計數排序使用密鑰值作爲索引到一個數組，它是 不是比較排序，並且用於比較的Ω（n log n）下界 排序不適用於它。 1桶排序可用於許多與計數排序相同的任務，具有類似的時間分析功能;然而，與計數排序相比，桶排序需要鏈接列表， 動態數組或大量的預分配內存來保存每個桶中的 組項目，而計數排序替代地存儲 單個數字（項目數）每桶。[4]

關於桶排序：

桶排序可以看作是計算排序的推廣;實際上，如果每個存儲桶的大小爲1，則 然後存儲桶排序退化爲計數 排序。桶排序的可變桶大小允許其使用O（n） 存儲器而不是O（M）存儲器，其中M是不同的 值的數目;作爲交換，它放棄了計數排序的O（n + M）最差情況 行爲。