Java Arrays.sort() 会增加时间复杂度和空间时间复杂度吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22571586/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Will Arrays.sort() increase time complexity and space time complexity?
提问by aminy
There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1).
有一个数组相关的问题，要求时间复杂度为O(n)，空间复杂度为O(1)。
If I use Arrays.sort(arr), and use a forloop to one pass loop, for example:
如果我使用Arrays.sort(arr), 并使用一个for循环到一个传递循环，例如：
public static int hello(int[]A){
Arrays.sort(A);
for(int i=0;i<A.length;i++){
....................
}
return ....;
}
}
So the loop will cost O(n) time. My question is: will Arrays.sort()cost more time? If I use Arrays.sort(), will this time complexity still be O(n)? And will Arrays.sort()cost more space?
所以循环将花费 O(n) 时间。我的问题是：会Arrays.sort()花费更多时间吗？如果我使用Arrays.sort()，这个时间复杂度仍然是 O(n) 吗？并且会Arrays.sort()花费更多空间？
采纳答案by Niklas B.
I am assuming you are talking about Java here.
我假设您在这里谈论的是 Java。
So the loop will cost O(n) time, my question is that will Arrays.sort() cost more time?
所以循环将花费 O(n) 时间，我的问题是 Arrays.sort() 会花费更多时间吗？
Yes, Arrays.sort(int[])in all Java standard library implementations that I know, is an example of a comparison-based sort and thus must have worst-case complexity Ω(n log n). In particular, Oracle Java 7 uses a dual-pivot quicksort variant for the integer overloads, which actually has an Ω(n2)worst case.
是的，Arrays.sort(int[])在我知道的所有 Java 标准库实现中，都是基于比较的排序的一个示例，因此必须具有最坏情况复杂度 Ω(n log n)。特别是，Oracle Java 7 对整数重载使用双枢轴快速排序变体，它实际上具有Ω(n 2)最坏情况。
and will Arrays.sort() cost more space?
Arrays.sort() 会占用更多空间吗？
In all likelihood it will use ω(1) space (which means another yes, the space usage is not O(1)). While it's not impossible to implement a comparison-based sort with only constant extra space, it's highly impractical.
它很可能会使用 ω(1) 空间（这意味着另一个是，空间使用不是 O(1)）。虽然仅使用恒定的额外空间来实现基于比较的排序并非不可能，但这是非常不切实际的。
That said, under certain conditions it is possible to sort specific types of data in linear time, see for example:
也就是说，在某些条件下，可以在线性时间内对特定类型的数据进行排序，例如：
- http://en.wikipedia.org/wiki/Counting_sort
- http://en.wikipedia.org/wiki/Pigeonhole_sort
- http://en.wikipedia.org/wiki/Radix_sort
- http://en.wikipedia.org/wiki/Counting_sort
- http://en.wikipedia.org/wiki/Pigeonhole_sort
- http://en.wikipedia.org/wiki/Radix_sort
With a constant range of input integers (for example if abs(A[i]) <= Cfor some constant C), then counting sort and radix sort use indeed only O(n) time and O(1) space, so that might be useful.
对于恒定范围的输入整数（例如，如果abs(A[i]) <= C对于某个常量 C），那么计数排序和基数排序实际上仅使用 O(n) 时间和 O(1) 空间，因此这可能很有用。
回答by Hypothetical inthe Clavicle
It is more than O(n) time and requires more than O(1) space.
它的时间超过 O(n) 并且需要超过 O(1) 的空间。
Arrays.sort()utilizes a modified Timsortin 1.7 which is a relatively recently developed sorting algorithm and it offers sorting with complexity x where O(n)< x < O(nlgn) and space of O(n/2)
Arrays.sort()使用了1.7 中的修改Timsort，这是一种相对较新开发的排序算法，它提供复杂度为 x 的排序，其中 O(n)< x < O(nlgn) 和空间为 O(n/2)
回答by apangin
Arrays.sort(int[] a) in recent JDK is implemented with Dual-pivot Quicksort algorithm which has O(n log n) average complexity and is performed in-place (e.g. requires no extra space).
最近 JDK 中的 Arrays.sort(int[] a) 是用双枢轴快速排序算法实现的，该算法具有 O(n log n) 平均复杂度并且就地执行（例如不需要额外的空间）。
回答by pedrogonzalezj
According to the java jvm 8 javadocs of Arrays.sort() method:
根据 Arrays.sort() 方法的 java jvm 8 javadocs：
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.
排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的双枢轴快速排序。该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降级为二次性能，并且通常比传统（单轴）快速排序实现更快。
So it will increase your time complexity from O(n) to O(n log(n))
所以它会将你的时间复杂度从 O(n) 增加到 O(n log(n))
