Java中Arrays.Sort方法的运行时间 [英] The Running Time For Arrays.Sort Method in Java

问题描述

有人知道arrays.sort java方法的大O表示形式的运行时间吗?我的Science Fair项目需要这个.

Does anyone know the running time in big O notation for the arrays.sort java method? I need this for my science fair project.

推荐答案

来自官方我观察到主要有两种方法.因此，这取决于您正在排序的内容以及您正在调用的 sort 方法族中的重载方法.

I've observed that there are primarily two approaches. So, it depends on what you are sorting and what overloaded method from sort family of methods you are calling.

文档提到原始类型，例如 long ， byte (例如: static void sort(long [])):

Docs mention that for primitive types such as long, byte (Ex: static void sort(long[])):

排序算法是调整后的快速排序，改编自JonL.本特利和道格拉斯·麦克罗伊(M. Douglas McIlroy)的设计排序功能"，软件实践与经验，第一卷.23(11)P.1249-1265(11月1993).该算法可在许多数据集上提供n * log(n)性能导致其他快速排序的性能下降到二次方.

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(nlogn)性能

排序算法是修改后的mergesort(其中合并是如果低子列表中的最高元素小于，则省略高子列表中的最低元素).该算法提供了有保证的n * log(n)性能.

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.

希望有帮助！

这篇关于Java中Arrays.Sort方法的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！