Mic*_*rry 22
Quicksort通过一个枢轴工作,然后将所有元素放在一侧低于该枢轴而另一侧放置所有较高元素; 然后它以相同的方式递归地对两个子组进行排序(一直向下直到所有内容都被排序.)现在,如果你每次选择最差的数据(列表中的最高或最低元素),你将只有一个组排序,除了您选择的原始枢轴之外,该组中的所有内容.这实际上为您提供了n个组,每个组需要迭代n次,因此O(n ^ 2)复杂度.
发生这种情况的最常见原因是,如果将枢轴选择为快速排序实现中列表中的第一个或最后一个元素.对于未排序的列表,这与任何其他列表一样有效,但是对于已排序或接近排序的列表(实际上很常见),这很可能会给您最坏的情况.这就是为什么所有半正式实现都倾向于从列表中心转移.
对标准快速排序算法进行了修改以避免这种边缘情况 - 一个例子是集成到Java 7中的双枢轴快速排序.
- Java 的 Arrays.sort 方法使用双枢轴快速排序来避免 O(N^2) 边缘情况。 (2认同)
mxm*_*nkn 13
总之,用于排序数组最低元素的Quicksort首先如下工作:
- 选择一个枢轴元素
- 预先排序,使得比枢轴小的所有元素都在左侧
- 递归地执行步骤1.和2.对于左侧和右侧
通常,您会使用一个pivot元素,在两个相同长的子序列中对序列进行分区.
现在有不同的方案来选择枢轴元素.早期版本只采用了最左边的元素.然而,在最坏的情况下,pivot元素将始终是最低元素的wlog.
最左边的元素是枢轴
在这种情况下,可以很容易地想到,最坏的情况是已经增加的排序数组:
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艺术很好地格式化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的数字被给予每个第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的伪随机元素是枢轴
中心元素和三个中值的最坏情况序列看起来已经非常随机,但为了使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).所选择的枢轴元素应该增加.
