バケットソートの実装

Question

ので、それは0から100の私のバケットの間でランダムに生成された数字でsize = 100で配列をソートすることを次のとおりです。

Bucket0: (0<=x<10) 
Bucket1: (10<=x<20) 
. 
. 
. 
Bucket9: (90<=x<100) 

今、私は背後にある理論を理解しますバケットソートでは、個々のバケットに要素を挿入しますが、実際にバケットを作成する方法はわかりません。バケットを配列そのものとして配列Bを作成しますか？または、整数を使ったバケットソートを実装する標準的な方法ですか？

私はちょうど正しい方向に微調整が必​​要です。何か助けてくれてありがとう！

Answer 1

はい。
長さ101の別の配列（bとも言う）を宣言する必要があります。長さは番号の範囲とその範囲です。

最初の配列と各セルについて、すべての番号k（0 < = k < = 100）を見つけたら、b [k]を++にする必要があります。次のようなものがあります。b[a[i]]++;

ここでは、kが最初の配列に何回出現したかを表す配列bがあります。あなたのケースで、範囲は100

複雑ですが

for(int i = 0; i <= RANGE; i++) 
    for(int j = 0; j < b[i]; j++) 
     a[p++] = i; 

：：O（n）は、我々は代わりに、配列を使用する1つの変数でこれを実装することができ

お知らせ当社は、最初の配列を上書きすることができますこれは同じことをしていますが、毎回違う数字になります。 多くは保存しませんが、スペースの複雑さを少し軽減します。