java - 快速排序算法的复杂度

Question

快速排序的标准最坏情况复杂度为 O(n^2)。这种最坏的情况是什么？在这种情况下如何进行修改以提出更好的行为？这只是一个理论问题。

Answer 1

最坏的情况是，每当您选择一个枢轴时，它始终是您正在排序的段中的最大或最小元素。为了改善最坏的情况，您需要有一种选择支点的好方法。

Answer 2

最坏的情况是数据已经排序。

一种补偿方法是随机选择第一个枢轴。

Answer 3

最坏的情况取决于您使用的分区方法。在最简单的情况下，最坏的情况是数据已经排序。这就是你不使用它的原因。