Java 14+ Arrays.sort( int[] ) 最坏情况的时间复杂度是多少？

Question

虽然我知道这似乎很明显，但我会解释我的困惑。我一直认为快速排序最坏情况的时间复杂度为 O(n^2)。从 Java 7 到 Java 13 的Arrays.sort(int[])文档表示： 该算法在许多数据集上提供了 O(n log(n)) 性能，这会导致其他快速排序性能降级为二次级，并且通常比传统（单枢轴）快速排序实现。

这里的关键字是“many”，所以我假设这里的 O(n log(n)) 指的是平均情况，并且仍然存在导致 O(n^2) 最坏情况的数据集。

但在 Java 14 及更高版本中， Arrays.sort(int[])的文档表示： This Algorithm Offers O(n log(n)) Performance on all data set。

那么，现在改进的快速排序实现的最坏情况是 O(n log(n)) 吗？有人请澄清一下。

Answer 1

您需要检查 Arrays.sort(int[]) 的更深层实现。

里面有一个函数 DualPivotQuicksort.sort(...) 用于排序。

您可以在 java 7 到 13 中看到该函数有一个故障安全机制，如果复杂度接近 O(n^2)，它会更改排序类型，它会更改为 QuickSort，平均复杂度为 O(n log n) 但最糟糕的是 O( n^2) 这就是为什么在 javaDoc 描述中说“许多数据集”。

另一方面，由于 java 14 针对更高复杂性的故障安全正在将排序算法更改为堆排序，其最差复杂度为 O(n log n)，因此它永远不会比这慢。