Javaで基数ソートを実装する - かなりの質問

Question

私のエクササイズでは明確に述べられていませんが、私はRadix sortを再帰的に実装することになっています。私は数日間仕事に取り組んできましたが、残念ながらごみを生産することしかできませんでした。我々は2つの方法で作業する必要があります。ソートメソッドは、0から999の範囲の数字と私たちが見ている数字を持つ特定の配列を受け取ります。ここでは配列内の数値を分配するために2次元の行列を生成することになっています。したがって、たとえば、523は5行目に配置され、27は027と解釈されるため、0行目に配置されます。

これを行うには、switch-case-constructの助けを借りて配列の内側に100を置き、残りの部分をチェックし、残りの部分に対して番号を配置します。それで、私は何とか同じ桁の数字だけを含むバケットを構築しようとしました。たとえば、最初の「ラウンド」で同じバケットに237と247が投げられます。私は前に値を入れた "フィールド" - マトリックスの行全体を取ってこれをしようとしました。

putInBucketメソッドでは、私はバケット（私は正しいことをやっていたと思います）を広げ、それを返す必要があります。

申し訳ありませんが、このコードは全体のゴミであることはわかっていますが、おそらく私が何をしているのか理解してくれている人がいるかもしれません。

私はここでバケットをどのように扱う必要があるのか​​分かりませんが、なぜ私はそれらを広げなければならないのか分からず、sort-methodに戻す方法もありません（私はそうする必要があると思います）。

さらなる説明は：

全体のことは、次のように動作するように意図されています。私たちは、0から999までのすべての数は、その最初の数字でソートされているの範囲の整数の配列を取る、前述したように。あなたが0から9の範囲の数字で示されたバケットを持っているとしましょう。バケット5に523を、バケット6に672を入れて並べ替えを開始します。これは、バケットの1つに1つの番号しかない（または全く番号がない）場合には簡単です。しかし、1つのバケツに複数の数値を入れたい場合は、難しくなります（再帰が手に入るかもしれません）。このメカニズムは次のようになります：同じバケットに同じ最初の桁の2つの数値、たとえば237と245を入れます。ここでは同じアルゴリズムでこれらの数値を再度ソートします。つまり、sort-method（何とか）もう一度これらの2つの数字だけを含んでいる配列を使ってもう一度並べ替えることができますが、今度は2番目の数字を調べることで3と4を比較します。このように配列内のすべての数字を並べ替え、ソートされた配列を得るために、最後にバケット9で始まり、すべてをまとめます。バケツ2の場合、アルゴリズムは再帰的なステップを調べ、既にソートされた配列[237、245]を受け取り、すべてを完了するためにそれを配信します。

私自身の問題：

我々はある程度バケツをする必要がある理由私は理解していないと私は記述から、それを把握することはできません。我々がそうするはずであると簡単に述べられている。バケットが0から9の場合、同じバケットの中に2つの数値を入れると、最初の値を上書きすることになるため、内部に別の要素をコピーすることにします。これは新しい拡張バケツを返す必要がある理由かもしれませんが、私はそれについてはわかりません。さらに、私はそこから遠くに行く方法を知らない。私がバケツを伸ばしても、それを古い行列に貼り付け、別の要素をもう一度それにコピーすることはできません。

public static int[] sort(int[] array, int digit) { 

    if (array.length == 0) 
    return array; 

    int[][] fields = new int[10][array.length]; 
    int[] bucket = new int[array.length]; 
    int i = 0; 

    for (int j = 0; j < array.length; j++) { 
    switch (array[j]/100) { 

    case 0: i = 0; break; 
    case 1: i = 1; break; 

    ... 

    } 

    fields[i][j] = array[j] 
    bucket[i] = fields[i][j]; 
    } 
    return bucket; 
    } 

private static int[] putInBucket(int [] bucket, int number) { 

    int[] bucket_new = int[bucket.length+1]; 

    for (int i = 1; i < bucket_new.length; i++) { 
    bucket_new[i] = bucket[i-1]; 
    } 
    return bucket_new; 
    } 

public static void main (String [] argv) { 

    int[] array = readInts("Please type in the numbers: "); 
    int digit = 0; 
    int[] bucket = sort(array, digit); 
    } 

Answer 1

• あなたはそれが
スイッチ/ケースは非常に複雑な方法のように見える
• は私がウィキペディアの説明を読むことをお勧めしますi = array[j] / 100
• 書くことは非常に疑わしいです、ソートに数字を使用していません基数ソート。
• ベース10から数字を抽出する式は(number / Math.pow(10, digit)) % 10です。
• 左から右または右から左に数字を数えることができることに注意してください。
• まず、数字0、次に数字1、次に数字2をソートしたいとします。これを行うソートの最後に再帰呼び出しがあるはずです。
• バケットの配列は2次元である必要があります。次のように呼び出す必要があります：buckets[i] = putInBucket(buckets[i], array[j])。 putInBucketsでnullを処理する場合は、初期化する必要はありません。
• 2dバケット配列と（固定サイズのフィールドではなく）putInBucketが必要な理由は、各バケットでいくつの番号が終了するかわからないことです。
• 第2段階）配列への再帰呼び出し
• は3桁

幸運