algorithm - QuickSort 的最坏情况 - 什么时候会发生？

Question

在分析QS时，每一个都是指“几乎排序”的最坏情况。什么时候自然输入会出现这种情况？

我想出的唯一例子是重新索引。

Answer 1

我认为人们混淆了基于分区的排序算法 Quicksort 和各种库实现的“qsort”。

我更愿意将 Quicksort 算法视为具有可插入的枢轴选择算法，这在分析其行为时非常重要。

如果始终选择第一个元素作为基准，那么已经排序的列表是最坏的情况。通常数组已经/接近排序的可能性很高，因此这个实现相当差。

类似地，出于同样的原因，选择最后一个元素作为基准是错误的。

有些实现试图通过选择中间元素作为基准来避免这个问题。这不会在已经排序/接近排序的数组上表现得那么糟糕，但仍然可以构建一个输入来利用这种可预测的枢轴选择并使其以二次方时间运行。

因此，您获得了随机的枢轴选择算法，但即使这样也不能保证 O(N log N)。

因此开发了其他算法，这些算法会在选择一个枢轴之前使用序列中的一些信息。您当然可以扫描整个序列并找到中位数，并将其用作基准。这保证了 O(N log N)，但在实践中当然会更慢。

所以一些角落被削减，人们设计了 median-of-3 算法。当然，后来甚至这也被所谓的 median-of-3“killer”利用了。

因此，人们进行了更多尝试以提出更“智能”的枢轴选择算法，以保证 O(N log N) 渐近行为仍然足够快以实用，并取得了不同程度的成功.

实际上，除非有人指定快速排序的特定实现，否则最坏情况何时发生的问题是不明确的。如果您使用所谓的中值中值枢轴选择算法，则不存在二次最坏情况。

然而，大多数库实现可能会放弃 O(N log N) 保证在一般情况下更快的排序。一些非常古老的实现使用第一个元素作为枢轴，现在人们普遍认为这种做法很差，不再被广泛遵循。