写一个快速排序的帮助

我正在写一个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

写一个快速排序的帮助

回答

相关问题