Java 7是否使用Tim Sort for Method Arrays.Sort？

Question

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

Answer 1

Java 7使用Dual-Pivot Quicksort作为基元,使用TimSort作为对象.

根据基元的Java 7 API doc:

实施说明:排序算法是Vladimir Yaroslavskiy,Jon Bentley和Joshua Bloch的双枢轴快速算法.该算法在许多数据集上提供O(n log(n))性能,导致其他快速降序降级为二次性能,并且通常比传统(单枢轴)Quicksort实现更快.

根据对象的Java 7 API doc:

该实现改编自Tim Peters的Python排序(TimSort).它使用了Peter McIlroy的"乐观排序和信息理论复杂性"中的技术,参见"第四届年度ACM-SIAM离散算法研讨会论文集",第467-474页,1993年1月.

Timsort是一种混合"合并排序和插入排序".

对于 Arrays.sort JDK6 ,不确定它是否与Java 6中的有很大不同:

一个改编的快速排序,改编自Jon L. Bentley和M. Douglas McIlroy的"工程排序功能",软件实践和经验,卷.23(11)P.1249-1265(1993年11月)

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

Answer 2

是! ......也没有.

摘要

在当前的Open JDK ⁰实现中,Tim Sort通常用于排序对象数组(即Arrays.sort(Object[])和朋友) - 但对于原始数组(Arrays.sort方法的其余部分),使用了各种其他方法.

对于原语,启发式选择各种排序方法,如快速排序,合并排序,计数排序³.取决于正在排序的数据.大多数这些决策都是根据被排序的数组的类型和大小预先制作的,但是对于int和long元素,决策实际上是基于测量的数组排序的自适应性.因此,在许多情况下,您可以在自适应/内省(TimSort或类似的合并排序)之上进行自适应/内省(选择算法的启发式方法)!

细节

Tim Sort用于大多数对象,例如Arrays.sort(Object[] a),除非用户通过将system属性设置java.util.Arrays.useLegacyMergeSort为true来专门请求遗留行为.

对于原始人来说,情况更复杂.至少从JDK 8(版本1.8.0_111)开始,根据被排序的数组的大小,基元类型和阵列的测量"排序",使用各种各样的heurstics.这是一个概述:

• 对于除字节¹之外的所有基本类型,使用插入排序(参见DualPivotQuicksort.INSERTION_SORT_THRESHOLD)简单地对少于47个元素的数组进行排序.在对使用合并或快速排序时出现的子阵列进行排序时,也会使用此阈值,并且子阵列的大小低于阈值.因此,某种形式的插入排序将在所有种类中使用,对于小型数组,它是唯一使用的算法.
• 对于原始类型byte,short并且char,一个计数排序用于稍大阵列.这是一种需要O(n + range)时间的简单排序,其中range是字节(256)或短/字符(65536)值的总数.排序涉及分配基础range值的数组,因此仅在要排序的元素数量占总范围的重要部分时使用.特别是,它用于大于29个元素的字节数组(即范围的~11%),以及大于3200个元素的短/字符数组(约为范围的5%).
• 对于字节数组,始终使用上述两种方法之一.
• 对于int和long上述插入排序阈阵列和用于short/ char上述两种插入排序阈值且低于所述计数排序阈值阵列中,两个算法之一可以被使用:双枢轴快速排序,或归并排序.哪一个被使用取决于阵列的有序性的量度:输入被分成运行升序或降序元件.如果此类运行的数量大于66,则该阵列主要被视为未排序,并使用双轴快速排序进行排序.否则,数组被认为主要是排序的,并且使用mergesort(使用已经枚举的运行作为起点).

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

合理

Object[]对于原语的不同排序行为背后的原因可能至少是双重的:

1)Object[]要求稳定的类别:平均排序的对象将以与输入相同的顺序出现.对于原始数组,不存在这样的概念:基元完全由它们的值定义,因此稳定和不稳定排序之间没有区别.这允许原始类型省去了有利于速度的稳定算法的需要.

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

另一方面,各种原始数组只是直接比较原始值,这些原始值通常采用一个或两个循环的顺序.在这种情况下,应该考虑比较的成本和周围的算法来优化算法,因为它们可能具有相同的幅度.

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

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

²这似乎不太可能,因为它非常大.

³计数排序仅用于16位或更小范围相对有限的值:byte,short或char.

Answer 3

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