帮助编写快速排序
我正在写一个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()方法来达到这个目的吗？怎么做到的？你能给我带路吗？
回答 3
Stack Overflow用户
发布于 2010-12-17 21:47:03
是的，您可以(也应该)使用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);对列表进行排序时，您有两种选择：
确保要排序的‘
- ’实现可比较接口(这是我刚刚使用的比较接口，您也可以在调用Collections.sort()
时指定要使用的比较器
Stack Overflow用户
发布于 2010-12-17 21:37:03
是的，您可以使用Collections.sort() --这几乎肯定是正确的做法。你至少应该从一开始就这样做，并对其进行基准测试，看看它是否足够快。如果你有更多关于列表的信息，你可能会做得更好(例如，一开始它可能是“基本上排序的”)，但采取简单的方法是一个很好的起点。
请注意，您的示例代码与您的描述不符-您已经描述了一个ArrayList<Node>，但您的代码只是用于ArrayList<Integer>。
Stack Overflow用户
发布于 2010-12-17 22:00:11
在对用户定义的对象进行排序时，需要实现类似的接口。为此，您还需要覆盖equals()和hashcode()方法。但是，对只包含原始数据类型对象的列表进行排序时，这不是必需的。
https://stackoverflow.com/questions/4470939
复制相似问题
腾讯云开发者
