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

Question

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

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

但在 Java 14 及更高版本中，Arrays.sort(int[]) 的文档说:此算法在所有 数据集 上提供 O(n log(n)) 性能。

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

Answer 1

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

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

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

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