快速排序到已排序的数组 [英] Quicksort to already sorted array

问题描述

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

Alejo Hausner告诉:在最坏的情况下，快速排序的费用是

Alejo Hausner told in: Cost of quicksort, in the worst case, that

具有讽刺意味的是，如果将quicksort应用于已排序的数组，则可能会得到这种代价高昂的行为

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

我不明白.有人可以向我解释.

I cannot get it. Can someone explain it to me.

https://www.quora.com/What-will-be-the-complexity-of-quick-sort-if-array-is-already-sorted 可能是对此的答案，但事实并非如此得到我一个完整的答复.

https://www.quora.com/What-will-be-the-complexity-of-quick-sort-if-array-is-already-sorted may be answer to this, but that did not get me a complete response.

推荐答案

Quicksort算法是这样的:

The Quicksort algorithm is this:

• 选择一个枢轴
• 将小于枢轴的元素移动到起点，将大于枢轴的元素移动到终点
• 现在数组看起来像 [< = p，< = p，< = p，p，> p，> p，> p]
对第一和​​第二一半"进行递归排序.数组

Quicksort将会非常有效，运行时间接近 n log n .如果枢轴是中间值，这将非常有效.但是，选择实际的中位数本身将是昂贵的.如果由于不幸而发生支点变化，成为数组中的最小或最大元素，您将获得如下数组: [p，> p，> p，> p，>p，> p，> p] .如果这种情况经常发生，则您的快速排序"有效地表现为选择排序.在那种情况下，由于要递归排序的子数组的大小在每次迭代时仅减少1，因此将有 n 个迭代级别，每个级别花费 n 个操作，因此总体复杂度将为'n ^ 2.

Quicksort will be efficient, with a running time close to n log n, if the pivot always end up close to the middle of the array. This works perfectly if the pivot is the median value. But selecting the actual median would be costly in itself. If the pivot happens, out of bad luck, to be the smallest or largest element in the array, you'll get an array like this: [p, >p, >p, >p, >p, >p, >p]. If this happens too often, your "quicksort" effectively behaves like selection sort. In that case, since the size of the subarray to be recursively sorted only reduces by 1 at every iteration, there will be n levels of iteration, each one costing n operations, so the overall complexity will be `n^2.

现在，由于我们不愿意使用昂贵的操作来找到一个好的支点，因此我们不妨随机选择一个元素.而且由于我们也不在乎真正的随机性，所以我们可以从数组中选择任意元素，例如第一个.

Now, since we're not willing to use costly operations to find a good pivot, we might as well pick an element at random. And since we also don't really care about any kind of true randomness, we can just pick an arbitrary element from the array, for instance the first one.

如果随机地对数组进行随机混洗，那么选择第一个元素就很棒.您可以合理地希望它会定期为您提供平均"收入.元素.但是如果数组已经被排序了……那么根据定义，第一个元素是最小的.因此，我们处于最糟糕的情况，即复杂度为 n ^ 2 .

If the array was shuffled uniformly at random, then picking the first element is great. You can reasonably hope it will regularly give you an "average" element. But if the array was already sorted... Then by definition the first element is the smallest. So we're in the bad case where the complexity is n^2.

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

A simple way to avoid "bad lists" is to pick a true random element instead of an arbitrary element. Or if you have reasons to believe that quicksort will often be called on lists that are almost sorted, you could pick the element in position n/2 instead of the one in position 1.

也有几篇有关选择枢轴的不同方法的研究论文，其中包括对复杂性影响的精确计算.例如，您可以选择三个随机元素，将它们从最小到最大排列，并保持中间一个.但是结论通常是:如果您尝试编写更好的枢轴选择，那么这样做也将更加昂贵，并且算法的整体复杂性不会得到太大改善.

There are also several research papers about different ways to select the pivot, with precise calculations on the impact on complexity. For instance, you could pick three random elements, rank them from smallest to largest and keep the middle one. But the conclusion usually is: if you try to write a better pivot-selection, then it will also be more costly, and the overall complexity of the algorithm won't be improved that much.

这篇关于快速排序到已排序的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！