JDK中 java.util.Collections类的sort方法

java.util
类 Collections

java.lang.Object
  java.util.Collections

public class Collections

   
    extends 
    Object

   

此类完全由在 collection 上进行操作或返回 collection 的静态方法组成。它包含在 collection 上操作的多态算法，即“包装器”，包装器返回由指定 collection 支持的新 collection，以及少数其他内容。

如果为此类的方法所提供的 collection 或类对象为 null，则这些方法都将抛出NullPointerException。

此类中所含多态算法的文档通常包括对实现 的简短描述。应该将这类描述视为实现注意事项，而不是规范 的一部分。实现者应该可以随意使用其他算法替代，只要遵循规范本身即可。（例如，sort使用的算法不一定是合并排序算法，但它必须是稳定的。）

此类中包含的“破坏性”算法，即可修改其所操作的 collection 的算法，该算法被指定在 collection 不支持适当的可变基元（比如set方法）时抛出UnsupportedOperationException。如果调用不会对 collection 产生任何影响，那么这些算法可能（但不要求）抛出此异常。例如，在已经排序的、不可修改列表上调用sort方法可能会（也可能不会）抛出UnsupportedOperationException。

此类是 Java Collections Framework 的成员。

方法详细信息：

sort

public static <T> void sort(List<T> list,
                            Comparator<? super T> c)

根据指定比较器产生的顺序对指定列表进行排序。此列表内的所有元素都必须可使用指定比较器 相互比较（也就是说，对于列表中的任意e1和e2元素，c.compare(e1, e2)不得抛出ClassCastException）。

此排序被保证是稳定的：不会因调用 sort 而对相等的元素进行重新排序。

排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的 n log(n) 性能。 指定列表必须是可修改的，但不必是可大小调整的。此实现将指定列表转储到一个数组中，并对数组进行排序，在重置数组中相应位置每个元素的列表上进行迭代。这避免了由于试图原地对链接列表进行排序而产生的 n² log(n) 性能。

参数：

list - 要排序的列表。

c - 确定列表顺序的比较器。null值指示应该使用元素的 自然顺序。

抛出：

ClassCastException - 如果列表中包含不可使用指定比较器 相互比较 的元素。

UnsupportedOperationException - 如果指定列表的列表迭代器不支持set操作。

另请参见：

Comparator

java.util
接口 Comparator<T>

类型参数：

T - 此 Comparator 可以比较的对象类型

所有已知实现类：

Collator, RuleBasedCollator

public interface Comparator<T>

强行对某个对象 collection 进行整体排序 的比较函数。可以将 Comparator 传递给 sort 方法（如 Collections.sort 
或 Arrays.sort），从而允许在排序顺序上实现精确控制。还可以使用 
Comparator 来控制某些数据结构（如有序 set或有序映射）的顺序，或者为那些没有自然顺序的对象 collection 提供排序。

当且仅当对于一组元素S中的每个e1和e2而言，c.compare(e1, e2)==0与e1.equals(e2)具有相等的布尔值时，Comparatorc强行对S进行的排序才叫做与 equals 一致 的排序。

当使用具有与 equals 不一致的强行排序能力的 Comparator 对有序 set（或有序映射）进行排序时，应该小心谨慎。假定一个带显式 Comparatorc的有序 set（或有序映射）与从 setS中抽取出来的元素（或键）一起使用。如果c强行对S进行的排序是与 equals 不一致的，那么有序 set（或有序映射）将是行为“怪异的”。尤其是有序 set（或有序映射）将违背根据equals所定义的 set（或映射）的常规协定。

例如，假定使用 Comparator c 将满足 (a.equals(b) && c.compare(a, b) != 0) 的两个元素a 和 b 添加到一个空 TreeSet 中，则第二个 add 操作将返回 true（树 set 的大小将会增加），因为从树 set 的角度来看，a 和b 是不相等的，即使这与 Set.add 方法的规范相反。

注：通常来说，让 Comparator 也实现java.io.Serializable是一个好主意，因为它们在可序列化的数据结构（像 TreeSet、TreeMap）中可用作排序方法。为了成功地序列化数据结构，Comparator（如果已提供）必须实现Serializable。

在算术上，定义给定 Comparatorc对给定对象 setS实施强行排序 的关系式 为：

       {(x, y) such that c.compare(x, y) <= 0}.

此整体排序的商 (quotient) 为：

       {(x, y) such that c.compare(x, y) == 0}.
 

它直接遵循compare的协定，商是S上的等价关系，强行排序是S上的整体排序。当我们说c强行对S的排序是与 equals 一致 的时，意思是说排序的商是对象的 equals(Object) 方法所定义的等价关系：

       {(x, y) such that x.equals(y)}. 

此接口是 Java Collections Framework 的成员。

方法详细信息：

compare

int compare(T o1,
            T o2)

比较用来排序的两个参数。根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。

在前面的描述中，符号sgn(expression)表示 signum 数学函数，根据expression 的值为负数、0 还是正数，该函数分别返回-1、0或1。

实现程序必须确保对于所有的x和y而言，都存在sgn(compare(x, y)) == -sgn(compare(y, x))。（这意味着当且仅当compare(y, x)抛出异常时compare(x, y)才必须抛出异常。）

实现程序还必须确保关系是可传递的：((compare(x, y)>0) && (compare(y, z)>0))意味着compare(x, z)>0。

最后，实现程序必须确保compare(x, y)==0意味着对于所有的z而言，都存在sgn(compare(x, z))==sgn(compare(y, z))。

虽然这种情况很普遍，但并不 严格要求(compare(x, y)==0) == (x.equals(y))。一般说来，任何违背这个条件的 Comparator 都应该清楚地指出这一事实。推荐的语言是“注意：此 Comparator 强行进行与 equals 不一致的排序。”

参数：

o1 - 要比较的第一个对象。

o2 - 要比较的第二个对象。

返回：

根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。

抛出：

ClassCastException - 如果参数的类型不允许此 Comparator 对它们进行比较。

equals

boolean equals(Object obj)

指示某个其他对象是否“等于”此 Comparator。此方法必须遵守 Object.equals(Object) 的常规协定。此外， 仅当 指定的对象也是一个 Comparator，并且强行实施与此 Comparator 相同的排序时，此方法才返回true。因此， comp1.equals(comp2) 意味着对于每个对象引用o1和o2而言，都存在sgn(comp1.compare(o1, o2))==sgn(comp2.compare(o1, o2))。

注意，不 重写Object.equals(Object)方法总是 安全的。然而，在某些情况下，重写此方法可以允许程序确定两个不同的 Comparator 是否强行实施了相同的排序，从而提高性能。

覆盖：

类 Object 中的 equals

参数：

obj - 要进行比较的引用对象。

返回：

仅当指定的对象也是一个 Comparator，并且强行实施与此 Comparator 相同的排序时才返回 true。

另请参见：

Object.equals(Object), Object.hashCode()