algorithm - 对已经排序的数组进行快速排序

Question

在这个问题中:https://www.quora.com/What-is-randomized-quicksort

Alejo Hausner 曾说过:快速排序的成本，在最坏的情况下，即

Ironically, if you apply quicksort to an array that is already sorted, you will get probably get this costly behavior

我无法得到它。谁能给我解释一下。

https://www.quora.com/What-will-be-the-complexity-of-quick-sort-if-array-is-already-sorted可能是对此的回答，但这并没有让我得到完整的回应。

Answer 1

快速排序算法是这样的:

• 选择一个支点
• 将小于pivot的元素移到开头，将大于pivot的元素移到末尾
• 现在数组看起来像[<=p, <=p, <=p, p, >p, >p, >p]
• 递归排序数组的第一和第二“一半”

Quicksort 将是高效的，运行时间接近 n log n ，如果枢轴总是靠近数组的中间结束。如果枢轴是中值，这将非常有效。但是选择实际的中位数本身成本就很高。如果不幸的是，主元恰好成为数组中最小或最大的元素，您将得到这样的数组:[p, >p, >p, >p, >p, >p, >p] .如果这种情况经常发生，您的“快速排序”实际上就像选择排序一样。在这种情况下，由于要递归排序的子数组的大小在每次迭代中仅减少 1，因此将有 n迭代级别，每个迭代成本 n操作，因此整体复杂度将为 `n^2。

现在，既然我们不愿意使用代价高昂的操作来找到一个好的主元，我们不妨随机选择一个元素。而且由于我们也不真正关心任何类型的真正随机性，我们可以只从数组中选择一个任意元素，例如第一个元素。

如果数组被随机均匀地打乱，那么选择第一个元素就很好了。您可以合理地希望它会定期给您一个“平均”元素。但是如果数组已经排序......那么根据定义第一个元素是最小的。所以我们处于复杂度为 n^2 的糟糕情况.

避免“坏列表”的一个简单方法是选择真正的随机元素而不是任意元素。或者，如果您有理由相信快速排序通常会在几乎已排序的列表上调用，您可以选择位置 n/2 中的元素。而不是位置 1 的那个。

还有几篇研究论文介绍了选择枢轴的不同方法，并精确计算了对复杂性的影响。例如，您可以选择三个随机元素，将它们从小到大排列并保留中间的元素。但结论通常是:如果你试图写一个更好的 pivot-selection，那么它的成本也会更高，算法的整体复杂度也不会提高那么多。