Arrays.sort（） 会增加时间复杂性和时空复杂性吗？

Question

有一个与数组相关的问题，要求是时间复杂度为O（n），空间复杂度为O（1）。

如果我使用< code>Arrays.sort(arr)，并使用< code>for循环进行一次循环，例如:

public static int hello(int[]A){
  Arrays.sort(A);
  for(int i=0;i<A.length;i++){
     ....................
  }
  return ....;

}

所以循环将花费O(n)时间。我的问题是:< code>Arrays.sort()会花费更多时间吗？如果我使用< code>Arrays.sort()，这个时间复杂度还是O(n)吗？< code>Arrays.sort()会占用更多空间吗？

Answer 1

最近JDK中的Arrays.sort(int[] a)是用双支点快速排序算法实现的，该算法具有O(n log n)的平均复杂度，并且是就地执行的(例如，不需要额外的空间)。

Answer 2

根据java jvm 8 javadocs的Arrays.sort（）方法：

排序算法是Vladimir Yaroslavskiy、Jon Bentley和Joshua Bloch的Dual-Pivot Quick排序。该算法在许多数据集上提供O（n log（n））性能，导致其他快速排序降级为二次性能，并且通常比传统的（one-pivot）Quick排序实现更快。

因此，它将增加从O（n）到O（n log（n））的时间复杂度

Answer 3

我假设你在这里谈论的是Java。

所以循环将花费O（n）时间，我的问题是Arrays.sort（）会花费更多的时间吗？

是的，数组。排序（int[]）在我所知道的所有Java标准库实现中，都是基于比较的排序的示例，因此必须具有最坏情况复杂度Ω（n logn）。特别是，Oracle Java 7对整数重载使用了双枢轴快速排序变体，这实际上是Ω（n²）最坏情况。

Arrays.sort（） 会占用更多空间吗？

它很可能会使用ω（1）空间（这意味着另一个是，空间使用不是O（1））。虽然实现基于比较的排序并非不可能，只有恒定的额外空间，但它是非常不切实际的。

也就是说，在某些情况下，可以在线性时间内对特定类型的数据进行排序，例如：

• 这是一个很好的例子http://en.wikipedia.org/wiki/Counting_sort
• 这是一个很好的例子http://en.wikipedia.org/wiki/Pigeonhole_sort
• 这是一个很好的例子http://en.wikipedia.org/wiki/Radix_sort这是一个很好的例子

具有恒定范围的输入整数（例如，如果abs（A[i]）