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 在下面提到的，这并不是排序数组独有的。通常，如果您以数组分区非常不均匀的方式选择枢轴，您将运行陷入这种最坏情况的复杂性。例如，如果数组未排序，但您始终选择 maximum（或 minimum，具体取决于您的实现），您将运行陷入同样的问题。

Answer 2

QuickSort 首先将所有比主元值高的值移动到列表的末尾，以及所有得到的值较低的值到列表的开头。

如果您的轴心点处的值是列表中的最低值，则列表中的每个值都将移至列表末尾。但是，仅仅确定将所有这些值移动到哪里就需要 O(n) 工作。如果您随后选择第二低的值，然后选择第三低的值，依此类推，那么您最终将完成 O(n) 工作 n/2 次。 O(n²/2) 简化为 O(n²).

Why some people suggest taking the first element as a pivot point, others tell to pick the middle element and some will tell that you should pick the last element as your pivot point, wouldn't it be different?

这完全是尝试猜测（无需扫描整个列表）哪个元素最有可能接近数据集的中位数，从而为您提供尽可能接近最佳情况的行为。

如果您的数据是完全随机的，那么您选择什么都没有关系——您同样有可能获得一个好的轴心点，并且始终如一的机会选择最差枢轴点非常渺茫。选择第一个或最后一个值是最简单的选项。
如果您的数据已预排序（或大部分情况下已预排序），选择中间值可能会为您提供最佳值之一，而选择第一个或最后一个元素将始终为您提供最差的枢轴点。

在现实生活中，处理大部分预排序数据的可能性非常高，因此代码稍微复杂一些可能是值得的。 The Wikipedia section 关于这个主题可能值得一读。

Answer 3

下面是一个使用中位数 3 的快速排序，通过仅对较小的部分使用递归，然后对较大的部分进行循环，将堆栈复杂度限制为 O(log(n))。最坏情况下的时间复杂度仍然是 O(n^2)，但这需要中位数为 3 才能重复选择较小或较大的值。通过使用中位数的中位数可以将时间复杂度限制为 O(n log(n))，但是这样做的开销会使平均情况慢得多（我想知道它最终是否比堆排序慢。使用中位数的中位数，它肯定比归并排序慢，但标准归并排序需要第二个大小相同或原始数组大小 1/2 的数组。

http://en.wikipedia.org/wiki/Median_of_medians

Introsort 通过切换到基于递归级别的堆排序来解决最坏情况下的时间复杂度。

http://en.wikipedia.org/wiki/Introsort

typedef unsigned int uint32_t;

void QuickSort(uint32_t a[], size_t lo, size_t hi) {
    while(lo < hi){
        size_t i = lo, j = (lo+hi)/2, k = hi;
        uint32_t p;
        if (a[k] < a[i])            // median of 3
            std::swap(a[k], a[i]);
        if (a[j] < a[i])
            std::swap(a[j], a[i]);
        if (a[k] < a[j])
            std::swap(a[k], a[j]);
        p = a[j];
        i--;                        // Hoare partition
        k++;
        while (1) {
            while (a[++i] < p);
            while (a[--k] > p);
            if (i >= k)
                break;
            std::swap(a[i], a[k]);
        }
        i = k++;
        // recurse on smaller part, loop on larger part
        if((i - lo) <= (hi - k)){
            QuickSort(a, lo, i);
            lo = k;
        } else {
            QuickSort(a, k, hi);
            hi = i;
        }
    }
}

Quicksort 算法的最坏情况

Worst case of the Quicksort algorithm

arrays

sorting

algorithm

quicksort

time-complexity