快速排序算法何时需要 O(n^2) 时间？
问问题
26062 次
6 回答
30
快速排序的工作原理是取一个轴，然后将所有低于该轴的元素放在一侧，将所有较高的元素放在另一侧；然后它以相同的方式对两个子组进行递归排序（一直到所有内容都排序为止。）现在，如果您每次都选择最差的枢轴（列表中的最高或最低元素），您将只有一个组排序，除了您选择的原始枢轴之外，该组中的所有内容。这实质上为您提供了 n 个组，每个组都需要迭代 n 次，因此复杂度为 O(n^2)。
发生这种情况的最常见原因是，如果在快速排序实现中选择枢轴作为列表中的第一个或最后一个元素。对于未排序的列表，这与任何其他列表一样有效，但是对于已排序或接近排序的列表（在实践中很常见），这很可能会给您带来最坏的情况。这就是为什么所有半体面的实现都倾向于从列表的中心开始。
对标准快速排序算法进行了修改以避免这种极端情况——一个例子是集成到 Java 7 中的双轴快速排序。
于 2011-01-29T02:38:44.857 回答
20
简而言之，对数组最低元素进行排序的快速排序首先是这样工作的：
- 选择一个枢轴元素
- 预排序数组，使得所有小于枢轴的元素都在左侧
- 对左侧和右侧递归执行步骤 1. 和 2.
理想情况下，您需要一个将序列划分为两个同样长的子序列的枢轴元素，但这并不容易。
选择枢轴元素有不同的方案。早期版本只取了最左边的元素。在最坏的情况下，枢轴元素将始终是当前范围的最低元素。
最左边的元素是枢轴
在这种情况下，可以很容易地认为最坏的情况是一个单调递增的数组：
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算法将当前选中的pivot元素对应的数组元素设置为单调递增的值来构造。即我们知道第一个枢轴是中心，所以中心必须是最低值，例如0。接下来它被交换到最左边，即最左边的值现在在中心并且将是下一个枢轴元素，所以它必须是 1。现在，我们已经可以猜到数组看起来像这样：
1 ? ? 0 ? ? ?
这是修改后的快速排序生成最差序列的 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 艺术很好地格式化 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 个元素执行相同的操作，在第 3 行中，将数字分配给每 8 个元素，依此类推。在这种情况下，要写入第 i 行的第一个值位于索引 2^i-1 处，但对于某些长度，这看起来有点不同。
由此产生的结构让人想起倒置二叉树，其节点从叶子开始自下而上标记。
最左边、中间和最右边元素的中位数是枢轴
另一种方法是使用最左边、中心和最右边元素的中值。在这种情况下，最坏的情况只能是 wlog 左子序列的长度为 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 的伪随机元素是枢轴
中心元素和三中位数的最坏情况序列看起来已经非常随机，但为了使快速排序更加稳健，可以随机选择枢轴元素。如果使用的随机序列至少在每次快速排序运行时都可以重现，那么我们也可以为此构造一个最坏情况的序列。我们只需要调整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)) 缩放，那么这些确实是最坏情况的序列。
- 调整正确的快速排序以提供有关子序列长度和/或所选枢轴元素的调试输出。其中一个子序列的长度应始终为 1（或 2 为三的中位数）。打印的选择的枢轴元素应该增加。
于 2017-01-20T15:54:43.830 回答
10
获得等于最低或最高数字的枢轴，也应该触发 O(n 2 )的最坏情况。
于 2011-01-29T02:29:15.463 回答
4
快速排序的不同实现需要不同的数据集来为其提供最坏情况的运行时间。这取决于算法在哪里选择它的枢轴元素。
正如 Ghpst 所说，选择最大或最小的数字会给你带来最坏的情况。
如果我没记错的话，快速排序通常使用随机元素作为枢轴，以尽量减少出现最坏情况的机会。
于 2011-01-29T02:29:28.330 回答
1
我认为如果数组是逆序的，那么对于该数组的最后一个元素进行旋转将是最坏的情况
于 2011-10-06T19:33:25.920 回答
0
导致快速排序最坏情况的因素如下：
- 最坏的情况发生在子阵列完全不平衡时
- 最坏的情况发生在一个子数组中有 0 个元素而另一个子数组中有
n-1元素时。
换句话说，快速排序的最坏情况运行时间发生在快速排序接受排序数组（按降序排列）时，时间复杂度为 O(n^2)。
于 2016-09-25T02:45:50.827 回答