如何构造数组使选中间元素为枢轴的快速排序达到O(N²)复杂度

要让选择中间元素作为枢轴的快速排序达到O(N²)时间复杂度，核心是确保每次选取的中间元素都是当前子数组的最大值或最小值。这样每次划分后，子数组只会减少一个元素（枢轴本身），递归深度为N，每次划分耗时O(N)，总时间复杂度即为O(N²)。

针对原数组{1,2,3,4,5,6,7}，可以构造如下数组：
[4, 5, 6, 7, 3, 2, 1]

验证过程： #

1. 初始数组：长度7，中间元素为索引3的7（整个数组的最大值）。划分后，所有元素都在左子数组[4,5,6,3,2,1]，右子数组为空，本次划分耗时O(7)。
2. 左子数组[4,5,6,3,2,1]：长度6，取中间索引(0+5)//2=2的元素6（当前子数组的最大值）。划分后，所有元素都在左子数组[4,5,3,2,1]，右子数组为空，耗时O(6)。
3. 左子数组[4,5,3,2,1]：长度5，中间索引2的元素3（当前子数组的最小值）。划分后，所有元素都在右子数组[4,5,2,1]，左子数组为空，耗时O(5)。
4. 右子数组[4,5,2,1]：长度4，中间索引(0+3)//2=1的元素5（当前子数组的最大值）。划分后，所有元素都在左子数组[4,2,1]，右子数组为空，耗时O(4)。
5. 左子数组[4,2,1]：长度3，中间索引1的元素2（当前子数组的最小值）。划分后，所有元素都在右子数组[4,1]，左子数组为空，耗时O(3)。
6. 右子数组[4,1]：长度2，中间索引(0+1)//2=0的元素4（当前子数组的最大值）。划分后，所有元素都在右子数组[1]，左子数组为空，耗时O(2)。
7. 处理[1]：长度1，无需划分。

整个递归过程中，每次划分都仅将子数组长度减少1，总时间复杂度为O(N²)，完全符合要求。

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