java在ArrayList上按降序实现快速排序

Question

我试图在arrayList上用Java实现快速排序，我希望输出是降序的。我有以下代码：

    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}

我想错误就在小列表和大列表连接的最后某个地方，但我似乎不知道如何修复它。有什么建议吗？谢谢

Answer 1

问题在于，您没有从任何地方的输入中删除轴心元素，而是稍后再次添加它，从而使其加倍