我目前正在尝试为数组找到一个排序:{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