快速排序的最坏情况是什么？

问题描述 投票：14回答：6

快速排序算法何时需要O（n ^ 2）时间？

algorithm quicksort
6个回答
25
投票

Quicksort的工作原理是，先取得一个枢轴，然后将所有比该枢轴低的元素放在一侧，将所有较高的元素放在另一侧；然后，它以相同的方式递归地对两个子组进行排序（一直向下直到所有内容都被排序。）现在，如果您每次都选择最差的数据透视表（列表中的最高或最低元素），则只有一组排序，以及该组中除您选择的原始数据透视表之外的所有内容。从本质上讲，这给您n个组，每个组需要迭代n次，因此O（n ^ 2）的复杂性。

发生这种情况的最常见原因是，是否将数据透视表选择为快速排序实现中列表中的第一个或最后一个元素。对于未排序的列表，这和其他列表一样有效，但是对于已排序或几乎已排序的列表（在实践中很常见），很可能会给您带来最坏的情况。这就是为什么所有半体面的实现都倾向于从列表的中心出发。

对标准快速排序算法进行了修改，以避免出现这种极端情况-dual-pivot quicksort that was integrated into Java 7是一个示例。

13
投票

总之，Quicksort首先用于对数组最低元素进行排序，如下所示：

  1. 选择枢轴元素
  2. 预排序数组，所有小于枢轴的元素都在左侧
  3. 递归地执行步骤1.和2.对于左侧和右侧

理想情况下，您需要一个透视图元素将序列分为两个相等长的子序列，但这并不容易。

选择枢轴元素有不同的方案。 Early versions只是最左边的元素。在最坏的情况下，枢轴元素将始终是当前范围的最低元素。

最左边的元素是枢轴

在这种情况下，很容易想到最坏的情况是单调递增数组：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

最右边的元素是枢轴

类似地，当选择最右边的元素时，最坏的情况是序列递减。

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

中心元素是枢轴

对于最坏情况的预排序数组，一种可能的补救方法是使用中心元素（如果序列的长度为偶数，则使用中心元素稍微偏左）。然后，最坏的情况将变得更加奇特。可以通过修改Quicksort算法以将与当前选定的枢轴元素相对应的数组元素设置为单调递增值来构造它。即我们知道第一个枢轴是中心，因此中心必须是最低值，例如0。接下来它被交换到最左边，即最左边的值现在在中心，并且将是下一个枢轴元素，因此它必须是1。现在，我们已经可以猜测数组看起来像这样：

1 ? ? 0 ? ? ?

这是修改后的Quicksort的C ++代码，以生成最差的序列：

// g++ -std=c++11 worstCaseQuicksort.cpp && ./a.out

#include <algorithm>    // swap
#include <iostream>
#include <vector>
#include <numeric>      // iota

int main( void )
{
    std::vector<int> v(20); /**< will hold the worst case later */

    /* p basically saves the indices of what was the initial position of the
     * elements of v. As they get swapped around by Quicksort p becomes a
     * permutation */
    auto p = v;
    std::iota( p.begin(), p.end(), 0 );

    /* in the worst case we need to work on v.size( sequences, because
     * the initial sequence is always split after the first element */
    for ( auto i = 0u; i < v.size(); ++i )
    {
        /* i can be interpreted as:
         *   - subsequence starting index
         *   - current minimum value, if we start at 0 */
        /* note thate in the last step iPivot == v.size()-1 */
        auto const iPivot = ( v.size()-1 + i )/2;
        v[ p[ iPivot ] ] = i;
        std::swap( p[ iPivot ], p[i] );
    }

    for ( auto x : v ) std::cout << " " << x;
}

