sorting - ソート範囲のカウントは常に [0,k] である必要がありますか?

Question

A=[7,9,12,15] という小さな範囲の数字でカウントソートを行うことはできますか? または、小さな範囲は常に [0..k] でなければなりませんか。

[0..15] と言って、配列 A の並べ替えを数えることはできますが、意味がありません。A=[100,750,452] の場合

なので実現可能だと思います。いくつかの入力をお願いします。

Answer 1

あなたの質問はあまり明確ではありませんが、ここにあります。あなたの例から A=[7,9,12,15] 範囲は [0..15] であり、サイズ k=15 (および A[長さ] の別の結果配列の追加スペースが必要です。n (A[長さ] ]) が 4 の場合、全体の実行時間は theta(k + n) になります。ソートのカウントは「時空間のトレードオフ」アルゴリズムですが、あなたのケースで使用すると意味がありません。トレードオフ k=Big-O(n) がある場合は、カウントソートを使用する必要があります.これは、A[] の最大値が A[] のサイズよりも小さいことを意味します.ところで、アルゴリズムはあなたの例をソートすると思います.正しく。