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

arrays sorting collections java java-8

2022-08-31 09:48:00

我使用的是 JDK-8 （x64）。对于（原语），我在Java文档中发现了以下内容：Arrays.sort

排序算法是Vladimir Yaroslavskiy，Jon Bentley和Joshua Bloch的Dual-Pivot Quicksort。

对于（对象），我发现这个“Timsort”：Collections.sort

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

如果使用数组，为什么它不直接调用或使用双透视快速排序？为什么使用 Mergesort？Collections.sortArrays.sort

答案 1

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

对于对象，您可能会注意到，当具有不同标识的对象根据其实现或提供的实现被视为相等时，它们会更改其顺序。因此，快速排序不是一个选项。因此，使用了MergeSort的变体，当前的Java版本使用TimSort。这两者都适用于，尽管在 Java 8 中，它本身可能会覆盖排序算法。equalsComparatorArrays.sortCollections.sortList

¹快速排序的效率优势在于，就地完成时需要的内存更少。但它具有戏剧性的最坏情况性能，并且无法利用数组中预排序数据的运行，而TimSort就是这样做的。

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

目前的情况（包括Java 8到Java 11）如下：

通常，基元数组的排序方法仅在特定情况下使用快速排序。对于较大的数组，它们将首先尝试识别预排序数据的运行，就像 TimSort 所做的那样，并在运行次数不超过某个阈值时合并它们。否则，它们将回退到 Quicksort，但实现将回退到小范围的插入排序，这不仅会影响小数组，还会影响快速排序的递归。
sort(char[],…)并添加另一个特殊情况，对长度超过特定阈值的数组使用计数排序sort(short[],…)
同样，将使用计数排序，但阈值要小得多，这与文档形成了最大的对比，因为从不使用快速排序。它仅对小数组使用插入排序，否则使用计数排序。sort(byte[],…)sort(byte[],…)

答案 2

我不知道文档，但是在Java 8（HotSpot）中的实现是这样的：java.util.Collections#sort

@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);
    }
}

因此，最后，在幕后使用Arrays#sort（对象元素）。此实现使用合并排序或 tim 排序。Collections#sort