问快速排序树最大和最小高度

EN

快速排序最坏的情况发生在输入数组是已排序的(不递减或不增加的顺序)，并且我们总是选择第一个或最后一个元素作为枢轴(分区不是随机的)。

例如，输入数组：

[1,2,3,4,5]

假设我们选择最左边的元素作为枢轴。因此，递归树的建立类似于：

   n
  /  \
 1    n-1(2,3,4,5)

同样，2将作为枢轴，使树：

   n
  /  \
 1    n-1(2,3,4,5)
     /   \
    1    n-2(3,4,5)

观察模式，树的高度将是O(N)，在每个层次上分区算法都会取O(N)时间，从而导致总时间= O(N^2)

递归树的最佳高度是O(logN)，这是当中间元素总是被选择为支点时发生的。