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

存在与arrays相关的问题，要求时间复杂度为O（n）且空间复杂度为O（1）。

如果我使用Arrays.sort(arr) ，并使用for循环到一个传递循环，例如：

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

}

因此循环将花费O（n）时间。我的问题是： Arrays.sort()花费更多时间吗？如果我使用Arrays.sort() ，这次复杂性仍然是O（n）吗？并且Arrays.sort()花费更多空间吗？

我假设你在这里谈论Java。

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

是的，我所知道的所有Java标准库实现中的Arrays.sort(int[])都是基于比较的排序的一个例子，因此必须具有最坏情况复杂度Ω（n log n）。特别是，Oracle Java 7对整数重载使用双枢轴快速排序变量，实际上具有Ω（n ² ）最坏情况。

并且Arrays.sort（）会花费更多空间吗？

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

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

使用恒定范围的输入整数（例如，如果abs(A[i]) <= C表示某个常数C），那么计算排序和基数排序确实只使用O（n）时间和O（1）空间，这样可能有用。

它超过O（n）时间并且需要超过O（1）空间。

Arrays.sort（）利用1.7中的修改后的Timsort ，它是一种相对最近开发的排序算法，它提供了复杂度x的排序，其中O（n）

最近JDK中的Arrays.sort（int [] a）是使用双枢轴Quicksort算法实现的，该算法具有O（n log n）平均复杂度并且就地执行（例如，不需要额外的空间）。

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

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

所以它会把你的时间复杂度从O（n）增加到O（n log（n））