查找快速排序O(N^2)的最坏情况



我目前正在尝试为数组找到一个排序:{1,2,3,4,5,6,7},这样当我们选择中间元素作为我们的枢轴时,它会产生二次时间复杂度。我将如何对这个数组进行排序,使它变成O(N^2(?枢轴必须是中间元素。

假设Lomuto分区方案,其中pivot不包括在下一级递归中,并且左中用于偶数个元素:

array                pivot
6 4 2 1 3 5 7        1
6 4 2 3 5 7          2
6 4 3 5 7            3
6 4 5 7              4
6 5 7                5
6 7                  6
7

最新更新