Java 7是否使用Tim Sort作为Method Arrays.Sort?

我找不到Java 7的文档,我只能findJava 6,它仍然很快或合并。 有谁知道如何在Java 7中find方法Arrays.sort的文档?

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

根据基元的Java 7 API文档:

实现注意事项:sortingalgorithm是由Vladimir Yaroslavskiy,Jon Bentley和Joshua Bloch编写的Dual-Pivot Quicksort。 该algorithm在许多数据集上提供了O(n log(n))性能,这些数据集导致其他快速sorting降低到二次性能,并且通常比传统(单枢轴)Quicksort实现更快。

根据对象的Java 7 API文档:

这个实现是从Tim Peters的Python列表类(TimSort)改编的。 它使用Peter McIlroy的“Optimistic Sorting and Information Theoretic Complexity”中的技术,在Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms,第467-474页,1993年1月。

不知道这是否与Java 6有很大不同:

一个经过调整的quicksort,改编自Jon L. Bentley和M. Douglas McIlroy的“Engineering a Sort Function”,Software-Practice and Experience,Vol。 23(11)第1249-1265页(1993年11月)

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

是! …也没有。

概要

在当前的Open JDK 0实现中,Tim Sort通常用于sorting对象数组( Arrays.sort(Object[])和朋友) – 但对于基本数组Arrays.sort方法的其余部分),有多种方法,包括但不限于Tim Sort。 在这种情况下,启发式用来select使用哪种sorting方法。

对于原语,启发式根据所sorting的数据在各种sorting方法中进行select。 这些决定大部分是根据被sorting的数组的types和大小简单地进行的,但是对于intlong元素,决策实际上是基于测量的数组sorting的自适应。 所以在很多情况下,在适应/反思(TimSort)的基础上,你有适应/反省(启发式selectalgorithm)!

细节

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

对于基元而言,情况更为复杂。 从JDK 8(版本1.8.0_111 )开始,根据要sorting的数组的大小,基本types和测量的“sorting”来使用各种heurstics。 这里有一个概述:

  • 对于除字节1以外的所有基本types,less于47个元素的数组仅使用插入sorting进行sorting(请参阅DualPivotQuicksort.INSERTION_SORT_THRESHOLD )。 当使用合并或快速sorting并且子arrays的大小低于阈值时,对sorting的子数组使用此阈值。 所以某种forms的插入sorting将被用于各种types,对于小型数组,这是唯一使用的algorithm。
  • 对于原始typesbyteshortchar , 计数sorting用于较大的数组。 这是一个简单的sorting,需要O(n + range)时间,其中range是字节总数(256)或short / char(65536)值。 这种sorting包括分配一个基本的range值数组,因此只有当要sorting的元素数量占整个范围的很大一部分时才使用它。 特别是用于大于29个元素的字节数组(即〜11%的范围)和大于3200个元素的短/字符数组(〜5%的范围)。
  • 对于字节数组,总是使用上面两种方法中的一种。
  • 对于高于插入sorting阈值的插入sorting阈值和short / char数组,在插入sorting阈值以上和计数sorting阈值以下的intlong数组,可以使用两种algorithm之一:双枢轴快速sorting或合并sorting。 使用哪一个取决于数组sorting的度量:input被分为上升或下降元素的运行 。 如果这样的运行次数大于66,则该arrays被认为是大部分未sorting的,并且用双枢轴快速sorting进行sorting。 否则,数组被认为大部分被sorting,并且使用mergesort(使用已经枚举的运行作为起点)。

查找运行然后使用mergesort对它们进行sorting的想法实际上与timsort非常相似,尽pipe存在一些差异。 所以至less对于一些参数来说,JDK正在使用一个运行感知合并器,但是对于许多其他参数组合,它使用的是不同的algorithm,并且总共使用了至less4个不同的algorithm!

合理

Object[]与primitive之间不同sorting行为的原因可能至less有两方面:

1) Object[]sorting需要稳定 :平均sorting的对象将以与input相同的顺序出现。 对于原始数组,不存在这样的概念:原语完全由它们的值定义,所以在稳定sorting和不稳定sorting之间没有区别。 这就允许原始sorting,而不需要稳定的algorithm来支持速度。

2) Object[]sorting需要涉及Object.compare()方法,这可能是任意复杂和昂贵的。 即使compare()方法很简单,通常会有方法调用开销,除非整个sorting方法可以内联2 。 所以, Object[]通常会偏向于最小化总体比较,即使以一些额外的algorithm复杂度为代价。

另一方面,原始数组的sorting只是直接比较通常需要一个或两个周期的原始值。 在这种情况下,考虑到比较的成本和周围的algorithm,algorithm应该被优化,因为它们可能具有相同的幅度。


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

1对于字节数组,插入sorting阈值实际上是29个元素,因为这是使用计数sorting的较低截止值。

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