快速排序的最坏情况

Question

我正在开发一个程序，需要更好地理解以下内容。

Quicksort的最坏运行时间是多少，可能会导致这种最坏情况的性能？我们如何修改quicksort程序以缓解这个问题？

我知道它的最坏情况是O(n^2)，并且我知道当主元是唯一的最小或最大元素时会发生。我的问题是如何修改程序以缓解这个问题。

一个好的算法将是很好的选择。

- John

---

此外，您应该注意重复元素。例如，如果正在排序的数组中所有元素都相等，则根据快速排序算法可能会导致最坏情况的行为。 - Justin Peel

这是作业吗？如果是的话，没问题，但你可能想将其标记为作业。 - Steve

Answer 1

快速排序的性能取决于你使用的枢轴选择算法。最简单的枢轴选择算法是选择第一个元素作为枢轴。很容易看出，如果数据已经排序，这将导致最坏情况的行为（第一个元素始终是最小值）。

有两种常见的算法来解决这个问题：随机选择枢轴或选择中位数。随机算法很明显，我就不详细介绍了。中位数算法涉及选择三个元素（通常是第一个、中间和最后一个），并选择其中位数作为枢轴。

由于随机数生成器通常是伪随机的（因此是确定性的），而非随机的中位数算法也是确定性的，因此可能会构造出导致最坏情况行为的数据，但在正常使用中很少发生。

你还需要考虑性能影响。你的随机数生成器运行时间会影响快速排序的运行时间。使用中位数算法会增加比较次数。

- Niki Yoshiuchi

Answer 2

最差性能条件：

当每次选择的中心点是“最大值”或“最小值”，并且这个模式重复时。

例如对于1 3 5 4 2，如果选择的中心点按顺序为1、2、3、4、5或5、4、3、2、1，则最坏情况下的运行时间为O(n*n)。

如何避免最坏情况：

(1)将数组分成五组。例如在1..100中，这五组为(1..20) (21..40) (41..60) (61..80) (81..100)

(2)在每组的前五个元素中选择中位数，因此选择的数为(3) (23) (43) (63) (83)

(3)现在从它们中选择中位数作为中心点，所以这里的中心点是(43)

- theReverseFlick

Answer 3

一种简单的修改方法是随机选择枢轴。这通常可以 高概率地 得到良好结果。

- Gabe Moothart

Answer 4

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

- Burton Samograd

---

不是真的。对于已经排序的数据，它可以正常工作。 - Nikita Rybak

在最简单、最基本的快速排序中，枢轴元素是第一个元素。对于该版本，已经排序好的数据是最坏情况下需要比较的次数（或者是反向排序的数据）。 - Steve Jessop

最坏的情况是一个已经排序好的数组，但我认为即使你检查它是否已经排序好了，仍然会有一些“几乎排序好”的数组，它们将成为“几乎最坏的情况”。 - Berdan Akyürek

Answer 5

最坏情况运行时间取决于快速排序中的划分方法。这有两个方面:

- 选择轴点 - 如何围绕轴点进行划分

在先前的帖子中，已经概述了选择轴点的良好策略（中位数、三数取中或随机化）。但是，即使智能地选择了轴点，在极端情况下，如果一个数组有所有相等的元素，并且只构建了两个分区，它将导致最坏情况运行时间，因为其中一个将携带相等的元素，即所有元素：

- 这会导致对“partion”调用n次，每次平均需要n/2的时间，从而导致O(n²)的时间复杂度。 - 这不好，因为它不是理论上的最坏情况，而是很常见的情况。 - 注意，通过检测空分区无法解决此问题，因为轴点可能具有最高或最低的元素值（例如，中位数为5，这也是最高的元素值，但仍可能存在一些放错位置的<5的值）。

解决此问题的方法是将其划分为三个分区：较低的分区（元素 < 轴点）、相等的分区（元素 = 轴点）和较高的分区。"=轴点元素"处于其最终位置。如果未为空，则仍需要对较低和较高的分区进行排序。

结合随机化、中位数或某些组合来选择轴点，最坏情况的情况非常罕见但并非不可能，这使算法具有O(n²)的最坏情况上限。

- Chris K

Answer 6

我想知道的问题经常被问到。根据我的研究，它的最坏情况有两个关键点。

• 如果数组已经排序，无论是升序还是降序，同时又选择最小值或最大值作为列表中的枢轴元素 [2,3,4] 或 [4,3,2]
• 如果所有元素都相同。[2,2,2]

- Soner from The Ottoman Empire