有没有人知道java的arrays.sort方法在大O符号表示法下的运行时间？我需要这个信息来完成我的科学展览项目。
4个回答
14
来自官方 文档
我观察到主要有两种方法。所以，这取决于你正在排序的内容以及从sort方法族中调用的哪个重载方法。
文档提到对于原始类型，例如long、byte（例如：static void sort(long[])）：
排序算法是经过调整的快速排序，改编自Jon L. Bentley和M. Douglas McIlroy的“Engineering a Sort Function”，Software-Practice and Experience，Vol。23(11)P.1249-1265（1993年11月）。这个算法在许多数据集上提供了O(n*log(n))性能，这些数据集会导致其他快速排序退化为二次性能。
对于对象类型：（例如：void sort(Object list[])）
保证O(nlogn)性能
排序算法是修改后的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。这个算法保证了n*log(n)性能。
希望这可以帮助！
- pinkpanther
2
3
Arrays.sort()使用Tim sort算法 - 对于对象数组是O(N log N)，对于基本类型数组使用QuickSort - 同样是O(N log N)。
这里有一个很棒的排序算法比较网站：http://www.sorting-algorithms.com/
- Svetlin Zarev
0
我已经在各种数据集中测试了Arrays.sort()的时间复杂度。在最坏情况下，它的时间复杂度是O(n^2)。 尝试使用Arrays.sort()和Collections.sort()来解决这个问题。你会看到差异。问题链接 当我使用Arrays.sort()时，它花费了超过2秒的时间。 而当我使用Collections.sort()时，只需要0.2秒。 Collections.sort()使用修改后的归并排序算法，而Arrays.sort()使用快速排序算法。如果你正在使用数组，则以下代码是在Java中进行排序的最佳方式。对于列表，你可以默认使用Collections.sort()。
static void sort(long[] a) {
ArrayList<Long> l=new ArrayList<>();
for (long i:a) l.add(i);
Collections.sort(l);
for (int i=0; i<a.length; i++) a[i]=l.get(i);
}
- Tarun Kumar Gola
0
这取决于您要排序的内容以及您使用的Java版本。不同类型数组的排序方法具有不同的时间和空间复杂度。在后来的Java版本中也有改进。
Arrays.sort(int[])
除了Arrays.sort(long[])、Arrays.sort(float[])和Arrays.sort(double[])之外
时间复杂度
Arrays.sort(int[])的时间复杂度取决于Java的版本。
Java 14之前
使用普通的快速排序，时间复杂度范围从O(n)（当数组已经排序并且我们只是检查它时）到O(n2)，对于某些导致元素极不均匀分布到具有平均复杂度O(n log(n))的部分的输入。您可以在这里找到详细的分析。
从Java 14到Java 19
在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(int[])方法，但我还是决定包括其他数据类型的答案，因为这是在谷歌搜索Arrays.sort()时间和空间复杂度时的第一个结果，并且在其他地方很难找到正确的答案。
Arrays.sort(short[])
除了Arrays.sort(char[])和Arrays.sort(byte[])之外
时间复杂度和空间复杂度
尽管文档中说：
排序算法是由Vladimir Yaroslavskiy、Jon Bentley和Joshua Bloch发明的Dual-Pivot Quicksort。这种算法在所有数据集上都提供O(n log(n))的性能，并且通常比传统（单轴）Quicksort实现更快。
但至少从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);
}
}
}
Arrays.sort(Object[])
与其他方法不同，这个方法有很好的文档记录，并且这里的文档内容与实际情况相符。
时间复杂度
O(n log(n))
从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[])
空间复杂度
O(n)
从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)额外空间。
- Denis Stafichuk
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
Tim sort。 - Svetlin Zarev