Javaで組み込みの比較ソート

Question

ソート後にランダムに選択する項目1〜10を並べ替えると、各数字の重み（すなわち1の重み= 10,2 = 30,4 = 15 、5 '= 35,6' = 10、残りは0）。私はすでに前に重みの合計を計算したと仮定します。今、私は最初にその重みに基づいて数を並べ替える必要があります。そして、リストをもう一度見て、それぞれを合計して（つまり、それぞれの体重を[0,1]で作るために正規化して）割ります。並べ替えとその後、リストを移動するのが遅いので、私はcompareTo()メソッドで重み付けを入れようとしましたので、ソート中は正規化されますが、Collections.sort（）は正しい順序で入れません。任意の提案（自分の効率的なソートアルゴリズムをゼロから書く必要はありません）？私は十分に明確であることを望む。

Answer 1

数字をランダムに選択するには、体重別にソートする必要があると思われる理由は何ですか？

私がやるだろう：

int[] numbers; 
int[] weight; 

int totalweight; 
for (int n : numbers) { 
    totalweight += weight[n]; 
} 

int t = new Random().nextInt(totalWeight); 
for (int n : numbers) { 
    t -= weight[n]; 
    if (t < 0) return n; 
} 

をあなたはrepeatadly同じ配列から選択している場合は、部分和を事前に計算し、それらのバイナリ検索を実行したい場合があります。

あなたの配列は、その長さよりもかなり小さい範囲の数字で構成されている場合、あなたは、ソートを数えるのアイデアを適応させる各明確な数のため、すなわち事前計算部分和とそれらのバイナリ検索を行う可能性があります。

数字や重みに関する事前知識がないと、（他のすべての重みを小さくする可能性があるため）各数値の重みを調べる必要があるため、一般的なアルゴリズムでは少なくともO（n）である。

ただし、追加の制約により、より効率的な実装が可能になります。あなたは数の体重適度に小さい上限がわかっている場合は、A/Rのサンプリングを行うことができます：intsを想定し

int[] numbers; 
int[] weight; 
int maxWeight; 

Random r = new Random(); 
do { 
    c = numbers[r.nextInt(numbers.length)]; 
} while (r.nextInt(maxWeight) > weight[c]); 
return c; 

Answer 2

はListです：

Collections.sort(ints, new Comparator<Integer>() { 
    private int getWeight(Integer i) { 
    int weight = 0; 
    switch(i) { 
     case 1: 
     case 6: weight = 10; break; 
     case 2: weight = 30; break; 
     case 4: weight = 15; break; 
     case 5: weight = 35; break; 
    } 
    return weight; 
    } 

    public int compare(Integer i1, Integer i2) { 
    int w1 = getWeight(i1); 
    int w2 = getWeight(i2); 
    return (w1>w2)?1:(w1==w2?0:-1); 
    }}); 

for(int i:ints) { 
    System.out.print(i+","); 
} 

あなたが列挙型を使用することができます

、またはそれにハッシュマップ数字のストアウェイト、コードは重量ベースの比較を行う方法の例でした。

Answer 3

だけの提案は、メリオンの優れた提案を改善します

あなたがループする必要がある要素が小さくなるように最初の部分がより速くあなたがインデックス作りを作成することができるようにしたい場合。重みを計算するときにN個ごとに、そのインデックスを配列/ハッシュとそれまでの合計でメモします。

ループする番号tを選択すると、索引を参照して要素をそこまで渡すことができます。たくさんのエントリーといくつかのルックアップがあれば時間を節約するかもしれません。