快速排序最差情况

Question

我正在研究下面需要的程序以更好地理解它。

Quicksort最糟糕的情况下运行时间是什么，什么可能会导致这种更糟的情况下性能？我们如何修改quicksort程序来缓解这个问题？

我知道它有最坏的情况O(n^2)，我知道它发生时，枢轴唯一最小值或最大元素。我的问题是如何修改程序来缓解这个问题。

一个好的算法会很好。

Answer 1

这已经有一段时间了，但我认为快速排序最糟糕的情况是数据已经排序。快速检查数据是否已经排序可以帮助缓解这个问题。

Answer 2

一个简单的修改就是随机选择pivot。这给出了好的结果with high probability。

Answer 3

快速排序的性能取决于您的数据透视选择算法。最朴素的枢轴选择算法是只选择第一个元素作为枢轴。很容易看出，如果您的数据已经排序，则会导致最差情况下的行为（第一个元素始终为最小值）。

有两种常见的算法来解决这个问题：随机选择一个数据透视表，或者选择三位数的中位数。随机是显而易见的，所以我不会详谈。三个中间值包括选择三个元素（通常是第一个，中间和最后一个）并选择这三个元素的中值作为关键点。由于随机数发生器通常是伪随机的（因此是确定性的）并且三种算法的非随机中值是确定性的，所以可以构造导致最坏情况行为的数据，但是它很少出现正常使用。

您还需要考虑性能影响。随机数生成器的运行时间会影响快速排序的运行时间。中位数为三，你正在增加比较的数量。

Answer 4

最坏性能条件：

当选择每次枢轴是 '最大' 或 '最小' 和此模式重复

所以对于1 3 5 4 2

如果枢转按顺序选1,2,3,4,5或5,4,3,2,1

那么最坏的情况下运行时间是O（n * n）

如何避免最坏的情况下：

（1）除以阵列分为五个sets.So如果1..100集合是（1..20）（21..40）（ 41..60）（61..80）（81 ..100）

（2）选择第一五行的中位数在每个设定成（3）（23）（43）（63）（83）

（3）现在选择之中的中值他们作为支点在这里它的（43）

Answer 5

最差的情况下运行时间取决于快速排序内的分区方法。这有两个方面：

• 选择枢轴
• 如何分区围绕枢

良好的战略选择枢轴在以前的帖子已经被outlinied（中位数的中位数，或三个位或随机化）。但即使枢轴是明智的选择，在极端情况下，如果一个数组的所有相等的元素会导致最坏的情况下运行时，如果只有两个分区建成，因为一个将携带相等的元素，这是所有元素：

• 这将导致partion被称为n次，每次它取N/2的平均导致O（N²）
• 这是不好的，因为它不是一个理论上的最坏的情况，但很常见的一个
• 注意，它不是通过检测空分区解决，因为枢轴可能具有最高或最低的元素值（例如中位数为5分，以及最高的元素值，但仍可能几个错放<个5值）

解决此问题的一种方法是分割成三个分区，低级（元件<枢轴），相等（元素=枢轴）和上分区。 “=枢轴元素”处于最终位置。如果不是空的话，下部分区和上部分区仍然需要排序。

与随机总之，中位数或某种组合的中间选择一个支点最坏的情况是相当罕见的，但不是不可能，这让与上限O（N²）的最坏情况下的算法。