重新排列java

Question

我正试图使用下面的代码根据年龄从最年轻到最年长来重新排列我的Person数组。

public class Trial {
    public static void main(String[] args){
        Person[] person = new Person[3];
        person[0] = new Person("Jerome", 21);
        person[1] = new Person("Jam", 16);
        person[2] = new Person("Imelda", 53);
        for(int i=0; i<person.length;i++){
            System.out.println(person[i].getName() + " " + person[i].getAge());
        }
        String name = "";
        int age = 0;
        int counter = 0;
        for(int i=1;i<person.length;i++){
            name = person[i].getName();
            age = person[i].getAge();
            counter = i - 1;
            while(i>-1&&person[counter].getAge()>age){
                person[counter+1].setAge(person[counter].getAge());
                person[counter+1].setName(person[counter].getName());
                counter -= 1;
            }

            person[counter+1].setAge(age);
            person[counter+1].setName(name);
        }
        for(int i=0; i<person.length;i++){
            System.out.println(person[i].getName() + " " + person[i].getAge());
        }
    }
}

该算法在整数数组中运行平稳，但在这里，我得到了这个错误。

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at com.example.java.Trial.main(Trial.java:28)

这是错误指向的地方

while(i>-1&&person[counter].getAge()>age){
                person[counter+1].setAge(person[counter].getAge());
                person[counter+1].setName(person[counter].getName());
                counter -= 1;
            }

我做错什么了吗？或者有没有其他方法可以根据特定的变量排列对象数组？

Answer 1

如果您让Person实现Comparable，您可以使用Arrays.sort(...)为您实现这一点！

public class Person implements Comparable<Person> {
    // Existing class implementation
    @Override
    public int compareTo(Person p) {
        return p2.age - this.age;
    }
}

EDIT:或者，当调用Arrays.sort()时，您可以直接内联实现compareTo方法（即：不需要修改Person）：

Arrays.sort(personArray, new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return p2.age - p1.age;
    }
});

如果您运行的是Java8，则可以使用lambda表达式来进一步缩短：

Arrays.sort(personArray, (p1, p2) -> p2.age - p1.age);

Answer 2

尝试更改此项：

     for(int i=1;i<person.length;i++){

至

     for(int i=1;i<=person.length;i++){ 

Answer 3

核心问题确实存在：

while(i>-1&&person[counter].getAge()>age){
    person[counter+1].setAge(person[counter].getAge());
    person[counter+1].setName(person[counter].getName());
    counter -= 1;
}

在while循环中，对i（i > -1）执行边界检查，但使用counter。因此，为了解决核心问题，您必须使用counter而不是i:

while(counter>-1&&person[counter].getAge()>age){
    person[counter+1].setAge(person[counter].getAge());
    person[counter+1].setName(person[counter].getName());
    counter -= 1;
}

不过，这不是对数组中的对象进行排序的好方法。由于以下几个原因：

• 不是交换对象，而是交换这些对象的状态。想象一下，在项目的后期，您必须向Person添加一个新字段，然后您的算法就被破坏了。此外，可能存在对该Person的其他引用，其name和age将发生变化
• 您正在实现插入排序算法，而QuickSort和MergeSort显著优于的插入排序

交换状态时出现问题

如果交换对象的状态，这与交换对象在数组中的位置不同。想象一下，你希望延长你的计划：现在人们可以结婚了。这意味着，例如，您持有一个与Bob结婚的Person的某个数组。假设鲍勃和爱丽丝结婚了。如果后来你把鲍勃的名字改成了辛迪，那么突然间辛迪就嫁给了爱丽丝。

你可以通过将代码重写为：来解决这个问题

for(int i=1;i<person.length;i++) {
    Person toSwap = person[i];
    counter = i - 1;
    while(counter >-1 &&person[counter].getAge()>age) {
        person[counter+1] = person[counter];
        counter -= 1;
    }
    Person[counter+1] = toSwap;
}

此外，建议将while转换为for，因为产生无限循环的可能性较小：

for(int i=1;i<person.length;i++) {
    Person toSwap = person[i];
    for(counter = i-1; counter >-1 &&person[counter].getAge()>age; counter--) {
        person[counter+1] = person[counter];
    }
    Person[counter+1] = toSwap;
}

排序算法

您基本上实现了插入排序的一个版本。插入排序获取一个对象，查找所有较大（或较小）的对象，将这些对象向右（左）移动一个，然后将对象定位在正确的位置。这在O（n²）或二次时间中运行最坏情况。这意味着，在最坏的情况下，如果你将列表的长度增加一倍，那么解决问题所需的时间将增加四倍。

计算机科学家已经想出了更好的排序方法，比如QuickSort和MergeSortMergeSort例如在O（n log n）中运行。这意味着，如果将列表的长度增加一倍，则排序所需的时间也会增加一倍并且添加了一个时间单位。这个时间单位是什么（1毫秒、纳秒、78秒…）是未知的，但最终，如果列表足够大，对于未排序的列表，MergeSort将优于InsertionSort。

使用内置

Java提供了大量的类、方法和算法。通过使用这些算法，你可以在如何做到错误安全、高效且没有太多/任何副作用方面进行大量研究。

为了执行错误安全和快速排序，可以使用Arrays.sort(T[],IComparator<T>)。