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

Question

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

javaarrayssortingcollectionsjava-8

110

我正在使用JDK-8（x64）。对于Arrays.sort（基本类型），我在Java文档中找到了以下内容：

排序算法是由Vladimir Yaroslavskiy、Jon Bentley和Joshua Bloch开发的双主元快速排序。

对于Collections.sort（对象），我找到了这个"Timsort":

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

如果Collections.sort使用数组，为什么不只调用Arrays.sort或使用双主元QuickSort？为什么要使用Mergesort?

- Quest Monger

10

这是基本类型数组的Javadoc - 对象数组使用归并排序进行排序。 - assylias

2

归并排序总是能够达到nlogn的复杂度，而快速排序有时可能会达到nlogn2。通常情况下，数组的大小不是很大，但集合很容易达到数百万条目，因此冒着nlogn2的风险是不值得的。P.S. 我指的是n的平方求对数后的结果。 - Kumar Saurabh

快速排序的O(n^2)是极端的最坏情况。实际上，它更快。 - James Wierzba

@KumarSaurabh 为什么数组的条目数应该比集合少？两者都可以有最大 int 值... - Puce

2

这个链接非常相关。 - qartal

显示剩余3条评论

5个回答

20

我不知道文档的情况，但在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);
    }
}

因此，在最终情况下，Collections#sort 在幕后使用 Arrays#sort（针对对象元素）。此实现使用合并排序或Tim排序。

- Luiggi Mendoza

17

根据Javadoc文档，只有原始数组使用快速排序算法进行排序。对象数组同样使用归并排序进行排序。

因此，对于对象，Collections.sort似乎使用与Arrays.sort相同的排序算法。

另一个问题是为什么原始数组和对象数组要使用不同的排序算法？

- Puce

2

如许多答案所述。

Quicksort被Arrays.sort用于对原始集合进行排序，因为不需要稳定性（您不会知道或关心在排序中是否交换了两个相同的int）。

对于对象集合的排序，使用MergeSort或更具体地说是Timsort。需要稳定性。 Quicksort不提供稳定性，而Timsort提供稳定性。

Collections.sort委托给Arrays.sort，这就是为什么您会看到javadoc引用MergeSort的原因。

- cogitoboy

1

快速排序在与归并排序相比有两个主要缺点：

当涉及到非原始类型时，它不是稳定的。
它不能保证n log n的性能。

对于原始类型来说，稳定性不是问题，因为没有身份的概念，而是（值）相等。

当对任意对象进行排序时，稳定性很重要。很好的一面是，无论输入如何，归并排序都保证了n log n（时间）的性能。

这就是为什么选择归并排序提供稳定排序（归并排序）以对对象引用进行排序的原因。

- Krutik

2

你的意思是什么意思“不稳定”？ - Arun Gowda

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Holger · Accepted Answer

API保证了一种稳定的排序方式，而快速排序则没有提供。但是，当按照其自然顺序对原始值进行排序时，你不会注意到任何差异，因为原始值没有标识。因此，快速排序可用于原始数组，并且在被认为更有效率时将被使用¹。

对于你可能注意到的对象，当根据它们的equals实现或提供的Comparator判断它们相等时，具有不同身份的对象改变它们的顺序。因此，快速排序不是一个选项。因此，使用归并排序的一个变体，当前的Java版本使用TimSort。这适用于Arrays.sort和Collections.sort，虽然在Java 8中，List本身可能会覆盖排序算法。

¹ 快速排序的效率优势在于可以原地排序，需要更少的内存。但是它的最坏情况性能差，并且无法利用预排序数据的运行数组，而TimSort可以。

因此，排序算法从版本到版本进行了重新设计，但仍保留在现在已经误导人的命名类DualPivotQuicksort中。此外，文档没有跟上步伐，这表明，在规范中不必要地命名一个内部使用的算法是一个坏主意。

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

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