快速排序算法的最坏情况

Question

快速排序算法的最坏情况

arraysalgorithmsortingtime-complexityquicksort

7

我发现了许多快速排序算法的实现，但最终我决定采用这个：

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)。

任何帮助将不胜感激！

- Nicky

2

姓、名、中间名……除非你对要排序的数据有一些了解，否则它们都是猜测，并可能导致最坏情况。快速排序的最大优点是它是原地排序，但它不稳定。 - maraca

我认为它将采用第一个作为枢轴，将其与所有其他元素进行比较，然后是第二个，依此类推。这将需要n^2的时间复杂度。但这只是最坏情况，平均时间复杂度是O(n logn)。对于基本数据类型而言，是否稳定并不重要。 - maraca

@maraca 这就是我不理解的地方，因为这个快速排序实现只有一个for循环，因此当列表被分成两个子数组时，“i”的值只会递增。因此，它不会将每个值与其他值进行比较。 - Nicky

是的，但如果一个组只包含一个元素，那么你就不会进展得那么快... 1 + 2 + 3 + ... + n - 1 = n * (n - 1) / 2，这等于O(n^2)。 - maraca

顺便问一句，为什么是 end <= start || start >= end？这两个表达式在什么情况下不等价？ - Anton Sherwood

3个回答

3

快速排序首先将所有比枢轴值大的元素移到列表末尾，将所有比枢轴值小的元素移到列表开头。

如果枢轴点的值是列表中最小的值，则列表中的每个值都将移动到列表末尾。然而，确定移动所有这些值的位置需要O(n)的工作。如果您选择第二小的值，然后选择第三小的值等等，则您最终会进行O(n)次n/2次的工作。O(n²/2)简化为O(n²)。

一些人建议以第一个元素作为枢轴点，有些人建议选择中间元素，还有些人会告诉你应该选择最后一个元素作为枢轴点，这不会有所不同吗？

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

如果你的数据是完全随机的，那么无论你选择什么，你都有同样的可能性得到一个好的枢轴点，并且你选择最差的枢轴点的几率非常小。选择第一个或最后一个值是最简单的可行选项。
如果你的数据是预先排序的（或大部分是这样），选择中间的元素可能会得到最佳值之一，而选择第一个或最后一个元素将始终给出最差的枢轴点。

在现实生活中，处理大部分预先排序的数据的可能性足够高，以至于稍微增加代码复杂度可能是值得的。阅读维基百科相关章节可能是值得的。

- StriplingWarrior

哦，那很有道理，所以如果我的数组已经排序，并且我选择将枢轴元素放在中间，它仍然是O(n^2)吗？ - Nicky

1

@Nicky - 使用中间值作为枢轴，对于排序和反向排序的数据都应该是O(n log(n))。 - rcgldr

3

下面是一个使用三数取中法进行快速排序的算法，通过仅在较小部分递归，然后循环回来处理较大部分，将堆栈复杂度限制为O(log(n))。最坏情况时间复杂度仍为O(n^2)，但这需要三数取中法反复选择小或大值。使用中位数的中位数可以将时间复杂度限制为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;
        }
    }
}

- rcgldr

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1952500 · Accepted Answer

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在下面提到的，这不仅适用于排序数组。一般来说，如果您选择的枢轴使数组被划分得非常不均匀，那么您将遇到最坏情况的复杂性。例如，如果数组未排序，但您始终选择枢轴的最大值（或最小值，具体取决于您的实现），则会遇到相同的问题。