如何在Java中以快速排序算法解决此问题 [英] How can I fix the issue in quick sort algoritm in Java

问题描述

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

I have a problem about sorting object array thanks to quick sort algorithm.

我创建了Person对象，包括id，name，surname和最后的age.

I created Person object including id, name, surname and lastly age.

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

I used comparator to sort list in terms of the attributes of person object.

这是下面显示的示例.

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

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

I think my problem is located in both two while loop by implementing greaterthan and lessthan. Here is the problem I think

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

如何解决该问题.

我还在帖子中添加了算法.

I also added my algorithm to the post.

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

Here is my quick sort algorithm implementation code snippet

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;
}

推荐答案

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

The simple answer is that you're calculating the index of the pivot element incorrectly. You want:

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

带有+而不是-.

或者:

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

但是说实话，我不喜欢这种快速排序策略.它做一些奇怪的事情，例如与元素本身交换元素(当ll == rr时)，并使元素在分区的两侧等于分区值.有一种更好的方式.

But honestly I'm not a fan of this quicksort strategy. It does weird things like swap elements with themselves (when ll == rr) and leave elements equal to the partition value on both sides of the partition. There's a better way.

这篇关于如何在Java中以快速排序算法解决此问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！