中间元素作为pivot的快速排序最坏时间复杂度及序列构造问题

问题1解答 #

你给出的{4, 5, 6, 7, 3, 2, 1}序列不会触发最坏O(n²)时间复杂度。
我们可以直接算总partition操作量验证：n=7时，最坏情况总操作量是7+6+5+4+3+2+1=28，而这个序列只有前3层partition符合长度递减规律：

• 第一层长度7，选中间元素7（最大值），partition操作7次，剩余左子序列长度6
• 第二层长度6，选中间元素6（最大值），partition操作6次，剩余左子序列长度5
• 第三层长度5，选中间元素3（非最值），partition操作5次，分裂为长度2和2的两个子序列
• 后续两层分别处理两个长度2的子序列，总操作量2+2=4
  总操作量为7+6+5+4=22，远低于最坏情况的28。对于更大的n，如果只有常数层是线性递减分区，后续分区都是平衡分裂，整体时间复杂度依然是O(n log n)量级，达不到O(n²)。

问题2解答 #

构造核心逻辑 #

要触发固定选中间元素为pivot的最坏时间复杂度，核心要求是：每一层待处理序列的中间位置元素，恰好是当前序列的最大值或最小值。这样每次partition操作后，只会生成一个长度为m-1的子序列和一个空序列，完全符合快排最坏情况的递归长度递减规律。

递归构造方法（以中间位置规则为mid = low + (high - low) // 2向下取整为例） #

我们可以用递归方式生成满足要求的排列，步骤如下：

1. 基础情况：长度为1的序列直接取[1]
2. 生成长度为m的序列时：
   • 先生成一个长度为m-1的最坏情况排列S
   • 取当前最大值m，放在长度为m的序列的中间位置（即索引(0 + m-1) // 2处）
   • 将S的元素按顺序填入新序列剩下的所有空位中

构造示例 #

按上述方法生成的不同长度的最坏情况排列如下：

• 长度1：[1]
• 长度2：[2, 1]
• 长度3：[2, 3, 1]
• 长度4：[2, 4, 3, 1]
• 长度5：[2, 4, 5, 3, 1]
• 长度6：[2, 4, 5, 6, 3, 1]
• 长度7：[2, 4, 5, 6, 3, 7, 1]
  你可以自行验证上述序列，每一层选中间pivot都是当前序列的最值，全程递归子序列长度每次减1，总操作量为n(n+1)/2，完全符合O(n²)的最坏时间复杂度要求。

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