快速排序多变量 [Java]

Question

你好！我正在尝试按年龄对数据（姓名 - 年龄）进行排序。我使用了 QUICKSORT 算法并且可以快速排序 AGEs 但我如何根据各自的名称对 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

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

通过实施 Comparable<NameAndAge>

NameAndAge

如果您不认为它们本质上具有可比性，请创建一个专用 Comparator<NameAndAge> 并将其应用于列表。

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

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

你需要为自己的算法做的是：

将你的算法从处理 int => NameAndAge 切换到 Comparable<T>
不使用 < 和 >，而是使用 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)

快速排序多变量 [Java]

Quicksort Multiple Variable [Java]

java

arrays

sorting

quicksort