在 Java 中，如何对排序字段为多层深度的对象的 ArrayList 进行快速排序？

In Java, How do you quicksort an ArrayList of objects in which the sorting field is multiple layers deep?

提问by trusktr

Basically, I have a Container class called "Employees" which has in it an ArrayList. This ArrayList contains "Employee" objects, which in turn contain "EmployeeData" objects which in turn contain String objects such as "first" or "last" (which are employee names).

基本上，我有一个名为“Employees”的容器类，其中包含一个 ArrayList。此 ArrayList 包含“Employee”对象，而这些对象又包含“EmployeeData”对象，而“EmployeeData”对象又包含 String 对象，例如“first”或“last”（它们是员工姓名）。

Here's a diagram of the ArrayList structure:

这是 ArrayList 结构的示意图：

ArrayList[Employee] emps ==> 1:Many ==> Employee emp
Employee emp ==> 1:1 ==> EmployeeData data
EmployeeData data ==> 1:2 ==> String last // A string that contains employee's last name.

How in the world would I perform a quicksort on the ArrayList so that the "Employee" objects in it are in alphabetical order based on the String object "last"? It seems kinda complicated!

我到底将如何对 ArrayList 执行快速排序，以便其中的“Employee”对象基于 String 对象“last”按字母顺序排列？好像有点复杂！

---

---

Here's a basic design of my classes:

这是我的课程的基本设计：

class Employees{
    //data:
        private ArrayList<Employee> emps = new ArrayList<Employee>();

    //Some constructors go here

    //Methods to add, remove, toString, etc, go here

    public /*output a sorted ArrayList?*/ sort(){
        // Some kind of "quicksort" in here to modify or create a new ArrayList sorted by employee's las name...
    }
}

class Employee{
    //data:
    EmployeeData data;
    // Some methods to construct and modify EmployeeData data.
}

class EmployeeData{
    //data:
        String first, last; // I wish to sort with "last". How do you do it?
        double payrate, hours;
    //...methods...
}

As you can see, those are the classes. I have no idea how to implement "sort" in the "Employees" class so that it sorts the ArrayList by the "last" variable of the "EmployeeData" class.

如您所见，这些就是类。我不知道如何在“Employees”类中实现“sort”，以便它通过“EmployeeData”类的“last”变量对ArrayList进行排序。

采纳答案by Jason Goemaat

The best practice is to encapsulate the sorting logic in the class stored in the ArrayList, Employee in this case. Implement Comparable by creating a compareTo(Employee) method.

最好的做法是将排序逻辑封装在ArrayList中存储的类中，本例中为Employee。通过创建 compareTo(Employee) 方法实现 Comparable。

import java.util.*;

public class Employee  implements Comparable<Employee> {
    public EmployeeData Data;

    public Employee(String first, String last)
    {
        Data = new EmployeeData(first, last);
    }

    public int compareTo(Employee other)
    {
        return Data.Last.compareTo(other.Data.Last);
    }

    public String toString() {
        return Data.First + " " + Data.Last;
    }

    public static void main(String[] args) throws java.io.IOException {
        ArrayList list = new ArrayList();
        list.add(new Employee("Andy", "Smith"));
        list.add(new Employee("John", "Williams"));
        list.add(new Employee("Bob", "Jones"));
        list.add(new Employee("Abraham", "Abrams"));
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++)
        {
            System.out.println(list.get(i));
        }
        System.in.read();
    }
}

public class EmployeeData {
    public String First;
    public String Last;
    public EmployeeData(String first, String last)
    {
        First = first;
        Last = last;
    }
}

Output:

输出：

Abraham Abrams
Bob Jones
Andy Smith
John Williams

回答by Peter DeWeese

You can make a comparator, something like:

您可以制作一个比较器，例如：

public class MyComparator implements Comparator<Employee>
{
  public int compare(Employee e1, Employee e2)
  {
    return e1.getData().getLast().compareTo(e2.getData().getLast());
  }
}

Then use it to sort the list.

然后使用它对列表进行排序。

Collections.sort(myList, new MyComparator());

Alternatively, you can use a TreeSet to sort on insertion using this comparator or make the Employee a comparable object to sort using Collections or a SortedSet.

或者，您可以使用 TreeSet 使用此比较器对插入进行排序，或者使 Employee 成为可比较的对象，以使用 Collections 或 SortedSet 进行排序。

public class Employee implements Comperable<Employee>
{
  ...
  public int compareTo(Employee e)
  {
    return this.getData().getLast().compareTo(e.getData().getLast());
  }
  ...
}

回答by Erick Robertson

Define Employee implements Comparable<Employee>.

定义Employee implements Comparable<Employee>。

In the compareTomethod, dig into the layers and compare the strings you need. Then you can use Collections.sort(), or you can store the data in a SortedSet, which is naturally ordered.

在该compareTo方法中，深入研究层并比较您需要的字符串。然后就可以使用Collections.sort()，也可以将数据存储在SortedSet自然有序的 中。

回答by sova

Peter DeWeese and others have given you very good answers. You can use

Peter DeWeese 和其他人已经给了你很好的答案。您可以使用

Collections.sort(myList, new MyComparator());

to sort myList using a Comparator you have defined. <=== What the heck does that mean?

