logo标签列表

Java 7是否在Arrays.Sort方法中使用Tim Sort算法？

javaarrayssortingtimsort
55

我找不到Java 7的文档，只能找到Java 6的文档，那里还是快速排序或合并排序。有人知道如何找到Java 7中Arrays.sort方法的文档吗？

4
它们比快速排序和归并排序更好。 - Osvaldo
1
可能是Java的排序算法是什么的重复问题。 - rogerdpack
3个回答
90

Java7使用双轴快速排序算法对原始类型进行排序，使用TimSort算法对对象进行排序。

根据Java 7 API文档中有关原始类型的说明：

实现注意事项：该排序算法是由Vladimir Yaroslavskiy、Jon Bentley和Joshua Bloch设计的双轴快速排序算法。这种算法在许多数据集上提供O(n log(n))性能，而其他快速排序算法会降级到二次性能，并且通常比传统（单轴）快速排序实现更快。

根据Java 7 API文档中有关对象的说明：

该实现是从Python的Tim Peters列表排序中改编而来(TimSort)。它使用了Peter McIlroy的“乐观排序和信息理论复杂性”中的技术，发表于第四届ACM-SIAM离散算法年会论文集，pp 467-474，1993年1月。

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

不确定这是否与JDK6中的Arrays.sort JDK6有很大差异：

一个经过调整的快速排序算法，改编自Jon L. Bentley和M. Douglas McIlroy的“工程化排序函数”，《软件实践与经验》杂志第23卷第11期，第1249-1265页（1993年11月）。对于Object[]或集合（Collections.sort()），使用归并排序。
3
好的，谢谢。对于基本数据类型，它使用双轴快速排序算法，而对于对象，则使用Tim Sort算法。 - Osvaldo
1
有没有想法为什么在对象上使用timsort而在原始数据上使用双轴快速排序？可能是内存方面的考虑吗？ - mR_fr0g
1
@Przemek: 根据文档，它是相同的。 - Michael Borgwardt
2
令人困惑的是，实现原始排序的类被称为 DualPivotQuicksort - 但它实际上实现了至少4种不同的排序算法(其中只有一种是快速排序)，并使用启发式方法在它们之间进行选择。例如，byte数组永远不会使用快速排序进行排序，并且“结构化”的数组（已经具有大量有序性）将使用归并排序进行排序（这与 timsort 有很多共同之处）。 - BeeOnRope
1
Timsort显然非常不同：https://www.reddit.com/r/programming/comments/9jj5z/vladimir_yaroslavskiys_dualpivot_quicksort/c0d0spf - rogerdpack
显示剩余6条评论
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）中，根据被排序数组的大小、基本类型和数组的“有序性”进行了各种启发式算法的使用。以下是一个概述：
  • 对于除了字节以外的所有原始类型，长度小于47的数组将使用插入排序进行简单排序（参见DualPivotQuicksort.INSERTION_SORT_THRESHOLD）。当合并或快速排序时，子数组的大小低于阈值时，也会使用此阈值。因此，在所有排序中都将使用某种形式的插入排序，对于小型数组，它是唯一使用的算法。
  • 对于原始类型byte、short和char，在大型数组中使用计数排序。这是一种简单的排序，需要O(n + range)的时间，其中range是字节（256）或短/字符（65536）值的总数。排序涉及分配包含range值的基础数组，因此仅在要排序的元素数量占总范围的显着部分时才使用。特别地，用于大于29个元素的字节数组（即范围的约11％），以及大于3200个元素的短/字符数组（约5％的范围）。
  • 对于字节数组，始终使用上述两种方法之一。
  • 对于插入排序阈值以上的int和long数组，以及插入排序阈值以上且计数排序阈值以下的short/char数组，可以使用两种算法之一：双轴快速排序或归并排序。使用哪个取决于数组的有序性度量：输入被分成升序或降序元素的运行。如果此类运行的数量大于66，则认为数组大部分未排序，并使用双轴快速排序进行排序。否则，认为数组大部分已排序，并使用归并排序（使用已枚举的运行作为起点）。
“找到运行并使用归并排序对其进行排序”的想法实际上与TimSort非常相似，尽管存在一些差异。因此，至少对于某些参数，JDK正在使用基于运行的归并排序，但对于许多其他参数组合，它正在使用不同的算法，总共使用了至少5种不同的算法！”
“背景”
“Object[]与基本类型之间不同的排序行为的推理可能至少有两个方面：”
“1）需要对Object[]进行稳定排序：排序相等的对象将按照输入顺序出现。对于原始数组，不存在这样的概念：原语完全由其值定义，因此稳定和不稳定排序之间没有区别。这使得原始排序可以放弃稳定算法而选择速度。”
2) Object[]的排序需要涉及Object.compare()方法，这可能是任意复杂和昂贵的。即使compare()方法很简单，除非整个排序方法可以内联2，否则通常会有方法调用开销。因此，Object[]的排序通常会倾向于最小化总比较次数，即使这样做会增加一些算法复杂度。

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

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

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

2 这似乎不太可能，因为它非常大。

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

我不立即看到Timsort在源代码中可能用于原始数组的地方...？ - rogerdpack
2
@rogerdpack - 你是对的，我可能弄错了或者看了与我现在看到的不同版本的源代码。至少在JDK8中，原始排序委托给DualPivotQuicksort，它使用各种策略：通常对于“结构化”（即长运行）数据使用普通归并排序，对于非结构化数据使用快速排序，以及其他像计数排序这样的字节值策略。我会更新答案。 - BeeOnRope
1
@rogerdpack - 我更新了问题。似乎在某个时候（在“详细信息”部分），我已经理解了原始数据只使用了归并排序，而不是真正的timsort，但两种算法实际上有些相似：都是“运行感知的归并排序”。无论如何，现在介绍应该更准确了。 - BeeOnRope
22
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接