如何构造1-10非正序逆序排列以重现快速排序最坏情况（最右元素为基准）

要构造出既非正序也非逆序，同时能触发快速排序（选取最右侧元素为基准）最坏情况的排列，核心是保证每次划分时，基准元素都是当前子数组的最大值或最小值（这样划分后仅剩下一个非空子数组，递归规模每次仅减1，时间复杂度为O(n²)），且交替选择最大值和最小值作为基准（避免出现全程选最大的正序或全程选最小的逆序）。

具体构造步骤（递归交替法） #

我们可以通过递归交替选择基准类型（最大值/最小值）来生成目标数组：

1. 递归终止条件：当需要构造的数值范围仅包含一个数时，直接返回该数组成的单元素数组。
2. 交替选择基准：
   • 如果当前层级选择最小值作为基准：
     • 先递归构造数值范围[low+1, high]的数组（下一层级选择最大值作为基准）。
     • 将最小值low添加到递归数组的末尾，作为当前子数组的基准。
   • 如果当前层级选择最大值作为基准：
     • 先递归构造数值范围[low, high-1]的数组（下一层级选择最小值作为基准）。
     • 将最大值high添加到递归数组的末尾，作为当前子数组的基准。

示例构造结果 #

按照上述方法，以初始选择最小值为基准构造1-10的排列，最终得到：
[6,5,7,4,8,3,9,2,10,1]

验证最坏情况 #

模拟快速排序过程：

• 初始数组基准为1（全局最小值），划分后仅剩下左侧子数组[6,5,7,4,8,3,9,2,10]；
• 该子数组基准为10（当前子数组最大值），划分后仅剩下左侧子数组[6,5,7,4,8,3,9,2]；
• 后续每一步的基准均为当前子数组的最小值或最大值，每次划分仅减少一个元素，完全符合最坏情况的特征。

其他可行构造思路 #

除了递归交替法，还可以通过手动交替放置极值来构造：

• 先放置一个非全局极值的子数组极值作为末尾基准，再在前面构造符合条件的子数组。比如先确定末尾是2（当前子数组最小值），前面构造[3,1,4,6,5,7,9,8,10]，最终数组[3,1,4,6,5,7,9,8,10,2]，同样能触发最坏情况。

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