我已经了解了递归快速排序，在最佳情况下需要O（nlogn），在最坏情况下需要O（n ^ 2）。但是我试图找到迭代快速排序的时间复杂度。我知道最好的情况是O（nlogn）和O（n ^ 2）。但我并不能为最好的情况辩护。我正在关注本教程
https://www.techiedelight.com/iterative-implementation-of-quicksort/
例如，我们有15个元素，因此枢轴索引位置始终位于中间，这使其成为理想的最佳情况。但是我发现它的条件是“ while（！stack.empty（））”，即分区的数目将发生6次，这与log（n）不太接近。如何证明迭代快速排序中最佳情况的时间复杂度是O（nlogn）。
我已经了解了递归快速排序，在最佳情况下需要O（nlogn），在最坏情况下需要O（n ^ 2）。但是我试图找到迭代快速排序的时间复杂度。我知道最好是O（nlogn）...
在第一遍分区中，您分为两个分区。这需要O（n）。在下一遍中，您将拥有两个分区，每个分区的大小为n / 2。需要O（n / 2）对每个分区进行分区。第二遍的总时间为O（n / 2 + n / 2）：O（n）。每遍都具有更多分区，但是分区较小。总的来说，您使log（n）通过，每个都需要O（n）总计时间。