以中间元素为基准的Quicksort最坏情况场景及困惑咨询

核心结论先明确 #

以中间元素为基准的快排，有序数组并不是最坏情况——这是它和以首/尾元素为基准的快排的关键区别。

为什么有序数组不是最坏情况？ #

当快排选择首/尾元素为基准时，有序数组会导致每次划分只能得到一个长度为n-1的子数组和一个空数组，递归树退化为线性结构，总操作次数为n + (n-1) + ... + 1 = O(n²)。

但如果选择中间元素为基准：

• 对于升序/降序数组，中间元素会将数组划分为两个长度接近n/2的子数组
• 递归树是平衡的，每层总操作次数为O(n)，递归深度为O(log n)，总时间复杂度为O(n log n)——这和你手动计算的结果一致。

真正的最坏情况：极端不平衡划分的数组 #

以中间元素为基准的快排，最坏情况出现在每次选择的中间元素都是当前数组的最大值或最小值，导致划分后一个子数组为空，另一个子数组长度为n-1，递归树退化为线性结构，时间复杂度变为O(n²)。

这种数组是人为构造的，比如：

• 长度为3的示例：[2, 0, 1]
  • 第一次取中间元素0（当前数组最小值），划分后左边为空，右边为[2,1]
  • 第二次对[2,1]取中间元素1（当前子数组最小值），划分后左边为[2]，右边为空
  • 总操作次数为3 + 2 + 1 = 6，符合O(n²)
• 更长的数组可以通过递归构造：每次将当前的最小（或最大）元素放在中间位置，其余元素按同样规则构造左右子数组，比如长度为7的数组：[5, 3, 6, 1, 4, 0, 2]

额外说明 #

这种最坏情况数组在实际场景中几乎不会自然出现，因此以中间元素为基准的快排通常能保持稳定的O(n log n)性能，避免了首/尾基准版本在有序数组上的糟糕表现。

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