42

在分析 QS 时，每个人总是提到“几乎排序”的最坏情况。自然输入何时会出现这种情况？

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

4

6 回答 6

42

我认为人们混淆了基于分区的排序算法的快速排序，以及各种库实现的“qsort”。

我更喜欢将快速排序算法视为具有可插入的枢轴选择算法，这在分析其行为时非常重要。

如果总是选择第一个元素作为枢轴，那么已经排序的列表是最坏的情况。通常数组已经/几乎排序的可能性很高，因此这种实现相当差。

类似地，出于同样的原因，选择最后一个元素作为枢轴是不好的。

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

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

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

所以一些角落被削减了，人们设计了3的中位数算法。当然，后来甚至这也被所谓的 3 中位数“杀手”利用了。

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

真的，除非指定快速排序的特定实现，否则最坏情况何时发生的问题是不明确的。如果您使用所谓的中位数枢轴选择算法，则不会出现二次最坏情况。

然而，大多数库实现可能会失去O(N log N)在平均情况下更快排序的保证。一些真正古老的实现使用第一个元素作为枢轴，现在人们普遍认为它很糟糕，并且不再是广泛遵循的做法。

于 2010-03-10T08:45:19.753 回答
34

我相信快速排序的最坏情况取决于每一步中枢轴元素的选择。如果主元可能是列表中的最小或最大元素（例如，已排序列表的第一个或最后一个元素），则快速排序的性能最差。

例如，如果您选择列表的中间元素，则已排序的列表没有最坏情况的运行时间。

因此，如果您怀疑您的场景可能是快速排序的不良场景，您可以简单地更改您对枢轴元素的选择以使快速排序性能更好。

注意：我知道，这并没有为快速排序最坏情况提供更多真实世界场合的示例。这方面的示例取决于您正在使用的实现。

于 2010-03-10T07:45:05.427 回答
8

实际的问题是：“这种情况（几乎已排序）何时可以通过自然输入发生？”。

尽管所有答案都涉及“导致最坏情况性能的原因”，但没有一个涵盖“导致满足最坏情况性能场景的数据的原因”。

所以，回答实际问题

  • 程序员错误：基本上你会两次对列表进行排序。通常会发生这种情况，因为列表在代码中被排序到一个位置。稍后在另一段代码中，您知道您需要对列表进行排序，因此您再次对其进行排序。

  • 使用几乎按时间顺序排列的数据：您的数据通常按时间顺序接收，但偶尔有些元素不在位。（考虑一个多线程环境，将带时间戳的元素添加到列表中。竞争条件会导致元素以与时间戳不同的顺序添加。）在这种情况下，如果您需要排序数据，则必须重新-种类。因为不能保证数据的顺序。

  • 将项目添加到列表：如果您有一个排序列表并简单地附加一些项目（即不使用二进制插入）。您需要重新排序几乎排序的列表。

  • 来自外部来源的数据：如果您从外部来源接收数据，则可能无法保证它已排序。所以你自己整理。但是，如果对外部源进行了排序，您将重新对数据进行排序。

  • 自然排序：这类似于时序数据。基本上，您收到的数据的自然顺序可能会被排序。考虑一家保险公司增加汽车登记。如果负责汽车登记的当局以可预测的顺序进行，那么较新的汽车可能但不能保证具有更高的登记号。由于您不能保证它已排序 - 您必须重新排序。

  • 交错数据：如果您从具有重叠键的多个排序源接收数据，您可能会得到类似于以下的键：1 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18。即使一半的元素都出来了-of-sequence 与它的邻居，列表是“几乎排序的”。当然，使用以第一个元素为中心的快速排序会表现出O(n^2)性能。

结论

因此，考虑到上述所有情况，实际上很容易对几乎排序的数据进行排序。这正是为什么最好避免以第一个元素为中心的快速排序的原因。polygene 提供了一些关于替代旋转考虑的有趣信息。

作为旁注：通常性能最差的排序算法之一，实际上对“几乎排序”的数据做得很好。在上面的交错数据中，冒泡排序只需要 9 次交换操作。它的性能实际上是O(n)。

于 2014-07-11T17:38:20.463 回答
7

从快速排序

对于快速排序，“最坏情况”对应于已排序

所有具有相同编号的项目的列表已经排序。

于 2010-03-10T07:32:06.383 回答
3

快速排序的最坏情况：

  1. 数组的所有元素都相同
  2. 数组已按相同顺序排序
  3. 数组已按相反顺序排序。
于 2013-05-28T08:31:11.947 回答
1

快速最坏的情况取决于选择枢轴元素。所以只有在 1) 数组已经按相同顺序排序时才会出现问题。2) 数组已按相反顺序排序。3) 所有元素都相同（情况 1 和 2 的特殊情况）

于 2016-05-13T06:05:00.043 回答