虽然我知道这似乎很明显，但我会解释我的困惑.我一直认为Quicksort最糟糕的时间复杂度是O(n^2).从Java 7到Java 13的Arrays.sort(int[])的文档说明:
这里的关键字是"many"，所以我假设这里的O(n log(n))指的是平均情况，并且仍然存在导致O(n^2)最坏情况的数据集.
但在Java 14及以上版本中，Arrays.sort(int[])的文档说明:
那么，这种改进的快速排序实现现在最糟糕的情况是O(n log(n))？请有人澄清一下.
虽然我知道这似乎很明显，但我会解释我的困惑.我一直认为Quicksort最糟糕的时间复杂度是O(n^2).从Java 7到Java 13的Arrays.sort(int[])的文档说明:
这里的关键字是"many"，所以我假设这里的O(n log(n))指的是平均情况，并且仍然存在导致O(n^2)最坏情况的数据集.
但在Java 14及以上版本中，Arrays.sort(int[])的文档说明:
那么，这种改进的快速排序实现现在最糟糕的情况是O(n log(n))？请有人澄清一下.
您需要更深入地判断数组的实现.排序(int[]).
里面有一个快速排序功能.排序(…)用于分类.
你可以在java 7到13中看到，这个函数有一个故障安全机制，当复杂度接近O(n^2)时，它会改变排序类型，它会变为快速排序，平均复杂度为O(n logn)，但最糟糕的是O(n^2)，这就是为什么在javaDoc描述中说"许多数据集".
另一方面，由于java 14对更高复杂度的故障保护正在将排序算法更改为最复杂度为O(n logn)的heapsort，所以它永远不会比这慢.