以数组末尾元素4为基准的快速排序时间复杂度分析

你之前以为这是最优情况其实刚好相反——这种场景属于快速排序的最坏情况，时间复杂度是O(n²)，而非O(nlogn)。咱们一步步拆解原因：

1. 分区操作的结果
   基准元素是数组里的最小值4，遍历数组时会发现所有其他元素都比4大。分区结束后，4会被放到数组的最左端，左边没有任何元素，右边则是剩下的5个元素[6, 8, 7, 5, 9]。

2. 递归过程的连锁反应
   接下来递归处理右边的子数组时，同样会选末尾元素9作为基准——而9是这个子数组的最大值。分区后右边没有元素，左边是4个元素[6, 8, 7, 5]。以此类推，每次分区都只能把数组拆成「一个空数组 + 长度减1的子数组」，递归树完全不平衡，变成了一条单链。

3. 时间复杂度计算
   这种情况下，每次递归都要遍历当前长度的数组，总操作次数是：n + (n-1) + (n-2) + ... + 1 = n(n+1)/2，对应的时间复杂度就是O(n²)。

而快速排序的最优情况（O(nlogn)），是每次分区都能把数组分成两个长度大致相等的子数组，这时候基准元素需要是数组的中位数（或接近中位数的元素），递归树是平衡的二叉树，每层遍历的总次数是n，树的高度是logn，总复杂度就是n*logn。

内容的提问来源于stack exchange，提问作者Dominic