结果：

                                    0
                                    0  1
                                 1  0  2
                                 2  0  1  3
                              1  3  0  2  4
                              4  2  0  1  3  5
                           1  5  3  0  2  4  6
                           4  2  6  0  1  3  5  7
                        1  5  3  7  0  2  4  6  8
                        8  2  6  4  0  1  3  5  7  9
                     1  9  3  7  5  0  2  4  6  8 10
                     6  2 10  4  8  0  1  3  5  7  9 11
                  1  7  3 11  5  9  0  2  4  6  8 10 12
                 10  2  8  4 12  6  0  1  3  5  7  9 11 13
               1 11  3  9  5 13  7  0  2  4  6  8 10 12 14
               8  2 12  4 10  6 14  0  1  3  5  7  9 11 13 15
            1  9  3 13  5 11  7 15  0  2  4  6  8 10 12 14 16
           16  2 10  4 14  6 12  8  0  1  3  5  7  9 11 13 15 17
         1 17  3 11  5 15  7 13  9  0  2  4  6  8 10 12 14 16 18
        10  2 18  4 12  6 16  8 14  0  1  3  5  7  9 11 13 15 17 19
      1 11  3 19  5 13  7 17  9 15  0  2  4  6  8 10 12 14 16 18 20
     16  2 12  4 20  6 14  8 18 10  0  1  3  5  7  9 11 13 15 17 19 21
   1 17  3 13  5 21  7 15  9 19 11  0  2  4  6  8 10 12 14 16 18 20 22
  12  2 18  4 14  6 22  8 16 10 20  0  1  3  5  7  9 11 13 15 17 19 21 23
1 13  3 19  5 15  7 23  9 17 11 21  0  2  4  6  8 10 12 14 16 18 20 22 24

这里有顺序。右侧只是从零开始的两个增量。左侧也有命令。让我们使用Ascii art很好地格式化长73个元素的最坏情况序列的左侧：

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
------------------------------------------------------------------------------------------------------------
  1     3     5     7     9    11    13    15    17    19    21    23    25    27    29    31    33    35   
    37          39          41          43          45          47          49          51          53      
          55                      57                      59                      61                      63
                                              65                                              67            
                                                                      69                                    
                      71

标头是元素索引。在第一行中，每个第二个元素均从1开始以2递增。在第二行中，对每个第4个元素执行相同的操作，在第三行中，将数字分配给每个第8个元素，依此类推。在这种情况下，要在第i行中写入的第一个值位于索引2 ^ i-1，但是对于某些长度，这看起来有点不同。

生成的结构让人想起一棵倒置的二叉树，其节点从叶子开始被标记为自下而上。

最左边，中间和最右边元素的中位数是枢轴

另一种方法是使用最左边，中间和最右边元素的中位数。在这种情况下，最坏的情况只能是w.l.o.g。左子序列的长度为2（不仅仅是上面示例中的长度1）。我们还假设最右边的值将始终是三位数中位数的最大值。这也意味着它是所有值中的最高值。在上面的程序中进行调整，现在我们有了：

auto p = v;
std::iota( p.begin(), p.end(), 0 );
auto i = 0u;
for ( ; i < v.size(); i+=2 )
{
    auto const iPivot0 = i;
    auto const iPivot1 = ( i + v.size()-1 )/2;
    v[ p[ iPivot1 ] ] = i+1;
    v[ p[ iPivot0 ] ] = i;
    std::swap( p[ iPivot1 ], p[i+1] );
}
if ( v.size() > 0 && i == v.size() )
    v[ v.size()-1 ] = i-1;

生成的序列是：

                                     0
                                     0  1
                                  0  1  2
                                  0  1  2  3
                               0  2  1  3  4
                               0  2  1  3  4  5
                            0  4  2  1  3  5  6
                            0  4  2  1  3  5  6  7
                         0  4  2  6  1  3  5  7  8
                         0  4  2  6  1  3  5  7  8  9
                      0  8  2  6  4  1  3  5  7  9 10
                      0  8  2  6  4  1  3  5  7  9 10 11
                   0  6  2 10  4  8  1  3  5  7  9 11 12
                   0  6  2 10  4  8  1  3  5  7  9 11 12 13
                0 10  2  8  4 12  6  1  3  5  7  9 11 13 14
                0 10  2  8  4 12  6  1  3  5  7  9 11 13 14 15
             0  8  2 12  4 10  6 14  1  3  5  7  9 11 13 15 16
             0  8  2 12  4 10  6 14  1  3  5  7  9 11 13 15 16 17
          0 16  2 10  4 14  6 12  8  1  3  5  7  9 11 13 15 17 18
          0 16  2 10  4 14  6 12  8  1  3  5  7  9 11 13 15 17 18 19
       0 10  2 18  4 12  6 16  8 14  1  3  5  7  9 11 13 15 17 19 20
       0 10  2 18  4 12  6 16  8 14  1  3  5  7  9 11 13 15 17 19 20 21
    0 16  2 12  4 20  6 14  8 18 10  1  3  5  7  9 11 13 15 17 19 21 22
    0 16  2 12  4 20  6 14  8 18 10  1  3  5  7  9 11 13 15 17 19 21 22 23
 0 12  2 18  4 14  6 22  8 16 10 20  1  3  5  7  9 11 13 15 17 19 21 23 24

