0

I'm trying to do a radix sort and some algorithms I've seen have a buckets[ ] array that's supposed to hold multiple integers into one index of the bucket array, here is the algorithm I'm referring to:

here is the algorithm I'm referring to

Is it really possible to have multiple integers in one index? And how so?
Or is there a simpler radix sort algorithm out there?

4

5 に答える 5

0

はい、配列に複数を追加することは可能ですが、各項目がではなくでintある配列が必要になります。Objectint

例えば...

// the items to store in the array, which contain 3 ints
public class Bucket {
    int number1 = -1;
    int number2 = -1;
    int number3 = -1;

    public void addInt(int number){
        if (number1 == -1){
            number1 = number;
        }
        else if (number2 == -1){
            number2 = number;
        }
        else if (number3 == -1){
            number3 = number;
        }
    }
}

// the array, as used in other classes
Bucket[] bArray = new Bucket[6]; // 6 items in the array, where each item is a Bucket that contains 3 ints

// assigning ints into the array
bArray[2].addInt(56); // add the int '56' to the bucket at index '2' of the array

// You could also use other Array-like structures
ArrayList<Bucket> bList = new ArrayList<Bucket>();

もちろん、バケットに常に3つ未満のアイテムがあるとは限らない場合は、バケットクラスを変更して、List個別のsではなく配列またはaを変数として使用することができますint。

多次元配列を使用することもできます...

// creating the buckets
int[][] buckets = new int[6][3];

// assigning ints into the array
bArray[2][0] = 56; // add the int '56' to the bucket at index '2' of the array, position '0'

ただし、さまざまなサイズのバケットを試してみると、少し面倒になります。そのためには、さらにエラーチェックを行う必要があります...

  1. バケット内のアイテムにアクセスしようとしても、アイテムは空ではありません
  2. バケットに数値を追加するときは、2次元で空の次の位置を検出する必要があるため、intすでにそこにあるを上書きしないでください。

これらの理由がある場合は、多次元配列ではなくオブジェクトベースの配列を使用することをお勧めします。

于 2012-11-30T01:33:12.577 に答える
0

2つのケースでバケットが作成されます

  • 数字は一意ではありません
  • 基数ソートは、次の桁に進む前に、各桁の位置（小数点以下の場合は1、10、100）でソートします。したがって、最初の桁でのソートが一致する場合は、003と019になります。

最初のケースは、実際には2番目のケースの単なる退化したケースです。

数字を並べ替える順序に応じて、基数ソートのバリエーションがいくつかあることに注意してください。

質問のデータ構造部分に答えすぎます-いいえ、各インデックスに複数の値を格納することはできません。代わりに、各バケットは通常、配列のサブシーケンスとして表されます。各バケットは、開始のオフセットで表されます（終了は暗黙的に指定できます）。

于 2012-11-30T01:34:23.433 に答える
0

abucketは、int[]（またはList複数のアイテムを保存できるもの）自体になります。

1 つのインデックスに複数のものを入れることはできません。

int[] array = new array[6];
int value = array[5];

複数の int がある場合、 は機能しなくなります。

最も簡単なのは、おそらくint[][]配列を使用することです。左のボックスの各インデックスは、配列全体を参照します。これらの配列の長さも異なる場合があります。

Java ジャグ配列

于 2012-11-30T01:43:52.133 に答える
0

バケットをリストまたは配列として表す可能性に加えて、配列スライスを使用することもできます。この場合、宛先配列は入力配列と同じ合計サイズになります。たとえば、バケット 0 に 2 つの要素、バケット 1 に 2 つ、バケット 2 に 3 つ、バケット 3 に 1 つ、バケット 5 に 2 つの要素があります。

Bucket 0 : d[0], d[1]
Bucket 1 : d[2], d[3]
Bucket 2 : d[4], d[5], d[6]
Bucket 3 : d[7]
Bucket 5 : d[8], d[9]

このようにすると、ソートは各バケットの次のインデックスを追跡する必要があります。

于 2012-11-30T02:06:19.233 に答える
0

うわー、配列とリストは基数ソートを実装する方法ではありません。はい、リストは機能しますが、遅くなります。私がそれを行ったとき、マージソートよりも遅くなりました。最良の方法は、各バイトごとのカウントソートの一部として頻度配列を実装することです。並列ソートに関してのみ、コードをここに投稿しました。それが役に立てば幸い。

于 2012-12-17T22:07:44.503 に答える