Java 14+ Arrays.sort( int[] ) 的最坏情况时间复杂度是多少？
What is the worst case time complexity of Java 14+ Arrays.sort( int[] )?
虽然我知道这似乎很明显，但我会解释我的困惑。我一直认为 Quicksort 的最坏情况时间复杂度为 O(n^2)。 Arrays.sort(int[]) 从 Java 7 到 Java 13 的文档说：
此算法在 许多 数据集上提供 O(n log(n)) 性能，导致其他快速排序降级为二次性能，并且通常比传统的（一- pivot) 快速排序实现。
这里的关键词是“很多”，所以我假设这里的O(n log(n))是指平均情况，并且仍然存在导致最坏情况O(n^2)的数据集.
但是在 Java 14 及更高版本中，Arrays.sort(int[]) 的文档说：
该算法在 所有 数据集.
上提供 O(n log(n)) 性能
那么，这个改进后的快速排序实现的最坏情况现在是 O(n log(n)) 吗？有人请澄清。
您需要检查 Arrays.sort(int[]).
的更深层实现
里面有一个函数DualPivotQuicksort.sort(...)，是用来排序的
您可以在 java 7 到 13 中看到该函数具有故障安全机制，如果复杂度接近 O(n^2)，它会更改排序类型，它会更改为平均复杂度为 O(n) 的快速排序log n) 但最糟糕的是 O(n^2) 这就是为什么在 java 文档描述中说“许多数据集”。
另一方面，由于 java 14 更高复杂度的故障安全正在将排序算法更改为堆排序，其复杂度为 O(n log n)，因此它永远不会比这慢。
虽然我知道这似乎很明显，但我会解释我的困惑。我一直认为 Quicksort 的最坏情况时间复杂度为 O(n^2)。 Arrays.sort(int[]) 从 Java 7 到 Java 13 的文档说： 此算法在 许多 数据集上提供 O(n log(n)) 性能，导致其他快速排序降级为二次性能，并且通常比传统的（一- pivot) 快速排序实现。
这里的关键词是“很多”，所以我假设这里的O(n log(n))是指平均情况，并且仍然存在导致最坏情况O(n^2)的数据集.
但是在 Java 14 及更高版本中，Arrays.sort(int[]) 的文档说： 该算法在 所有 数据集.
上提供 O(n log(n)) 性能那么，这个改进后的快速排序实现的最坏情况现在是 O(n log(n)) 吗？有人请澄清。
您需要检查 Arrays.sort(int[]).
的更深层实现里面有一个函数DualPivotQuicksort.sort(...)，是用来排序的
您可以在 java 7 到 13 中看到该函数具有故障安全机制，如果复杂度接近 O(n^2)，它会更改排序类型，它会更改为平均复杂度为 O(n) 的快速排序log n) 但最糟糕的是 O(n^2) 这就是为什么在 java 文档描述中说“许多数据集”。
另一方面，由于 java 14 更高复杂度的故障安全正在将排序算法更改为堆排序，其复杂度为 O(n log n)，因此它永远不会比这慢。