有一个涉及数组的问题，要求时间复杂度为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对整数重载使用双轴快速排序变体，其实际上具有Ω(n2)的最坏情况。
Arrays.sort()会占用更多空间吗？
很可能它将使用ω(1)空间（这意味着另一个是的，空间使用不是O(1)）。虽然可以实现只使用恒定额外空间的基于比较的排序，但这是非常不实际的。
话虽如此，在特定条件下，可以在线性时间内对特定类型的数据进行排序，例如：
如果输入整数具有恒定的范围（例如，如果abs(A[i]) <= C对于某个常数C），那么计数排序和基数排序确实只使用O(n)时间和O(1)空间，因此可能非常有用。
Arrays.sort()方法使用双轴快速排序算法（Dual-Pivot Quicksort），该算法由Vladimir Yaroslavskiy，Jon Bentley和Joshua Bloch开发。相较于传统的单轴快速排序实现，该算法提供了O(n log(n))性能，在许多数据集上表现良好，而其他快速排序算法则会退化为二次性能。因此，它将使您的时间复杂度从O(n)增加到O(n log(n))。这个技术要求的时间复杂度不止O(n)，需要更多的空间，但是它可以利用Arrays.sort()在1.7版本中使用修改过的Timsort来进行排序。这是一个比较新的排序算法，它提供的排序复杂度为O(n)<x < O(nlgn)，并且空间复杂度为O(n/2)。
Arrays.sort(int[] a)标准实现使用快速排序，而不是Timsort。由于它是稳定的，因此基于对象的搜索也是如此。参考文献：http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(int[])和http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])。在Java中，对象数组的稳定排序实现是强制性的。 - Cahit GungorArrays.sort重载使用快速排序。操作对象的重载使用了一个改编自Python中Tim Peters列表排序算法的适应性排序算法（TimSort）。 - Reuben Tanner最近JDK中的Arrays.sort(int[] a)方法是使用双轴快排算法实现的，平均复杂度为O(n log n)，且在原地执行（例如不需要额外的空间）。
除了Arrays.sort(long[])、Arrays.sort(float[])和Arrays.sort(double[])之外，
Arrays.sort(int[])的时间复杂度取决于Java的版本。
在Java 14之前为O(n2)
使用普通的快速排序算法，时间复杂度范围从O(n)（当数组已经排序并且我们只是检查它时）到某些输入导致元素极不均匀地分布到具有平均复杂度O(n log(n))的部分，其复杂度为O(n2)。您可以在这里找到详细的分析。
从Java 14开始为O(n log(n))
在Java 14中，实现得到改进以保证O(n log(n))的最坏时间复杂度。如果递归变得太深，该函数将更改为使用堆排序：if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
heapSort(a, low, high);
return;
}
这可以防止该方法退化为二次时间复杂度。
展望未来
有一个initiative计划，针对几乎随机的足够大的数组转换到基数排序，从而将时间复杂度降低到最坏情况下的O(n)。
在所有版本中，算法的空间复杂度范围从O(1)（当数组已经排序并且我们只需要检查它是否已排序）到O(n)（当数组高度结构化时（原始数组中有少量已排序的子数组，并且我们合并这些子数组））。
以下是最坏情况下分配发生的位置：
/*
* Merge runs of highly structured array.
*/
if (count > 1) {
int[] b; int offset = low;
if (sorter == null || (b = (int[]) sorter.b) == null) {
b = new int[size];
} else {
offset = sorter.offset;
}
mergeRuns(a, b, offset, 1, sorter != null, run, 0, count);
}
return true;
除了 Arrays.sort(char[]) 和 Arrays.sort(byte[]) 之外
虽然文档中说：
排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的双轴快速排序。该算法在所有数据集上都能提供 O(n log(n)) 性能，并且通常比传统（单轴）快速排序实现更快。
但至少从 Java 7 开始这是不正确的。实际上，对于足够大的数组使用原地 计数排序 ，其具有线性时间复杂度和恒定空间复杂度：
private static void countingSort(short[] a, int low, int high) {
int[] count = new int[NUM_SHORT_VALUES];
/*
* Compute a histogram with the number of each values.
*/
for (int i = high; i > low; ++count[a[--i] & 0xFFFF]);
/*
* Place values on their final positions.
*/
if (high - low > NUM_SHORT_VALUES) {
for (int i = MAX_SHORT_INDEX; --i > Short.MAX_VALUE; ) {
int value = i & 0xFFFF;
for (low = high - count[value]; high > low;
a[--high] = (short) value
);
}
} else {
for (int i = MAX_SHORT_INDEX; high > low; ) {
while (count[--i & 0xFFFF] == 0);
int value = i & 0xFFFF;
int c = count[value];
do {
a[--high] = (short) value;
} while (--c > 0);
}
}
}
与其他方法不同，这个方法有很好的文档记录，并且这里的文档与现实相符。
从Java 7开始
这个实现是一个稳定的、自适应的、迭代的归并排序，在输入数组部分排序时需要比n lg(n)更少的比较，同时在输入数组随机排序时提供传统归并排序的性能。如果输入数组几乎排序，该实现需要大约n次比较。
https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])
Java 7之前
排序算法是修改后的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。该算法提供了保证的n*log(n)性能。
https://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(java.lang.Object[])
从 Java 7 开始
临时存储需求因输入数组的排序程度而异，对于几乎有序的输入数组，要求的常量很小，而对于随机排序的输入数组，则需要 n/2 个对象引用。
https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])
在Java 7之前
java.util.Arrays.sort和（间接地）java.util.Collections.sort使用的算法，用于对对象引用进行排序，是一种“修改后的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并操作）”。它是一种相对快速且稳定的排序算法，保证O(n log n) 的性能，并需要额外的O(n) 空间。
既然你在讨论Java语言，时间复杂度肯定会从O(n)增加到O(nlogn)。这是因为在Java 8中，Arrays.sort()采用双轴快速排序算法而不是单轴快速排序算法，所以需要额外的时间。 而O(1)的空间复杂度是不可能的，因为它需要更多的空间，我猜测是O(n/2)。
import java.util.Arrays;
public class MyClass {
static void hello(int ac[]){
}
public static void main(String args[]) {
int ac[] ={1,4,2,3,5};
int i=0;
int temp=0;
while(i!=5-1){
if( ac[i]>ac[i+1]){
temp= ac[i];
ac[i]=ac[i+1];
ac[i+1]=temp;
i= -1;
}
i++;
}
System.out.println(Arrays.toString(ac));
}
}
Arrays.sort()使用了某些魔法，否则我认为关于它具有最低时间复杂度的问题是可以回答的，不是吗？ - O. R. MapperArrays.sort，因此使用任何算法。很难确定这是什么语言（猜测是Java），但标准库排序几乎总是比较排序。 - user2357112Arrays.sort的时间和空间复杂度是什么？”，这实际上是一个没有研究努力的问题，因为这已经有相当充分的文献资料。 - Bernhard Barker