4

我最近一直在努力更好地理解排序算法及其与不同类型输入的关系。目前，我正在开发一个学生管理程序，其中每个学生都有三个参数：姓氏、GPA 和用户 ID（字符串、双精度、整数）。它们每个都存储在具有这三个参数的 Student 类中，并且有 DOZENS 学生（该程序的一个关键特性是输入、删除和更新学生）。

我的问题是：使用主要的排序算法（合并排序、快速排序等），按每个参数对我的学生列表进行排序的最佳方法是什么？例如，执行合并排序以按 GPA 对列表进行排序的最佳方法是什么？或者使用快速排序按姓氏对列表进行排序？

基本上我的问题归结为......如果这些对象没有三个参数，我可以对它们进行排序（编写一个合并排序来对 100 个数字进行排序对我来说非常容易）。如何管理其他两个参数并确保它们在排序后可访问？

4

6 回答 6

5

在 Java 中完成此操作的方式是使用不同的Comparators。然后你说：

Collections.sort(list, new NameComparator());

或者

Collections.sort(list, new GpaComparator());

这些比较器使用不同的字段来定义两个元素之间的顺序。

例如，名称比较器可能是：

class NameComparator implements Comparator< Student> {
    @Override public int compare(Student left, Student right) {
        return left.getName().compareTo(right.getName());
    }
}

而 GpaComparator 可能是

class GpaComparator implements Comparator< Student> {
    @Override public int compare(Student left, Student right) {
        if (left.getGpa() < right.getGpa()) {
            return -1;
       } else if (left.getGpa() > right.getGpa()) {
            return 1;
       } else {
           return 0;
     }
 }
于 2012-04-04T17:49:20.413 回答
1

我建议像这样在你的类中实现Comparable接口Student

public class Student implements Comparable {
   public int compareType; //you can make this an enum if you want
   ...

   public int compareTo(Object o) {
       if(compareType == 0) 
         return gpaCompareTo(o);
       else if(compareType == 1)
         return nameCompareTo(o);

       return idCompateTo(o); 
   }

   public int gpaCompareTo(Object o) {
       //implement your gpaCompareTo
   }

   public int nameCompareTo(Object o) {
       //implement your nameCompareTo
   }

   public int idCompareTo(Object o) {
       //implement your idCompareTo
   }
}

然后使用内置排序，如

List<Student> list = new ArrayList<Student>();
...
Collections.sort(list);

或者您无法实现Comparable和设计自己的比较器

public class MyComparator implements Comparator<Student> {

   public int compare(Student o1, Student o2) {
      //implement the comparator
   }

   public boolean equals(Object o) {
      //implement the equals 
   }
}

然后你可以使用其他Collection's排序方法

Collections.sort(list, MyComparator);
于 2012-04-04T17:48:57.700 回答
1

执行此操作的典型方法是对任何接受 a 的类型编写通用排序算法Comparator，然后编写不同Comparator的 s 以按不同字段排序。

于 2012-04-04T17:49:10.097 回答
1

这可能是题外话，但是如果您想尝试一些很酷的东西，JDK 8 Lambda Preview提供了一些很酷的方法来使用Lamda 表达式和方法引用来定义比较器。

假设我们有一个类：

class Jedi  {
   private final String name;
   private final int age;
   //...
}

然后是它们的集合：

List<Jedi> jediAcademy = asList(new Jedi("Obiwan",80), new Jedi("Anakin", 30));
sort(jediAcademy, (j1, j2) -> j1.getAge() > j2.getAge() ? 1 : j1.getAge() < j2.getAge() ? -1 : 0);
System.out.println(jediAcademy); //Anakin, Obiwan

或者使用方法引用，假设 Jedi 具有充当比较器的方法（相同的签名）

class Jedi  {
  public static int compareByAge(Jedi first, Jedi second){
     return first.age > second.age ? 1 : first.age < second.age ? -1 : 0;
  }
   //...
}

可以如下使用方法引用来生成比较器：

List<Jedi> jediAcademy = asList(new Jedi("Obiwan",80), new Jedi("Anakin", 30));
sort(jediAcademy, Jedi::compareByAge);
System.out.println(jediAcademy);//Anakin, Obiwan
于 2012-04-04T18:18:18.880 回答
0

真的和排序数字没什么区别，只不过在这种情况下你的“数字”是你用户的三个字段，每个数字的值受每个字段的值的约束，字段的顺序决定了排序的排名。

更具体地说，您有一个包含 3 个字段的元组：<GPA, Last Name, User ID>，假设您要按 GPA 排序，然后是姓氏和用户 ID。

与 219 排序高于 139 的方式相同（即，即使“十”位较低，“百”位具有更高的值），类似元组的<3.75, Jones, 5>将在上方排序，<3.0, Adams, 2>因为“GPA 位”（这是更多显着）具有更高的值，即使“姓氏数字”较低（例如，琼斯“低于”亚当斯）。

于 2012-04-04T17:48:10.117 回答
0

使用多个比较器

class Student
{

        String lastName;
        dounle GPA;
        int userId


    static Comparator<Student> getStudentLastNameComparator() {
        return new Comparator<Student>() {

            @Override
            public int compare(Student Student1, Student Student2) {
                return Student1.getlastName().compareTo(Student2.getlastName());
            }
            // compare using Student lastName
        };
    }

    static Comparator<Student> getStudentGPAComparator() {
        return new Comparator<Student>() {

            @Override
            public int compare(Student Student1, Student Student2) {
                if(Student1.GPA < Student2.GPA)
                    return 1;
                else
                    return -1;
            }
            // compare using Student GPA
        };
    }

    static Comparator<Student> getStudentUserIdComparator() {
        return new Comparator<Student>() {

            @Override
            public int compare(Student Student1, Student Student2) {
                if(Student1.userId < Student2.userId)
                    return 1;
                else
                    return -1;
            }
            // compare using Student userId
        };
    }
}
于 2015-06-30T08:08:32.510 回答