我正在尝试在 Java 中对 arrayList 实现快速排序,并且我希望输出按降序排列。我有以下代码:
public static <K, V extends Comparable> ArrayList<K> quickSort(ArrayList<K> toSort, HashMap<K, V> results) {
if (toSort.size() <= 1) {
return toSort; //already sorted!
}
ArrayList<K> sorted = new ArrayList<K>();
ArrayList<K> lesser = new ArrayList<K>();
ArrayList<K> greater = new ArrayList<K>();
K pivot = toSort.get(toSort.size()-1); //use last element as pivot ??
for (int i = 0; i < toSort.size(); i++) {
if (results.get(toSort.get(i)).compareTo(results.get(pivot)) >= 0) {
greater.add(toSort.get(i));
}
else {
lesser.add(toSort.get(i));
}
}
lesser = quickSort(lesser, results);
greater = quickSort(greater, results);
lesser.add(0, pivot);
greater.addAll(lesser);
sorted = greater;
但是,不要输出类似:{99, 98, 97},
我收到以下“双倍”输出:{99, 99, 98, 98, 97, 97}
我想错误是在较小列表和较大列表串联的末尾的某个地方,但我似乎不知道如何修复它。有什么建议吗?谢谢
最佳答案
问题是您没有从任何地方的输入中删除枢轴元素,而是稍后再次添加它,从而使其加倍。
关于java - 在ArrayList上实现降序快速排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59021666/