Java 7 是否将 Tim Sort 用于方法 Arrays.Sort? [英] Is Java 7 using Tim Sort for the Method Arrays.Sort?

问题描述

我找不到Java 7的文档，我只能找到关于Java 6的，它仍然很快或merge.有谁知道如何在 Java 7 中找到方法 Arrays.sort 的文档?

解决方案

Java 7 对原语使用双枢轴快速排序，对对象使用 TimSort.

根据原语的 Java 7 API 文档:

<块引用>

实现说明:排序算法是一个双枢轴快速排序弗拉基米尔·雅罗斯拉夫斯基、乔恩·本特利、和约书亚·布洛赫.这个算法在许多方面提供 O(n log(n)) 性能导致其他快速排序的数据集降级到二次性能，并且通常比传统(单轴)快速排序实现.

根据对象的 Java 7 API 文档:

<块引用>

该实现改编自蒂姆·彼得斯 (Tim Peters) 的 Python 列表排序 (提姆排序).它使用了 Peter 的技术麦克罗伊的乐观排序和信息论的复杂性"，在第四届会议纪要ACM-SIAM 离散研讨会算法，第 467-474 页，1993 年 1 月.

Timsort 是合并排序和插入排序"的混合体.

不确定这是否与 Java 6 中的有很大不同， Arrays.sort JDK6:><块引用>

调整后的快速排序，改编自 Jon L.Bentley 和 M. Douglas McIlroy's设计排序功能"，软件实践和经验，卷.23(11) P. 1249-1265(1993 年 11 月)

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

I can't find the documentation of Java 7, I can only find about the Java 6, which is still quick or merge. Does anyone know how to find the documentation of the method Arrays.sort in Java 7?

解决方案

Java 7 uses Dual-Pivot Quicksort for primitives and TimSort for objects.

According to the Java 7 API doc for primitives:

Implementation note: 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.

According to the Java 7 API doc for objects:

The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techiques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

Timsort is a hybrid "merge sort and insertion sort."

Not sure if this is much different from what it was in Java 6, for Arrays.sort JDK6:

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)

For Object[] or collections (Collections.sort()) merge sort is used.

这篇关于Java 7 是否将 Tim Sort 用于方法 Arrays.Sort?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！