用快速排序- O(n^2)观测二次行为

Question

快速排序算法的平均时间复杂度为O(n*log(n))，最坏情况复杂度为O(n^2)。

假设Hoare的快速排序算法的某些变体，什么样的输入会使快速排序算法表现出最坏的情况复杂性？

请说明与具体的快速排序算法(如枢轴选择等)的实现细节有关的任何假设，或者它是否来自一个常用的库，如libc。

有些人读到：

1. 快速杀手的对手
2. 快速排序是最优的
3. 工程排序函数
4. 内省排序和选择算法

Answer 1

当所选择的枢轴的所有值都是所选集合中的最大或最小时，快速排序在O(n^2)处表现最差。以这个例子为例。

1 2 3 4 5

选择的枢轴是1，你将在枢轴的右侧有4个元素，而左侧没有元素。递归地应用相同的逻辑，选择的枢轴分别是2、3、4、5，我们已经达到了这样一种情况，即这种情况在可能最坏的时候执行。

建议并证明，如果输入洗牌良好，则快速排序的性能会很好。

此外，排序的选择通常取决于对输入域的清楚了解。例如，如果输入是巨大的，那么就有一个叫做外部排序的东西，它可以使用外部内存。如果输入的大小很小，我们可以选择合并排序，而不是中型和大型输入集，因为它需要额外的内存。快速排序的主要优点是它的“就地”意味着，输入数据不需要额外的内存。它在纸上的最坏的时间是O(n^2)，但仍然是广泛的首选和使用。我的观点是，排序算法可以根据输入集上的知识来改变，这是一个偏好问题。

Answer 2

扩展Bragboy所说的，而不仅仅是跑步：

quicksort(array);

运行：

shuffle(array);
quicksort(array);

shuffle()的定义可以是：

shuffle(array){
    for(int i = array.length; i > 0; i--){
        r= random number % i;
        swap(array[i], array[r]);
    }
}

这样做可能会处理输入导致quicksort()慢的情况。

Answer 3

Hoare的快速排序算法选择了一个随机支点。为了获得可重复的结果，我建议斯柯恩进行修改，其中包括从输入中选择中间项。对于这个变体，以枢轴为最小的锯齿图案似乎是最坏的输入：

starting with           {  j   i   h   g   f   a   e   d   c   b  }
compare 1 to 6          { (j)  i   h   g   f  (a)  e   d   c   b  }
compare 6 to 10         {  j   i   h   g   f  (a)  e   d   c  (b) }
compare 6 to 9          {  j   i   h   g   f  (a)  e   d  (c)  b  }
compare 6 to 8          {  j   i   h   g   f  (a)  e  (d)  c   b  }
compare 6 to 7          {  j   i   h   g   f  (a) (e)  d   c   b  }
swap 1<=>6              { (a)  i   h   g   f  (j)  e   d   c   b  }
compare 1 to 5          { (a)  i   h   g  (f)  j   e   d   c   b  }
compare 1 to 4          { (a)  i   h  (g)  f   j   e   d   c   b  }
compare 1 to 3          { (a)  i  (h)  g   f   j   e   d   c   b  }
compare 1 to 2          { (a) (i)  h   g   f   j   e   d   c   b  }
compare 2 to 6          {  a  (i)  h   g   f  (j)  e   d   c   b  }
compare 3 to 6          {  a   i  (h)  g   f  (j)  e   d   c   b  }
compare 4 to 6          {  a   i   h  (g)  f  (j)  e   d   c   b  }
compare 5 to 6          {  a   i   h   g  (f) (j)  e   d   c   b  }
compare and swap 6<=>10 {  a   i   h   g   f  (b)  e   d   c  (j) }
compare 7 to 10         {  a   i   h   g   f   b  (e)  d   c  (j) }
compare 8 to 10         {  a   i   h   g   f   b   e  (d)  c  (j) }
compare 9 to 10         {  a   i   h   g   f   b   e   d  (c) (j) }
compare 2 to 6          {  a  (i)  h   g   f  (b)  e   d   c   j  }
compare 6 to 9          {  a   i   h   g   f  (b)  e   d  (c)  j  }
compare 6 to 8          {  a   i   h   g   f  (b)  e  (d)  c   j  }
compare 6 to 7          {  a   i   h   g   f  (b) (e)  d   c   j  }
swap 2<=>6              {  a  (b)  h   g   f  (i)  e   d   c   j  }
compare 2 to 5          {  a  (b)  h   g  (f)  i   e   d   c   j  }
compare 2 to 4          {  a  (b)  h  (g)  f   i   e   d   c   j  }
compare 2 to 3          {  a  (b) (h)  g   f   i   e   d   c   j  }
compare 3 to 6          {  a   b  (h)  g   f  (i)  e   d   c   j  }
compare 4 to 6          {  a   b   h  (g)  f  (i)  e   d   c   j  }
compare 5 to 6          {  a   b   h   g  (f) (i)  e   d   c   j  }
compare and swap 6<=>9  {  a   b   h   g   f  (c)  e   d  (i)  j  }
compare 7 to 9          {  a   b   h   g   f   c  (e)  d  (i)  j  }
compare 8 to 9          {  a   b   h   g   f   c   e  (d) (i)  j  }
compare 3 to 6          {  a   b  (h)  g   f  (c)  e   d   i   j  }
compare 6 to 8          {  a   b   h   g   f  (c)  e  (d)  i   j  }
compare 6 to 7          {  a   b   h   g   f  (c) (e)  d   i   j  }
swap 3<=>6              {  a   b  (c)  g   f  (h)  e   d   i   j  }
compare 3 to 5          {  a   b  (c)  g  (f)  h   e   d   i   j  }
compare 3 to 4          {  a   b  (c) (g)  f   h   e   d   i   j  }
compare 4 to 6          {  a   b   c  (g)  f  (h)  e   d   i   j  }
compare 5 to 6          {  a   b   c   g  (f) (h)  e   d   i   j  }
compare and swap 6<=>8  {  a   b   c   g   f  (d)  e  (h)  i   j  }
compare 7 to 8          {  a   b   c   g   f   d  (e) (h)  i   j  }
compare 4 to 6          {  a   b   c  (g)  f  (d)  e   h   i   j  }
compare 6 to 7          {  a   b   c   g   f  (d) (e)  h   i   j  }
swap 4<=>6              {  a   b   c  (d)  f  (g)  e   h   i   j  }
compare 4 to 5          {  a   b   c  (d) (f)  g   e   h   i   j  }
compare 5 to 6          {  a   b   c   d  (f) (g)  e   h   i   j  }
compare and swap 6<=>7  {  a   b   c   d   f  (e) (g)  h   i   j  }
compare and swap 5<=>6  {  a   b   c   d  (e) (f)  g   h   i   j  }