寫一個快速排序的幫助

我正在寫一個Java應用程序。我有一個名爲Node的類。我創建了一個ArrayList對象並在其中添加一些節點。，每個節點都有一個整數數據和一個雙重概率。我想要按照它們的概率對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（）方法嗎？怎麼樣？你能指導我嗎？

來源

2010-12-17 Elton.fd

是的，你可以（也應該）使用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);

當排序列表，你有兩個選擇：

確保了「對象」進行排序實現Comparable接口（這是我只是用
或者你也可以指定一個比較調用Collections.sort（）時使用

來源

2010-12-17 13:47:03 bug

+1，給出了實現Comparable的代碼示例。 – Ibrahim 2010-12-17 14:05:35

感謝您的明智回答 – 2010-12-17 16:49:48

是的，你可以使用Collections.sort() - 這幾乎肯定是正確的做法。您至少應該先做這件事，然後進行基準測試，看看它是否足夠快。如果你有更多的關於清單的信息（例如，它可能是「大多數排序」），但採取簡單的方法是一個很好的起點，你可能會做得更好。

請注意，您的示例代碼與您的描述不符 - 您已描述了ArrayList<Node>，但您的代碼僅適用於ArrayList<Integer>。

來源

2010-12-17 13:37:03

對不起，我已經複製了一個錯誤的代碼。我編輯了 – 2010-12-17 13:42:02

當對用戶定義的對象進行排序時，需要實現可比較的接口。你也需要重寫equals（）和hashcode（）方法。但是，對於僅包含原始數據類型對象的列表進行排序不是必需的。

來源

2010-12-17 14:00:11 9ikhan

寫一個快速排序的幫助

回答

相關問題