问Java的排序算法是什么

EN

从版本7开始，Oracle实现对大于10个元素的对象数组使用Timsort，对元素数少于10的数组使用Insertion sort。同样的注意事项也适用于Arrays.sort()和Collections.sort()。在旧版本的Java中，使用Merge sort而不是Timsort。

该语言的其他实现(不是Oracle的)可能会使用不同的排序算法，因为这不是规范所要求的。引用Collections的documentation

该类中包含的多态算法的文档通常包括对实现的简要描述。这样的描述应该被视为实现说明，而不是规范的一部分。实现者应该可以自由地替换其他算法，只要规范本身得到遵守。(例如，sort使用的算法不必是合并排序，但它必须是稳定的。)

对于数字基元的排序，JDK7 uses“双轴快速排序”。

Collections.sort()使用修改后的合并排序。Arrays.sort()对原语使用quicksort的变体，对Object排序使用mergesort。

对于Java 7，请阅读下面@SebastianPaaskeTørholm的评论

好的，试着拿出规范的列表。基本上，约定是Collections.sort必须是“稳定的”排序(即相等的元素不会被重新排列)，其中Arrays.sort (对于本机类型数组)可以重新排列它们，因为它们是相同的，所以它有更多的自由来使用不同的(即更快的)算法。here给出了想要稳定合约的理由。此外，还假定比较对象(与原生对象)“更昂贵”(通常是如此)，因此Collections.sort的一个副目标是最大限度地减少比较次数，并且保持稳定。

对于所有版本，Collections.sort最初复制列表(到一个数组)，修改它，然后将排序的元素复制回初始列表，排序链表的复杂度为avoid O(n^2)。我猜他们认为额外的副本不会太贵，因为它只是复制引用，而不是实际的值(?)。

JDK6中的：

本机类型：tuned quicksort的数组

 * The sorting algorithm is a tuned quicksort, adapted from Jon
 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
 * 1993).  This algorithm offers n*log(n) performance on many data sets
 * that cause other quicksorts to degrade to quadratic performance.

它被认为是这种改进的快速排序的二次“最坏情况”O(n^2)行为是not a problem的。

Quicksort本身被选择用于performance。

对象列表：modified mergesort

 * The sorting algorithm is a modified mergesort (in which the merge is
 * omitted if the highest element in the low sublist is less than the
 * lowest element in the high sublist).  This algorithm offers guaranteed
 * n log(n) performance. 

“它is了一个相当快的稳定的排序，保证了O(n log n)的性能并且需要O(n)额外的空间。”

它也默认为small arrays的插入排序。

JDK7：

本机类型：dual-pivot quicksort的数组

 * ...The sorting algorithm is a Dual-Pivot Quicksort
 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 * offers O(n log(n)) performance on many data sets that cause other
 * quicksorts to degrade to quadratic performance, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.

“新算法将掉期的平均数量reduces了20%.”

还有一些are阈值，如果大小“低于x”，它将只执行计数排序、插入排序或快速排序，而不是“双轴快速排序”。(取决于排序的基元类型) https://stackoverflow.com/a/41129231/32453

List of Objects：Timsort是一种hybrid合并/插入排序。

“它是一种稳定的、自适应的、迭代的合并排序，当在部分排序的数组上运行时，它需要远少于n个log(n)比较，而当在随机数组上运行时，它提供了与传统合并排序相当的性能。像所有正确的合并排序一样，timsort是稳定的，并且运行时间为O(n log n)时间(最坏情况)。在最坏的情况下，timsort需要用于n/2个对象引用的临时存储空间；在最好的情况下，它只需要少量恒定的空间。与此形成对比的是，当前的实现总是需要额外的空间来存储n个对象引用，并且只在几乎排序的列表上击败n个log n。”

对于高度有序的数据，此代码的运行速度最高可达当前实施的25倍。

"1) log O(n* Guaranteed (N))或更少的具有低常数的比较。2)精确的n-1个预先排序(或重新排序)数据的比较。3)稳定排序。“

您可以恢复使用带有环境的LegacyMergeSort。设置。

JDK8：

本机类型为：dual-pivot quicksort的数组，在JDK7上做了一些小的修改(什么？)。

对象列表: Timsort (相同)

并行排序：？

JDK9：

原生类型为：dual-pivot quicksort的数组，至少包含一些小的modifications，因此如果数据“主要是有序的”，它将只对其执行修改后的合并排序。

对象列表：Timsort (相同)

并行排序：？

JDK10：

本机类型的数组：dual-pivot quicksort，一些修改已经proposed。

对象列表: Timsort (相同)

并行排序：？

这是一个社区维基，请随时更新和/或详细说明。