如何用Java快速排序算法解决问题

Question

由于快速排序算法，我在排序对象数组时遇到问题。

我创建了Person对象，包括id，name，surname，最后是age。

我使用比较器根据人员对象的属性对列表进行排序。

这是下面显示的示例。

Comparator<Person> compTr = new Comparator<Person>() {
    @Override
    public int compare(Person p0, Person p1) {
        return Long.compare(p0.getId(), p1.getId());
    }
};

我认为我的问题通过实现greaterthan和lessthan处于两个while循环中。这是我认为的问题

        while (lessThan(comp, array[i], pivot)) {
            i++;
        }
        while (greaterThan(comp, array[i], pivot)) {
            j--;
        }

我该如何解决此问题。

我也在帖子中添加了我的算法。

这是我的快速排序算法实现代码段

public static Person[] quickSort(Person a[], Comparator comp) {
    return quickSort(a, 0, a.length - 1, comp);
}

private static Person[] quickSort(Person[] array, int lowerIndex, int higherIndex, Comparator comp) {

    int ll = lowerIndex;
    int rr = higherIndex;

    if (rr > ll) {

        // calculate pivot number, I am taking pivot as middle index number
        Person pivot = array[(higherIndex - lowerIndex) / 2];

        while (ll <= rr) {
            while (ll < higherIndex && lessThan(comp, array[ll], pivot)) {
                ll += 1;
            }
            while (rr > lowerIndex && greaterThan(comp, array[rr], pivot)) {
                rr -= 1;
            }
            if (ll <= rr) {
                exchangeNumbers(array, ll, rr, comp);
                ll += 1;
                rr -= 1;
            }
        }
        if (lowerIndex < rr) {
            quickSort(array, lowerIndex, rr, comp);

        }
        if (ll < higherIndex){
            quickSort(array, ll, higherIndex, comp);
        }
    }
    return array;
}

private static void exchangeNumbers(Person[] array, int i, int j, Comparator comp) {
    Person temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

// ASC
private static boolean greaterThan(Comparator comp, Person x, Person y) {
    return comp.compare(x, y) > 0;
}

// DESC
private static boolean lessThan(Comparator comp, Person x, Person y) {
    return comp.compare(x, y) < 0;
}

Answer 1

简单的答案是您计算的枢轴元素的索引不正确。您想要：

Person pivot = array[(higherIndex + lowerIndex) / 2];

[不带+，不带-。

或：

Person pivot = array[lowerIndex + (higherIndex - lowerIndex) / 2];

但是说实话，我不喜欢这种快速排序策略。它做一些奇怪的事情，例如与元素本身交换元素（ll == rr时），并使元素在分区的两侧等于分区值。有better way。