如何解决 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--;
        }

我该如何解决这个问题。

我也将我的算法添加到 post。

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

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.

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

How can I fix the issue in quick sort algoritm in Java

java

sorting

algorithm

quicksort