52

我找不到Java 7的文档，我只能找到关于Java 6的，它仍然是快速或合并的。有谁知道如何Arrays.sort在 Java 7 中找到该方法的文档？

4

3 回答 3

84

Java 7 对原语使用 Dual-Pivot Quicksort，对对象使用 TimSort。

根据Java 7 API doc for primitives：

实施说明：排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的 Dual-Pivot Quicksort。该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降低到二次性能，并且通常比传统的（单轴）快速排序实现更快。

根据对象的 Java 7 API 文档：

该实现改编自 Tim Peters 的 Python 列表排序 (TimSort)。它使用了 Peter McIlroy 在 1993 年 1 月第四届 ACM-SIAM 离散算法年度研讨会论文集上的“乐观排序和信息论复杂性”中的技术。

Timsort是一种混合的“合并排序和插入排序”。

不确定这是否与 Java 6 中的Arrays.sort JDK6 有很大不同：

调整后的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy 的“Engineering a Sort Function”，Software-Practice and Experience，Vol。23(11) P. 1249-1265（1993 年 11 月）

对于 Object[] 或集合 (Collections.sort())，使用合并排序。

于 2010-10-25T20:01:57.917 回答
29

是的！......也没有。

概括

在撰写本文时（2016 年），在当前的 Open JDK 0实现中，Tim Sort 通常用于对对象数组（即Arrays.sort(Object[])和朋友）进行排序 - 但对于原始数组（其余Arrays.sort方法），使用了各种其他方法.

对于原语，启发式方法在多种排序方法中进行选择，例如快速排序、归并排序、计数排序3。取决于被排序的数据。这些决定中的大多数都是根据被排序数组的类型和大小预先做出的，但是对于元素int，long该决定实际上是基于数组的测量排序的自适应的。因此，在许多情况下，您在适应/自省（TimSort 或类似的合并排序）之上还有适应/自省（选择算法的启发式方法）！

细节

Tim Sort 用于大多数类型的对象，例如Arrays.sort(Object[] a)，除非用户通过将系统属性设置java.util.Arrays.useLegacyMergeSort为 true 来特别请求遗留行为。

对于原语，情况更为复杂。至少从 JDK 8（版本1.8.0_111）开始，根据要排序的数组的大小、原始类型和数组的测量“排序性”，使用了各种启发式方法。这是一个概述：

  • 对于除字节1以外的所有原始类型，少于 47 个元素的数组使用插入排序（请参阅 参考资料DualPivotQuicksort.INSERTION_SORT_THRESHOLD）进行简单排序。当对使用合并或快速排序时出现的子数组进行排序并且子数组的大小低于阈值时，也会使用此阈值。因此，某种形式的插入排序将用于所有排序，对于小型数组，它是唯一使用的算法。
  • 对于原始类型和byte，计数排序用于较大的数组。这是一个需要时间的简单排序，其中是字节 (256) 或短/字符 (65536) 值的总数。排序涉及分配一个底层的值数组，因此它仅在要排序的元素数量占总范围的很大一部分时使用。特别是，它用于大于 29 个元素的字节数组（即约 11% 的范围）和大于 3200 个元素的短/字符数组（约 5% 的范围）。shortcharO(n + range)rangerange
  • 对于字节数组，始终使用上述两种方法之一。
  • 对于高于插入排序阈值的和int数组以及高于插入排序阈值和低于计数排序阈值的数组，可以使用以下两种算法之一：双轴快速排序或合并排序。使用哪一个取决于数组排序的度量：输入分为升序或降序元素的运行。如果此类运行的次数大于 66，则认为该数组大部分未排序，并使用双轴快速排序进行排序。否则，该数组被认为大部分已排序，并使用合并排序（使用已经枚举的运行作为起点）。longshortchar

查找运行然后使用归并排序对它们进行排序的想法实际上与 TimSort 非常相似，尽管存在一些差异。因此，至少对于某些参数，JDK 使用了运行感知合并排序，但对于许多其他参数组合，它使用了不同的算法，总共使用了至少 5 种不同的算法！

基本原理

与原始的不同排序行为背后的原因Object[]可能至少有两个：

1) 排序Object[]必须是稳定的：排序相同的对象将以与输入相同的顺序出现。对于原始数组，不存在这样的概念：原始数组完全由它们的值定义，因此稳定排序和不稳定排序之间没有区别。这允许原始排序免除对稳定算法的需要以支持速度。

Object[]2)需要涉及方法的种类Object.compare()，这可能是任意复杂和昂贵的。即使compare()方法很简单，通常也会有方法调用开销，除非整个排序方法可以内联2。因此Object[]，即使以一些额外的算法复杂性为代价，通常也会倾向于最小化总比较。

另一方面，原始数组的排序只是直接比较原始值，这些原始值通常采用一两个周期的顺序。在这种情况下，应该考虑比较的成本和周围的算法来优化算法，因为它们可能具有相同的量级。

0至少对于 Java 7 和 Java 9 之间的版本，当然这也包括 Oracle 的 JDK，因为它基于 Open JDK。其他实现很可能使用类似的方法，但我没有检查过。

1对于字节数组，插入排序阈值实际上是 29 个元素，因为这是使用计数排序的下限。

2这似乎不太可能，因为它相当大。

3计数排序仅用于范围相对有限的 16 位或更少的值byte：short或char。

于 2016-12-13T19:39:22.720 回答
21

是的，Java 7 将为 Arrays.sort 使用 Timsort。这是提交： http ://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/bfd7abda8f79

于 2010-10-25T20:51:26.370 回答