为什么Collections.sort使用Mergesort而Arrays.sort不使用？

Question

我使用的是JDK-8（x64）。对于＜code＞数组。sort＜/code＞（原语）我在Java文档中找到了以下内容：

排序算法是弗拉基米尔·雅罗斯拉夫斯基、乔恩·本特利和约书亚·布洛赫的双轴快速排序。'

对于＜code＞集合。sort（对象）我找到了这个“Timsort”：

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

如果 Collections.sort 使用数组，为什么它不只调用 Arrays.sort 或使用双透视快速排序？为什么使用合并排序？

Answer 1

根据Javadoc，只有原始数组使用快速排序进行排序。对象数组也使用Mergesort进行排序。

所以Collections.sort似乎使用了与Arrays.sort对象相同的排序算法。

另一个问题是，为什么对基元数组使用不同于对象数组的排序算法？

Answer 2

我不知道留档，但Java8（HotSpot）中java.util.集合#排序的实现是这样的：

@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在幕后使用数组#sort（对象元素的）。此实现使用合并排序或tim排序。

Answer 3

API保证了快速排序无法提供的稳定排序。但是，当按原始值的自然顺序对其进行排序时，您不会注意到差异，因为原始值没有标识。因此，快速排序可用于原始数组，并将在被认为更有效时使用。

对于对象，您可能会注意到，当根据其< code>equals实现或提供的< code>Comparator被视为相等的具有不同标识的对象改变它们的顺序时。因此，快速排序不是一个选项。所以使用了MergeSort的一个变种，当前的Java版本使用TimSort。这适用于< code>Arrays.sort和< code>Collections.sort两者，尽管是用Java

快速排序的效率优势是就地完成时需要更少的内存。但是它有一个戏剧性的最坏情况下的性能，并且不能利用一个数组中预排序的数据，而TimSort可以。

因此，排序算法从一个版本到另一个版本进行了重新设计，同时保留了现在被误导命名的类 DualPivotQuicksort。此外，文档没有赶上，这表明，在没有必要的时候，在规范中命名内部使用的算法通常是一个坏主意。

当前情况(包括Java

• 通常，基本数组的排序方法仅在特定情况下使用Quicksort。对于较大的数组，它们将尝试首先识别预排序html" target="_blank">数据的运行，就像TimSort一样，并在运行次数不超过某个阈值时将它们合并。否则，它们将返回到Quicksort，但对于小范围，实现将返回到Insertion排序，这不仅影响小数组，也影响快速排序的递归
• sort（char[]，…）和sort（short[]，，…）添加另一种特殊情况，以对长度超过特定阈值的数组使用计数排序
• 同样，sort（byte[]，…）将使用计数排序，但阈值要小得多，这与文档形成了最大的对比，因为sort（byte[]…）从不使用Quicksort。它只对小数组使用插入排序，否则使用计数排序