java Collections.sort 实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14322585/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Collections.sort implementation
提问by FrankD
I can not understand the method implementation and the logic of Collections.sort method. Here is the method implementation i found,
我无法理解 Collections.sort 方法的方法实现和逻辑。这是我找到的方法实现，
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]);
}
}
First of all this method return type is void. What is <T extends Comparable<? super T>>does in the method signature?
首先这个方法的返回类型是void。什么是<T extends Comparable<? super T>>方法签名呢？
What is the purpose of using Array.sort here?
在这里使用 Array.sort 的目的是什么？
Also once we implement comparable or comparator where is the compare or compareTo method logic that we wrote take in to consider?
此外，一旦我们实现了可比较或比较器，我们编写的 compare 或 compareTo 方法逻辑在哪里考虑？
回答by Tomasz Nurkiewicz
Please pay attention to where the generic type appears:
请注意泛型类型出现的位置：
public static <T extends Comparable<? super T>> void sort(List<T> list)
It basically declares and puts restriction on generic type T. In this particular case it means: Tmust extend Comparable<F>where Fmust be of type Tor a super type of it. This means thay if you have the following classes:
它基本上声明并限制了泛型类型T。在这种特殊情况下，它意味着：T必须扩展Comparable<F>where Fmust be of typeT或 it 的超类型。这意味着如果您有以下课程：
class Animal {}
class Dog extends Animal implements Comparable<Animal> {
//...
}
You can still pass List<Dog>to Collections.sort()(notice that Dogimplements Comparable<Animal>, not Comparable<Dog>as usual).
您仍然可以传递List<Dog>到Collections.sort()（注意Dog实现Comparable<Animal>，而不是Comparable<Dog>像往常一样）。
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.
Arrays.sort()之所以使用，是因为这是实现排序算法的地方。如果集合不是随机访问，则需要从集合到数组的防御性复制以遵守约定并避免次优运行时间。
Some lists, like LinkedListhave 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).
一些列表，比如LinkedList随机访问（按索引）性能很差，这使得大多数排序算法非常慢（在 范围内O(n^2)）。最好防御性地复制整个集合并对数组进行排序，因为O(n + nlogn + n)仍然O(nlogn)- 如果您使用大 O 符号）。
回答by Andrei Barsan
The way Collections.sortworks is that it actually takes the collection's underlying array, and calls itssort method to sort the actual elements. That sorting algorithm used by Java is the lightning-fast Timsort.
有效的方法Collections.sort是它实际上采用集合的底层数组，并调用其sort 方法对实际元素进行排序。Java 使用的排序算法是闪电般的Timsort。
The method returns voidbecause it sorts the collection in-place. That is, it modifiesthe collection you give it as a parameter by sorting its elements. Returning a sorted copy would be a waste of resources.
该方法返回void是因为它对集合进行了就地排序。也就是说，它通过对其元素进行排序来修改您作为参数提供的集合。返回已排序的副本将浪费资源。
回答by mishadoff
First of all this method return type is void
首先这个方法的返回类型是void
Because it's in-placeimplementation. List that passed to method will be sorted
因为它是就地实现。传递给方法的列表将被排序
What is
<T extends Comparable<? super T>>does in the method signature?
什么是
<T extends Comparable<? super T>>方法签名呢？
To compare results that extends Comparableinterface for type Tand it's children.
比较扩展Comparable类型接口的结果T及其子项。
Object[] a = list.toArray();
Object[] a = list.toArray();
Convert list to plain array.
将列表转换为普通数组。
What is the purpose of using Array.sort here?
在这里使用 Array.sort 的目的是什么？
Sorting of array.
数组的排序。
i.set((T)a[j]);
i.set((T)a[j]);
assign to list elements in sorted order from array
从数组中按排序顺序分配给列表元素
回答by kosa
What is <T extends Comparable<? super T>>
This is to specify Type of Tin List<T>. Read this tutorial on Type Inference.
这是指定类型Tin List<T>。阅读有关类型推断的本教程。
回答by PermGenError
First of all this method return type is void. What is > does in the method signature?
首先这个方法的返回类型是void。> 方法签名中的作用是什么？
is a generic Type that you use in your method, T could only be an object which implements java.util.Comparable.
是您在方法中使用的泛型类型，T 只能是实现 java.util.Comparable 的对象。
for example if you want to pass a List<String>to the sort method it'd compile as java.lang.Stringimplements java.lang.Comparable, but if you pass List<Animal>you'd get a compiler error unless Animalimplements java.lang.comparable
例如，如果您想将 a 传递List<String>给 sort 方法，它会编译为java.lang.Stringimplements java.lang.Comparable，但是如果您通过，List<Animal>则会出现编译器错误，除非Animalimplementsjava.lang.comparable