随机种子为0的伪随机元素是枢轴

中心元素和三位数中位数的最坏情况序列看起来已经很随机了，但是为了使Quicksort更加健壮，可以随机选择枢轴元素。如果使用的随机序列至少在每次Quicksort运行中都可重现，那么我们也可以为此构建最坏情况的序列。我们只需要在第一个程序中调整iPivot =行，例如至：

srand(0); // you shouldn't use 0 as a seed
for ( auto i = 0u; i < v.size(); ++i )
{
    auto const iPivot = i + rand() % ( v.size() - i );
    [...]

生成的序列是：

                                     0
                                     1  0
                                  1  0  2
                                  2  3  1  0
                               1  4  2  0  3
                               5  0  1  2  3  4
                            6  0  5  4  2  1  3
                            7  2  4  3  6  1  5  0
                         4  0  3  6  2  8  7  1  5
                         2  3  6  0  8  5  9  7  1  4
                      3  6  2  5  7  4  0  1  8 10  9
                      8 11  7  6 10  4  9  0  5  2  3  1
                   0 12  3 10  6  8 11  7  2  4  9  1  5
                   9  0  8 10 11  3 12  4  6  7  1  2  5 13
                2  4 14  5  9  1 12  6 13  8  3  7 10  0 11
                3 15  1 13  5  8  9  0 10  4  7  2  6 11 12 14
            11 16  8  9 10  4  6  1  3  7  0 12  5 14  2 15 13
             6  0 15  7 11  4  5 14 13 17  9  2 10  3 12 16  1  8
          8 14  0 12 18 13  3  7  5 17  9  2  4 15 11 10 16  1  6
          3  6 16  0 11  4 15  9 13 19  7  2 10 17 12  5  1  8 18 14
       6  0 14  9 15  2  8  1 11  7  3 19 18 16 20 17 13 12 10  4  5
      14 16  7  9  8  1  3 21  5  4 12 17 10 19 18 15  6  0 11  2 13 20
    1  2 22 11 16  9 10 14 12  6 17  0  5 20  4 21 19  8  3  7 18 15 13
   22  1 15 18  8 19 13  0 14 23  9 12 10  5 11 21  6  4 17  2 16  7  3 20
 2 19 17  6 10 13 11  8  0 16 12 22  4 18 15 20  3 24 21  7  5 14  9  1 23

那么如何检查那些序列是否正确？

  • 测量序列花费的时间。在序列长度N上绘制时间。如果曲线以O（N ^ 2）而不是O（N log（N））缩放，则这些确实是最坏情况的序列。
  • 调整正确的Quicksort，以给出有关子序列长度和/或选定的枢轴元素的调试输出。子序列之一的长度应始终为1（三位数的中位数为2）。所选的枢轴元素应该增加。

benchmarking quicksort median-of-three with random and worst case

10
投票

获得等于最低或最高数字的枢轴，也应该触发O（n 2）的最坏情况。

4
投票

快速排序的不同实现需要不同的数据集，以使其在最坏的情况下运行。这取决于算法在哪里选择它的枢轴元素。

而且正如Ghpst所说，选择最大或最小的数字会给您带来最坏的情况。

如果我没记错的话，quicksort通常使用随机元素作为枢轴，以最大程度地降低发生最坏情况的机会。

1
投票

我认为，如果数组按可重排顺序排列，则旋转该数组的最后一个元素将是最坏的情况

0
投票

导致快速排序最坏情况的因素如下：

  • 当子数组完全不平衡时，出现最坏的情况
  • [最坏的情况是一个子数组中有0个元素，而另一个子数组中有n-1个元素。

换句话说，当Quicksort接受排序数组（以降序排列）时，其时间复杂度为O（n ^ 2）。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.