java - 多变量快速排序 [Java]

Question

再见! 我正在尝试按数据的年龄对数据(名称 - 年龄)进行排序。 我使用了 QUICKSORT 算法，可以快速对 AGE 进行排序，但是如何使用年龄各自的名称对 Age 进行排序？

我还用谷歌搜索了 Comparable 和 Comparator，但我不明白如何使用快速排序来实现它。

这是我的快速排序代码。

private int array[];
private int length;

public void sort(int[] inputArr) {
    if (inputArr == null || inputArr.length == 0) {
        return;
    }
    this.array = inputArr;
    length = inputArr.length;
    quickSort(0, length - 1);
}

private void quickSort(int lowerIndex, int higherIndex) {
    int i = lowerIndex;
    int j = higherIndex;
    int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
    while (i <= j) {
        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(i, j);
            i++;
            j--;
        }
    }
    // call quickSort() method recursively
    if (lowerIndex < j)
        quickSort(lowerIndex, j);
    if (i < higherIndex)
        quickSort(i, higherIndex);
}

private void swap(int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public static void main(String a[]){

    GUIAdvanceSort sorter = new GUIAdvanceSort();
    int[] input = {5,4,3,2,1};
    sorter.sort(input);
    for(int i:input){
        System.out.print(i);
        System.out.print(" ");
    }
}

Answer 1

要总结链接和评论，您首先需要创建一个 NameAndAge类来封装这两个属性。那么你有两个选择:

1. 制造NameAndAge通过实现Comparable<NameAndAge>“自然”地具有可比性
2. 如果您不认为它们本质上具有可比性，请创建专用的 Comparator<NameAndAge>并将其应用到列表中。

我认为 (1) 是正确的选择。

以下示例远未完成( equals() 和 hashCode() 应被覆盖)，但它演示了 NameAndAge 的自然顺序:首先是名称(不区分大小写)，然后是年龄(升序)，并且在使用 Java 现有的 Collections.sort() 时有效。方法。

您需要为自己的算法做的是:

1. 将您的算法从处理 int 中切换出来=> NameAndAge ，或者理想情况下 Comparable<T>
2. 不要使用 < 和 >，而是使用 current.compareTo(pivot)相反。

Comparable示例:

public static void main(String a[]){

    List<NameAge> entries = new ArrayList<>();
    entries.add( new NameAge("Zack", 2) );
    entries.add( new NameAge("John", 37) );
    entries.add( new NameAge("John", 11) );
    entries.add( new NameAge("John", 5) );
    entries.add( new NameAge("Andrew", 9) );

    Collections.sort(entries);

    for (NameAge each : entries) {
        System.out.println(each.name + " (" + each.age + ")");
    }
}

public static class NameAge implements Comparable<NameAge> {
    String name;
    int age;

    public NameAge(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo( NameAge other) {
        int nc = name.compareToIgnoreCase( other.name );
        if (nc != 0) {
            return nc;
        }
        return (age < other.age) ? -1 : ((age > other.age) ? 1 : 0);
    }
}

产品:

Andrew (9)
John (5)
John (11)
John (37)
Zack (2)