OpenJDK 如何在内部对数据类型进行排序，为什么？如果能提到具体的算法就好了
user1639297
问问题
11372 次
3 回答
23
从版本 7 开始，Oracle 的 Java 实现对大于 10 个元素的对象数组使用Timsort ，对元素少于该数量的数组使用插入排序。相同的考虑适用于Arrays.sort()和Collections.sort()。在旧版本的 Java 中，使用合并排序而不是 Timsort。
该语言的其他实现（除了 Oracle 的）可能使用不同的排序算法，因为规范没有强制要求。引用Collections'文档：
此类中包含的多态算法的文档通常包括对实现的简要描述。此类描述应被视为实现说明，而不是规范的一部分。只要遵守规范本身，实现者应该可以随意替换其他算法。（例如，sort 使用的算法不必是归并排序，但它必须是稳定的。）
对于数字基元排序，JDK 7使用“双轴快速排序”。
于 2012-09-01T14:46:33.180 回答
6
Collections.sort()使用修改后的归并排序。Arrays.sort()对基元使用快速排序的变体，对排序使用归并Object排序。
对于 Java 7，请阅读下面 @SebastianPaaskeTørholm 的评论
于 2012-09-01T14:43:03.743 回答
5
好的，尝试提出规范列表。基本上，合同Collections.sort必须是“稳定”排序（即不会重新排列相等的元素），其中Arrays.sort（对于本机类型数组）可以重新排列它们，因为它们是相同的，所以它有更多的自由使用不同的（即更快的）算法。这里给出了想要稳定合同的理由。还假设比较对象（与本地人相比）“要昂贵得多”（通常是这样），因此副目标Collections.sort是尽量减少比较次数并保持稳定。
对于所有版本，Collections.sort最初制作列表的副本（到数组），对其进行修改，然后将已排序的元素复制回初始列表，以避免对链表进行排序的 O(n^2) 复杂性。猜猜他们认为额外的副本不会太贵，因为它只是复制引用，而不是实际值（？）。
在 JDK 6 中：
本机类型数组：调整的快速排序
* 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) 行为对于这种修改后的快速排序来说不是问题。
选择快速排序本身是为了提高性能。
对象列表：修改后的归并排序
* 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.
“这是一种相当快速的稳定排序，可保证 O(n log n) 性能并需要 O(n) 额外空间。”
它还默认为小数组的插入排序。
JDK 7：
本机类型数组：双轴快速排序
* ...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.
“新算法将平均掉期次数减少了 20%。”
还有一些阈值，如果大小“低于 x”，它将只进行计数排序、插入排序或快速排序，而不是“双轴快速排序”。（取决于正在排序的原语类型）https://stackoverflow.com/a/41129231/32453
“它是一种稳定的、自适应的、迭代的归并排序，当在部分排序的数组上运行时，它需要远少于 n log(n) 的比较，同时在随机数组上运行时提供与传统归并排序相当的性能。像所有适当的归并排序一样，timsort 是稳定的，并且在 O(n log n) 时间内运行（最坏情况）。在最坏情况下，timsort 需要用于 n/2 个对象引用的临时存储空间；在最好的情况下，它只需要少量的恒定空间。将其与当前的实现，它总是需要额外的空间来存储 n 个对象引用，并且仅在几乎排序的列表上优于 n log n。”
“在高度有序的数据上，这段代码的运行速度可以达到当前实现的 25 倍。”
“1)保证O(n*log(n)) 或更少的低常数比较。2) 对预排序（或重新排序）数据进行精确的 n-1 次比较。3）稳定排序。
您可以恢复使用带有 env 的 LegacyMergeSort。环境。
JDK 8：
本机类型数组：双轴快速排序，对 jdk 7 进行了一些小的修改（什么？）。
对象列表：Timsort（相同）
并行排序：？？？
JDK 9：
本机类型数组：双轴快速排序，至少有一些小的修改，所以如果数据“大部分是有序的”，它只会对其进行修改后的合并排序。
对象列表：Timsort（相同）
并行排序：？？？
JDK 10：
对象列表：Timsort（相同）
并行排序：？？？
这是一个社区 wiki，可以随时更新和/或详细说明。
于 2018-07-03T18:46:12.547 回答