0

次のコードについて 3 つの質問があります。

  static void funct(int[] list)  {
  final int N = 20;

  java.util.ArrayList[] buckets = new java.util.ArrayList[N];
  for(int i = 0;  i< list.length; i++)  {
     int key = list[i];
     if(buckets[key] = null)
          buckets[key].add(list[i]);
  }
  int k = 0
  for(int i = 0; i <buckets.length; i++)  {
      if(buckets[i] != null)  {
          for(int j = 0; j< buckets[i].size(); j++)
              list[k++] = (Integer)buckets[i].get(j);
      }
  }

}

  1. このアルゴリズムには大きな欠点があります。最大 20 個の要素に対してしか機能せず、複雑さが乏しいということですか?

  2. コードのポイントは、要素のリストをソートすることです-それらは配列に入れられ、次にバケットに入れられ、次にバケットから再び配列に入れられますか?

  3. これは私が困惑しているものです。整数の代わりに別のクラスのオブジェクトを含む配列を渡すことができるように、メソッドをどのように変更しますか?

4

2 に答える 2

2

質問への対処:

  1. それが2つの欠点です。ちょっと複雑なことは気にしないでください。20 を超える要素に対してどのように機能するかを検討してください。バケット ソートの場合、要素の全範囲内での要素の位置に基づいてバケットを選択するという考え方です。バイナリ ベースの整数を使用するコンピューターでこれを行う最も簡単な方法は、数値の最初の数ビット (最上位ビット) を選択し、16 や 32 などの 2 の累乗の数値を使用することです。 and 演算 ( ) を使用して、最上位ビットを取得します (したがって、バケットを計算します&)。その後、ビットを使用してバケットを直接選択できます。

  2. バケット ソートの背後にある考え方は、入力に対する最初のパスに基数ソートの要素を使用し、次に小さいバケット (小さくてソートが容易な場合がある) に対して別のソート (または反復基数ソート) を使用することです。すべてのバケットの連結 (配列に戻すなど) は、複雑さを軽減してソートできます。

  3. バケットの並べ替えは、入力の全範囲を把握することに基づいているため、その範囲をセグメントに分割して、入力を個別に分類できます。これを行う最も簡単な方法は、入力が数値の場合です。入力の順序付けが相対的なものであり、既知の絶対値がなく、1 つの要素が全体の範囲内のどこにあるかを簡単に把握する方法がない場合、バケット ソートは適切ではありません。

于 2009-08-16T16:04:28.113 に答える
0

これは良い宿題の質問です。質問の多くは一種の主観的なものであり、ほぼ間違いなく授業に依存しています。

クラスのレッスンは、ここでの回答よりもインストラクターが探しているものをよりよく理解できるため、自分で試してみることをお勧めします.

その上、教室外の誰かがこれを見た場合、答えは、組み込みの配列ソートを使用して、このゴミを捨てることです!

于 2009-08-16T19:23:56.077 に答える