为什么Collections.sort使用Mergesort但是Arrays.sort却没有？

Question

我使用的是JDK-8(x64).对于Arrays.sort(primitives),我在Java文档中找到了以下内容:

该排序算法是一个双枢轴快速排序弗拉基米尔·Yaroslavskiy,乔恩·本特利,以及约书亚Bloch.`

对于Collections.sort(对象),我发现了这个"Timsort":

这个实现是一个稳定的,自适应的,迭代的mergesort ......这个实现将指定的列表转储到一个数组中,对数组进行排序,并迭代列表,从数组中的相应位置重置每个元素.

如果Collections.sort使用数组,为什么不调用Arrays.sort或使用双枢轴QuickSort？为什么要使用Mergesort？

Answer 1

API保证了Quicksort不提供的稳定排序.但是,当按原样顺序对原始值进行排序时,您不会注意到差异,因为原始值没有标识.因此,Quicksort用于原始数组,因为它稍微更高效.

对于您可能注意到的对象,当根据其equals实现被认为相等的对象或提供的对象Comparator改变其顺序时.因此,Quicksort不是一个选择.因此使用MergeSort的变体,当前的Java版本使用TimSort.这适用于,Arrays.sort与Collections.sort,虽然与Java 8中,List本身可以覆盖排序算法.

Answer 2

我不知道文档,但java.util.Collections#sortJava 8(HotSpot)的实现如下:

@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

而List#sort有这样实现:

@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

所以,最后,在幕后Collections#sort使用Arrays#sort(对象元素).此实现使用合并排序或时间排序.

Answer 3

根据Javadoc,只使用Quicksort对原始数组进行排序.对象数组也使用Mergesort进行排序.

因此Collections.sort似乎使用与Arrays.sort for Objects相同的排序算法.

另一个问题是为什么不同的排序算法用于原始数组而不是Object数组？