使用您定义的比较器对 myList 进行排序。<=== 这到底是什么意思？

In Java, if something implements Comparable (java.lang.comparable)then you can define an order for your elements. It seems like you know what Java Genericsare, as you used them to declare your ArrayList as being of type < Employee >. This is awesome, because you can store an Employee object into each entry in the ArrayList. So far so good?

在 Java 中，如果某些东西实现了 Comparable (java.lang.comparable)，那么您可以为您的元素定义一个顺序。您似乎知道Java 泛型是什么，因为您使用它们将 ArrayList 声明为 < Employee > 类型。这很棒，因为您可以将 Employee 对象存储到 ArrayList 的每个条目中。到现在为止还挺好？

However, if you want to sort objects, first you have to define an order. Since objects can have various properties, maybe I want to sort my employees by ear-size. In this case, I simply tell Java that my class implements Comparable. With generics, I have to specify that it implements Comparable< Employee > because I am defining an order for my Employee objects (peons, minions, whatever).

但是，如果要对对象进行排序，首先必须定义一个顺序。由于对象可以具有各种属性，也许我想按耳朵大小对我的员工进行排序。在这种情况下，我只是告诉 Java 我的类实现了 Comparable。对于泛型，我必须指定它实现 Comparable<Employee>，因为我正在为我的 Employee 对象（peons、minions 等）定义一个顺序。

Peter DeWeese mentioned:

彼得·德威斯提到：

 public int compareTo(Employee e)
 {
     return this.getData().getLast().compareTo(e.getData().getLast());
 }

and Jason Goemaat mentioned:

Jason Goemaat 提到：

public int compareTo(Employee other)
{
    return Data.Last.compareTo(other.Data.Last);
}

What the heck does this mean? If I say that my class implements Comparable then I need to define a compareTo function. (An interface is a collection of methods that need to be implemented) The function compareTo defines the order of my elements.

这到底是什么意思？如果我说我的类实现了 Comparable，那么我需要定义一个 compareTo 函数。（接口是需要实现的方法的集合）函数 compareTo 定义了我的元素的顺序。

From the Comparable< T> spec:

来自 Comparable<T> 规范：

int compareTo(T o)

int compareTo(T o)

Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

将此对象与指定的对象进行比较以进行排序。当此对象小于、等于或大于指定对象时，返回一个负整数、零或正整数。

If I am comparing ear sizes, and let's say I want big ears to come first in my list, then I could (re)define compareTo as:

如果我比较耳朵大小，并且假设我希望大耳朵排在我的列表中，那么我可以（重新）将 compareTo 定义为：

public int compareTo(Employee e)
{
    if (this.earSize > e.earSize) //big ears come first
        return -1;
    if (this.earSize == e.earSize) //equality
        return 0;
    else
        return 1; // if e.earSize > this.earSize then return 1
}

To answer Steve Kuo's question, we put the keyword thisin our comparator because when we call the compareTo method

为了回答 Steve Kuo 的问题，我们将关键字this放在比较器中，因为当我们调用 compareTo 方法时

x.compareTo(y); 

the keyword thiswill refer to x.

关键字this将引用x。

You can think of compareTo as being a method of the object x, so when you call x.compareTo(y) you are really saying this.compareTo(y) from within the scope of object x.

您可以将 compareTo 视为对象x 的一个方法，因此当您调用 x.compareTo(y) 时，您实际上是在对象x的范围内说 this.compareTo(y) 。

We can also look at a String example:

我们还可以看一个字符串示例：

This means that if I want "Medvedev" to come before "Putin" (as 'M' comes before 'P' in the English alphabet) I would have to state that I want compareTo to return -1 when comparing Medvedev to Putin.

这意味着，如果我希望“Medvedev”出现在“Putin”之前（因为在英文字母表中“M”出现在“P”之前），我必须声明我希望在将 Medvedev 与普京进行比较时 compareTo 返回 -1。

String TheMString = "Medvedev";
String ThePString = "Putin";

then the line

然后线

TheMString.compareTo(ThePString);

will evaluate to -1.

将评估为 -1。

Now a standard routine such as Collections.sort(list, comparator) will be able to use these values that compareTo returns to figure out the [absolute] order of list. As you may know, sorting is a comparison based operation and we need to know what value is "less than" or "greater than" another value in order to have a meaningful sort.

现在，诸如 Collections.sort( list,comparator) 之类的标准例程将能够使用 compareTo 返回的这些值来确定list的 [绝对] 顺序。您可能知道，排序是基于比较的操作，我们需要知道什么值“小于”或“大于”另一个值才能进行有意义的排序。

One big caveat is that if you call compareTo on Strings, it defaults to alphabetical order, so you may simply tell compareTo to return A.compareto(B) and it will make sure the strings are in order.

一个重要的警告是，如果你在字符串上调用 compareTo，它默认按字母顺序排列，所以你可以简单地告诉 compareTo 返回 A.compareto(B) ，它会确保字符串是有序的。

Normally (well, I should say, in other cases) when redefining the compareTo method, you must explicitly state a neg/zero/pos return value.

通常（好吧，我应该说，在其他情况下）在重新定义 compareTo 方法时，您必须明确声明一个 neg/zero/pos 返回值。

I hope that helps.

我希望这有帮助。