如何按照某种自然顺序对链表进行排序？

Question

如何按照某种自然顺序对链表进行排序？

javasorting

4

我们有一个链表，这个链表的元素是员工(Employee)，我想根据员工的薪水对这个链表进行排序，薪水是Employee类的一个成员，我们可以使用Collections.sort()吗？如果不能，该怎么办呢？

- user707549

4个回答

4

虽然 LinkedList<Employee> 可以工作，但我会使用 ArrayList<Employee>：

List<Employee> employees = new ArrayList<Employee>();

在您填充数据（无论哪种方式）后，可以按薪资排序，如下所示：

Collections.sort(employees, new Comparator<Employee>() {
    public int compare(Employee e1, Employee e2) {
        return e1.getSalary() - e2.getSalary();
    }
});

- WhiteFang34

0

你可以使用 Collections.sort()

但是为了做到这一点，你的 Employee 类需要先实现 Comparable 接口。

一个简单的例子如下：

public class Employee implements Comparable<Employee>
{
    public int compareTo(Employee e)
    {
        return this.salary - e.salary;
    }
}

- Coding District

好的，我明白了。但是如果我们实现Comparable接口，有几种排序算法，比如冒泡排序、选择排序、快速排序等等，那么Comparable接口和Collections.sort()使用哪种排序算法呢？ - user707549

1

Comparable接口仅仅是一个接口 - 它与Collections.sort()使用的算法无关。请注意，我不是100％确定，但我认为Java使用混合归并排序。放心，时间效率将是O(nlogn)。 - Coding District

是的，它使用了修改后的归并排序，详细信息在Collections.sort()的javadoc中。 - Brian Roach

我已经阅读了教程，只是想澄清一下compareTo()的实现，如果返回值小于0，那么Collections.sort()会交换这两个对象吗？如果返回值为1或0，它什么也不做？ - user707549

0

你可以对链表进行排序，但这不是一种高效的操作，特别是当链表的大小不是微不足道的时候。选择适当的数据结构。

- ddyer

取决于您的数据和使用模式。简单的答案是使用数组，因为有很多有效的排序算法已经实现了数组。另一个答案是使用B*树并创建已经排序好的数据。 - ddyer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，

- Brian Roach · Accepted Answer

是的，你可以使用 Collections.sort()

你需要让你的Employee类实现Comparable接口。

http://download.oracle.com/javase/6/docs/api/java/lang/Comparable.html

在你的compareTo()方法中，你应该比较当前对象的薪水和传入对象的薪水。

编辑:

如果你不想让这成为默认的比较方法，你还有另一个选择，那就是创建一个Comparator对象并使用第二个形式 -> Collections.sort(List, Comparator);

它会像这样：

class SalaryComparator implements Comparator<Employee>
{

    public int compare(Employee e1, Employee e2)
    {

        if (e1.getSalary() > e2.getSalary())
            return 1;
        else if (e1.getSalary() < e2.getSalary())
            return -1;
        else
            return 0;
    }

}

现在您可以执行：Collections.sort(myEmployeeList, new SalaryComparator());