最糟糕的Quicksort算法案例

Question

我发现了许多快速排序算法的实现,但最后我决定坚持这个:

public static void quickSort(int array[], int start, int end)
        {
            if(end <= start || start >= end) { 

            } else {
            int pivot = array[start];
            int temp = 0 ;
            int i = start+1;

            for(int j = 1; j <= end; j++)  { 
                if(pivot > array[j]) { 
                    temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;
                    i++;
                }

            }
            array[start] = array[i-1];
            array[i-1] = pivot;
            quickSort(array, start, i-2);
            quickSort(array, i, end);
        }} 

有几件我很困惑的事情.
为什么有些人建议把第一个元素作为一个支点,其他人告诉你选择中间元素,有些人会告诉你应该选择最后一个元素作为你的支点,它不会有所不同吗？
假设我试图说明为什么如果数组被排序,快速排序将有O(n ^ 2)作为最坏情况的增长顺序.
我有以下数组:
{1,2,3,4,5,6}.
如果我选择第一个元素作为我的枢轴元素,它是否会将它与其他所有元素进行比较,然后只是将它与自身交换并且只是O(n)？然后它将继续进行两行,即O(logn)

quickSort(array, start, i-2);
quickSort(array, i, end);

所以最后,即使它是一个有序的整数列表,它仍然是O(nlogn)？

如果我决定选择我的最后一个元素作为我的枢轴元素,它会不会完全不同？它将交换6和1,因此与枢轴元素是数组中的第一个元素相比,它将执行完全不同的操作.

我只是不明白为什么最坏的情况是O(n ^ 2).

任何帮助将不胜感激!

Answer 1

Quicksort的重点是找到一个将阵列分成两个大致相等的部分的枢轴.这就是你得到的log(n)地方.

假设有一个大小的数组,n并且在每次迭代时,您可以将数组分成相等的部分.然后我们有:

T(n) = 2 * T(n / 2) + O(n)
     = 4 * T(n/4) + 2 * O(n)
.
.
(log(n) steps)
.
.
    = 2^log(n) * T(1) + log(n) * O(n)
    = n * O(1) + O(n * log(n))
    = O(n * log(n))

现在,如果我们进入大小说分区阵列1和n-1,我们得到:

T(n) = T(1) + T(n-1) + O(n) = T(n-1) + O(n)
     = T(n-2) + O(n-1) + O(n)
     = T(n-3) + O(n-2) + O(n-1) + O(n)
.
.
(n-1) steps
.
.
    = T(1) + O(2) + O(3) + ... + O(n)
    = O(1 + 2 + 3 + .... + n)
    = O(n^2)

在您提到的情况下,以下两个都不是单独的O(log(n)).一个将是O(1),T(n-1)如果数组已排序,另一个将是.因此,你会得到O(n^2)复杂性.

quickSort(array, start, i-2); // should be constant time
quickSort(array, i, end); // should be T(n-1)

正如@MarkRansom在下面提到的,这不是排序数组所独有的.一般来说,如果你选择的方式是阵列分区非常不均匀,那么你将遇到这种最坏情况的复杂性.例如,如果数组没有排序,但您总是选择枢轴的最大值(或最小值,具体取决于您的实现),那么您将遇到同样的问题.