Java 快速排序 - 是否可以在不使用比较器的情况下比较对象?

Java quicksort - is it possible to compare objects without using a comparator?

有没有一种方法可以同时对 ArrayList 中的数组元素进行快速排序 根据排序的数组更改 ArrayList 的顺序而不使用 Comparator<> 函数?

    public ArrayList<PatientArray> ageSorter(ArrayList<PatientArray> pa) {
        if (pa.size() <= 1) {
            return pa;
        }

        ArrayList<PatientArray> sorted;
        ArrayList<PatientArray> smaller = new ArrayList<PatientArray>();
        ArrayList<PatientArray> greater = new ArrayList<PatientArray>();

        PatientArray middle = pa.get(0);
        int i;
        PatientArray j;
        for (i = 1; i < pa.size(); i++) {
            j = pa.get(i);

            if ((new SortAge().compare(j, middle)) < 0) { // this object comparator
                smaller.add(j);
            } else {
                greater.add(j);
            }
        }
        smaller = ageSorter(smaller);
        greater = ageSorter(greater);
        smaller.add(middle);
        smaller.addAll(greater);
        sorted = smaller;

        return sorted;
    }

    class SortAge implements Comparator <PatientArray>{
    public int compare(PatientArray a1, PatientArray a2){
        return a1.age-a2.age;
    }

您可以在 List class 上使用 Java 8 上介绍的 sort 方法. 所以你的方法如下:

public List<PatientArray> ageSorter(ArrayList<PatientArray> pa) {
   pa.sort(Comparator.comparingInt(a -> a.age));
   return pa;
}

避免使用 Comparator 的最简单方法是直接在快速排序代码中自己执行比较:

if (pa.get(i).age < middle.age)

虽然您没有要求一般性的审阅意见,但我会注意到您的代码中有很多不必要的命令。

public ArrayList<PatientArray> ageSorter(ArrayList<PatientArray> pa) {
    if (pa.size() <= 1) {
        return pa;
    }

    ArrayList<PatientArray> smaller = new ArrayList<PatientArray>();
    ArrayList<PatientArray> greater = new ArrayList<PatientArray>();

    PatientArray pivot = pa.get(0);
    for (int i = 1; i < pa.size(); i++) {
        if (pa.get(i).age < pivot.age) {
            smaller.add(j);
        } else {
            greater.add(j);
        }
    }
    smaller = ageSorter(smaller);
    greater = ageSorter(greater);
    smaller.add(middle);
    smaller.addAll(greater);
    return smaller;
}

另请注意,通常实施快速排序以便就地完成排序 - 即无需创建新数组。

正如@Holger 在下面的评论中指出的那样,枢轴(作为第一个元素)的选择也很糟糕。解释了原因和备选方案 here

虽然从技术上讲您的算法是快速排序,但它可能并不快。