Java 7 是否对方法数组使用 Tim Sort。Sort？

Java 7 对基元使用 Dual-Pivot Quicksort，对对象使用 TimSort。

根据 Java 7 API 的原语文档：

实现说明：排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的 Dual-Pivot Quicksort。此算法在许多数据集上提供 O（n log（n）） 性能，这些数据集会导致其他快速排序降级为二次性能，并且通常比传统的（单透视）快速排序实现更快。

根据对象的 Java 7 API 文档：

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

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（）），使用合并排序。

是的！...也没有。

总结

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

对于基元，启发式方法可在各种排序方法中进行选择，例如快速排序、合并排序、计数排序³。取决于要排序的数据。这些决策中的大多数只是根据所排序数组的类型和大小预先做出的，但对于元素，决策实际上是基于数组的测量排序的自适应的。因此，在许多情况下，您在适应/内省（TimSort或类似的合并排序）之上具有适应/内省（选择算法的启发式方法）！intlong

详

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

对于基元，情况更为复杂。至少从JDK 8（版本）开始，根据要排序的数组的大小，基元类型和数组的测量“排序”，使用各种启发式。以下是概述：1.8.0_111

• 对于除字节¹ 以外的所有基元类型，小于 47 个元素的数组只需使用插入排序进行排序（请参见）。当对使用合并或快速排序且子数组的大小低于阈值时出现的子数组进行排序时，也会使用此阈值。因此，某种形式的插入排序将用于所有排序，对于小数组，它是唯一使用的算法。DualPivotQuicksort.INSERTION_SORT_THRESHOLD
• 对于基元类型，和 ，计数排序用于大数组。这是一个需要时间的简单排序，其中是字节 （256） 或短/字符 （65536） 值的总数。排序涉及分配基础值数组，因此仅当要排序的元素数是总范围的很大一部分时才使用它。特别是，它用于大于 29 个元素（即范围的 ~11%）的字节数组，以及大于 3200 个元素（约 5% 范围的 short/char）数组。byteshortcharO(n + range)rangerange
• 对于字节数组，始终使用上述两种方法之一。
• 对于高于插入排序阈值的 和 数组，对于同时高于插入排序阈值且低于计数排序阈值的 / 数组，可以使用以下两种算法之一：双透视快速排序或合并排序。使用哪一个取决于数组排序的度量：输入被划分为升序或降序元素的运行。如果此类运行次数大于 66，则数组被视为大部分未排序，并使用双透视快速排序进行排序。否则，数组将被视为主要排序，并使用合并排序（使用已枚举的运行作为起点）。intlongshortchar

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

理由

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

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

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

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

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

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

² 这似乎不太可能，因为它很大。

³ 计数排序仅用于范围相对有限（16 位或更小）的值：、 或 。byteshortchar