使用中位数的快速排序算法在O(n log n)时间内完成排序

Question

我不太明白为什么我们不总是选择中位数作为轴心元素。这可以在O(n)的时间内完成，因此总运行时间为O(n log n)。

我只是猜想可能中位数搜索的O(n)中有一个很大的常数隐藏。

- andy

---

@Gabe - 三个元素的中值，所以是常数时间。 - Joel Lee

更正之前的评论。三个元素（第一个、中间和最后一个）的中位数是选择枢轴的一种方法，但仍可能导致O(n^2)的最坏情况算法。OP的问题假设所有n个元素的中位数。我在第一次阅读时误解了。 - Joel Lee

你要如何在O(n)时间复杂度内选择中位数元素？ - Evegeny

Answer 1

来自维基百科快速排序页面:

相反，一旦我们知道最坏情况下的选择算法是可用的，我们可以使用它在快速排序的每个步骤中找到理想的枢轴（中位数），从而产生具有最坏情况O(n log n)运行时间的变体。然而，在实际实现中，这种变体平均上要慢得多。

换句话说，强制保证O(n log n)的成本通常不值得支付。该页面上还有更多信息，以及选择算法页面上的信息。

- Jon Skeet

Answer 2

看起来使用随机化版本的分区找到中位数的运行时间是O(n)，但实际上当分区在其极端处再次不平衡时，运行时间会变为O(n²)。因此，您从这里无法做出任何改进。 但仍有希望。如果您阅读“CORMEN”，则会发现即使在最坏情况下，也可以在线性时间内找到第i个顺序统计量。使用的技术是将中位数作为枢轴元素，然后找到保证在任何情况下都具有线性运行时间的中位数。 因此，我们还可以在快速排序中使用该技术以获得O(nlogn)的运行时间。

- Avijit Dutta

Answer 3

使用随机化快速排序算法，你可以以非常高的概率获得O(n log n)的最坏情况运行时间。

- duedl0r