速いソートを書くためのヘルプ

Question

私はJavaアプリケーションを作成しています。 Nodeという名前のクラスがあります。 ArrayListオブジェクトを作成し、そこにいくつかのノードを追加しました。各ノードは整数データと2倍の確率を持つ。 arrayList内のノードをその確率でますますソートする必要があります。私は、以下の方法書かれている：

 private void sort(ArrayList<Node> list2) { 
    int n = list2.size(); 
    for (int i = 1; i < n; i++) { 
     int m = list2.get(i); 
     int j = i - 1; 
     while ((j >= 0) && (list2.get(j).prob > m.prob)) 
      list2.set(j + 1, list2.get(j--)); 
     list2.set(j + 1, m); 
     } 

    } 

をしかし、それは、ソートのための高速な方法ではありません。どのようにしてより速くソートできますか？この目的のためにJavaでCollections.sort（）メソッドを使用できますか？どうやって ？あなたは私を案内してくれますか？

Answer 1

はい、Collections.sort（）を使用できます（また使用する必要があります）。ソートのこの方法は既に最適化されており、おそらくあなた自身を書く可能性の高い実装よりも速く実行されるでしょう。

ただし、コードは現在Collections.sort（）には適用されません。これを行うには、リストに入れるオブジェクトに「データ」と「確率」の両方のフィールドが必要です。

ここでは簡単な例です：

public class DataProbability implements Comparable<DataProbability> { 
    private int data; 
    private double probability; 

    public int getData() { 
     return data; 
    } 

    public double getProbability() { 
     return probability; 
    } 

    public int compareTo(DataProbability pProb) { 
     return Double.compare(getProbability(), pProb.getProbability()); 
    } 
} 

// Later, with your list 
List<DataProbability> lDataList = new ArrayList<DataProbability>(); 
// Add some elements 
Collections.sort(lDataList); 

は、リストをソートする場合、あなたは2つのオプションがあります（ソートする「オブジェクト」はComparableインタフェースを実装するかどうかを確認する

• を、これはどのような私ですただ
• を使用したり、あなたはまた、Collections.sort（）を呼び出すときに使用するコンパレータを指定することができます

Answer 2

はい、Collections.sort()を使用することができます。これはほとんど正しいことです。あなたは少なくともそれから始めて、それが十分に速いかどうかを見るためにそれをベンチマークするべきです。リストに関する詳細情報があれば、よりうまくいくかもしれません（たとえば、「大部分がソートされている」など）が、簡単なアプローチを取ることは良い出発点です。

サンプルコードはあなたの説明に対応していません。ArrayList<Node>と記載されていますが、あなたのコードはArrayList<Integer>です。

Answer 3

ユーザー定義オブジェクトをソートする際に、同等のインタフェースを実装する必要があります。また、equals（）メソッドとhashcode（）メソッドをオーバーライドする必要があります。ただし、プリミティブデータ型オブジェクトのみを含むリストのソートには必要ありません。