Collections.sort实现 [英] Collections.sort implementation

问题描述

我无法理解Collections.sort方法的方法实现和逻辑。这是我找到的方法实现，

I can not understand the method implementation and the logic of Collections.sort method. Here is the method implementation i found,

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
    }

首先，此方法的返回类型为void。什么是< T extends Comparable<？超级T>> 在方法签名中做了什么？

First of all this method return type is void. What is <T extends Comparable<? super T>> does in the method signature?

在这里使用Array.sort的目的是什么？

What is the purpose of using Array.sort here?

一旦我们实现了比较或比较器，我们编写的比较或比较方法逻辑会考虑吗？

Also once we implement comparable or comparator where is the compare or compareTo method logic that we wrote take in to consider?

推荐答案

请注意泛型类型的显示位置：

Please pay attention to where the generic type appears:

public static <T extends Comparable<? super T>> void sort(List<T> list)

它基本上声明并限制泛型类型 T 。在这种特殊情况下，它意味着： T 必须延伸可比较< F> 其中 F 必须是 T 类型或其超级类型。这意味着如果您有以下类别：

It basically declares and puts restriction on generic type T. In this particular case it means: T must extend Comparable<F> where F must be of type T or a super type of it. This means thay if you have the following classes:

class Animal {}

class Dog extends Animal implements Comparable<Animal> {
    //...
}

您仍然可以传递列出< Dog> 到 Collections.sort（）（注意 Dog implements Comparable< Animal> ，而非 Comparable< Dog> 照例）。

You can still pass List<Dog> to Collections.sort() (notice that Dog implements Comparable<Animal>, not Comparable<Dog> as usual).

使用Arrays.sort（），因为这是实现排序算法的地方。如果集合不是随机访问，则需要遵守合同并避免次优运行时从集合到数组的防御性副本。

Arrays.sort() is used because this is where the sorting algorithm is implemented. Defensive copy from collection to array is needed to obey the contract and to avoid suboptimal runtime if collection is not random access.

某些列表，如 LinkedList 具有较差的随机访问（按索引）性能，这使得大多数排序算法非常慢（在 O（n ^ 2）的范围内）。最好是防御性地复制整个集合并对数组进行排序，因为 O（n + nlogn + n）仍然是 O（nlogn） - 如果你得到大O符号）。

Some lists, like LinkedList have poor random access (by index) performance, which makes most sorting algorithms quite slow (in the range of O(n^2)). It's better to defensively copy the whole collection and do the sorting on array because O(n + nlogn + n) is still O(nlogn) - if you get big O notation).

这篇关于Collections.sort实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！