0

いらっしゃいませ。配列を使用して通過する基数ソート方法がありますが、空のキューに格納する別の配列 (ビン) が必要です。ビンのキューを作成する方法について混乱しています。呼び出されたときに各桁の場所を見つける findPlace メソッドもあります。それで、ここに私が得たものがあります。誰かが私が欠けているものを見つけるのを手伝ってくれますか? お時間をいただきありがとうございます。

public static void radix(int [] list){
       int [] bin = new int[10]; 
      ArrayQueue<Integer> part = new ArrayQueue<Integer>(); // EDIT What would I do with this queue?? 
      int num = 0; 
         for(int i=0;i<list.length;i++)
         {
            bin[i] = 0;  
          }

            for(int pass=0;pass<list.length;pass++)
           {
                for(int num=0;num<list.length;num++)
               {
                       int digit=findPlace(bin[pass], num);
                 }

                  bin[digit].add(list[num]); // add to the bin
            }
              // Put back into list
               for(int h=0; h<10; h++)
               {
                    while(!bin[h].isEmpty())
                    {
                       list[num] = bin[queueNum].remove();
                     num++;
                    }
              }
        }


public static int getPlace (int x, int place)
    {return x/place % 10;}

バケットを見つける方法も作成しました。それで、それを配列に入れる方法を知る必要があります。これを行うだけですか? part.add(getPlace(x, 場所));?

4

1 に答える 1

3

あなたの配列は、binあなたがしたいという理由だけでキューのようには機能しません:)配列にはadd()やのようなメソッドはありませんremove()。これを修正するには、次の 2 つの方法があります。

  • 自分でキューの適切な処理をプログラムします。キューは、配列と、その配列への 2 つのポインター (従来は と と呼ばれていました) で構成されheadますtail。追加および削除する独自のメソッドを作成する必要があります。これは、配列とポインターを操作し、空のキューまたはオーバーフローしたキューを処理します。

  • Java の組み込み Queue クラスを使用します。これは、ライブラリの Javadocs に記載されています。ただし、割り当てが独自のキューを作成することを意図しているかどうかはわかりません。

別の詳細で更新します。

数値から 1 桁を抽出する方法を尋ねました。ウィキペディアの記事で提案されているように、最下位桁 (LSD) から作業するのが最も簡単です。それを行うには：

  • 最後の桁を抽出するには、次のようにしますdigit = number % 10(これがモジュロ演算です)。0 から 9 までの整数を取得します。
  • 最後の桁を取り除くには、単純に 10 で割ります。その後、別の桁を取り除くことができます。
  • 数値の最後の n 桁を何度も確認する必要があるため、この機能を別のメソッドに配置することをお勧めします。

0 から 9 までを使用して、番号を配置する適切なキューを選択できます。

すべての番号を 10 個のバケットにキューイングし終わったら、そこからそれらを 1 つのリストにコピーする必要があります。次に、処理していない数字が残っている限り繰り返します。

于 2009-11-15T06:56:17.880 に答える