用快速排序算法对K排序阵列排序的时间复杂度

Question

问题：

我必须分析排序的时间复杂性(使用快速排序)，一个整数值的列表，这些值几乎是排序的。

我做了什么？

我读过SO Q1，SO Q2，SO Q3和this one。

但是，我没有发现任何明确提到使用快速排序对k排序数组排序的时间复杂性的内容。

由于快速排序算法的时间复杂度取决于选择枢轴的策略，并且由于数据几乎排序，所以有可能面临最坏的情况，为了避免最坏的情况，我使用了三个值的中值(第一、中、最后三个值)作为参考here。

，我怎么想？

因为在一般情况下，快速排序算法的时间复杂度是O(n log(n))，而且正如前面提到的here，“对于n的任何非平凡值，一个分治算法将需要很多O(n)的传递，即使数组几乎被完全排序”，

如果没有出现最坏的情况，我认为使用快速排序算法对k排序数组排序的时间复杂度是O(n log(n))。

我的问题：

使用快速排序算法对k排序数组排序的时间复杂度是O(n log(n))吗?如果我试图避免最坏的情况，选择一个适当的枢轴，如果最坏的情况没有发生，那么时间复杂度是吗？

Answer 1

当您说快速排序的时间复杂性时，它是O(n^2)，因为最坏的情况是默认假设的。但是，如果您使用另一种策略来选择枢轴，比如随机快速排序，那么默认情况下，您的时间复杂度仍然是O(n^2)。但预期的时间复杂度是O(n log(n))，因为最坏情况的发生是极不可能的。因此，如果你能以某种方式证明最坏的情况是100%被保证不会发生，那么你可以说时间复杂度小于O(n^2)，否则，默认情况下，最坏的情况被考虑，不管多么不可能。