61

有没有人能够给出一个“简单的英语”直观但正式的解释是什么让 QuickSort n log n？据我了解，它必须通过 n 项，并且它会记录 n 次......我不知道如何用语言表达为什么它会记录 n 次。

4

6 回答 6

162

复杂

快速排序首先将输入分成两个块：它选择一个“枢轴”值，并将输入划分为小于枢轴值和大于枢轴值的输入（当然，任何等于枢轴值的都有当然，进入其中一个或另一个，但对于基本描述，那些最终出现的并不重要）。

由于输入（根据定义）没有排序，因此要像这样对其进行分区，它必须查看输入中的每个项目，所以这是一个 O(N) 操作。在第一次对输入进行分区后，它递归地对每个“块”进行排序。这些递归调用中的每一个都会查看它的每一个输入，因此在这两个调用之间它最终会访问每个输入值（再次）。因此，在分区的第一个“级别”，我们有一个调用来查看每个输入项。在第二级，我们有两个分区步骤，但在这两个步骤之间，他们（再次）查看每个输入项。每个连续级别都有更多单独的分区步骤，但每个级别的调用总共会查看所有输入项。

它继续将输入划分为越来越小的部分，直到达到分区大小的某个下限。最小的可能是每个分区中的单个项目。

理想案例

在理想情况下，我们希望每个分区步骤将输入分成两半。“一半”可能不会完全相等，但如果我们选择好枢轴，它们应该非常接近。为了保持数学简单，让我们假设完美的分区，所以我们每次都得到精确的一半。

在这种情况下，我们可以将其分成两半的次数将是输入数量的以 2 为底的对数。例如，给定 128 个输入，我们得到的分区大小为 64、32、16、8、4、2 和 1。这是 7 个分区级别（是的，log 2 (128) = 7）。

因此，我们有 log(N) 分区“级别”，每个级别都必须访问所有 N 个输入。因此，log(N) 个级别乘以每个级别的 N 次操作给了我们 O(N log N) 的整体复杂度。

最差的情况

现在让我们重新审视每个分区级别都会将输入精确地“打破”一半的假设。根据我们对分区元素的选择有多好，我们可能不会得到精确相等的一半。那么可能发生的最坏情况是什么？最坏的情况是枢轴实际上是输入中的最小或最大元素。在这种情况下，我们执行 O(N) 分区级别，但不是得到大小相等的两半，而是得到一个元素的一个分区和 N-1 个元素的一个分区。如果每个分区级别都发生这种情况，那么我们显然最终会在分区下降到一个元素之前进行 O(N) 分区级别。

这为快速排序提供了技术上正确的大 O 复杂度（大 O 正式指的是复杂度的上限）。由于我们有 O(N) 级别的分区，并且每个级别都需要 O(N) 步，我们最终会得到 O(N * N)（即 O(N 2 )）的复杂度。

实际实现

实际上，实际实现通常会在实际到达单个元素的分区之前停止分区。在典型情况下，当一个分区包含 10 个或更少的元素时，您将停止分区并使用诸如插入排序之类的东西（因为对于少量元素它通常更快）。

修改后的算法

最近已经发明了对快速排序的其他修改（例如，Introsort、PDQ 排序），它们可以防止 O(N 2 ) 最坏的情况。Introsort 通过跟踪当前分区“级别”来做到这一点，并且当/如果它太深时，它将切换到堆排序，这对于典型输入来说比快速排序慢，但保证 O(N log N) 复杂度对于任何输入。

PDQ 排序为此增加了另一个变化：由于堆排序较慢，因此它会尽可能避免切换到堆排序为此，如果看起来它的枢轴值很差，它会在选择之前随机打乱一些输入枢。然后，如果（且仅当）未能产生足够好的枢轴值，它将切换到使用堆排序。

于 2012-05-03T05:24:55.593 回答
50

每个分区操作都需要 O(n) 次操作（对数组进行一次传递）。平均而言，每个分区将数组分为两部分（总计为 log n 个操作）。我们总共有 O(n * log n) 操作。

即平均 log n 分区操作，每个分区需要 O(n) 操作。

于 2012-05-03T05:24:00.027 回答
4

对数背后有一个关键的直觉：

在达到 1 之前，您可以将数字 n 除以常数的次数是 O(log n)。

换句话说，如果您看到一个运行时具有 O(log n) 项，那么您很有可能会发现某些东西会以一个常数因子反复缩小。

在快速排序中，按一个常数因子缩小的是每个级别的最大递归调用的大小。快速排序的工作原理是选择一个枢轴，将数组拆分为两个小于枢轴的元素和大于枢轴的元素的子数组，然后递归地对每个子数组进行排序。

如果你随机选择枢轴，那么选择的枢轴有 50% 的机会位于中间 50% 的元素中，这意味着有 80% 的机会两个子数组中较大的一个最多为 75%原件的大小。（你明白为什么吗？）

因此，为什么快速排序在 O(n log n) 时间内运行的一个很好的直觉如下：递归树中的每一层都做 O(n) 的工作，并且由于每个递归调用都有很好的机会减少数组的大小至少 25%，我们希望在你用完要丢弃的元素之前有 O(log n) 层。

当然，这假设您随机选择枢轴。许多快速排序的实现都使用启发式方法来尝试在不做太多工作的情况下获得一个不错的枢轴，不幸的是，在最坏的情况下，这些实现可能会导致整体运行时差。@Jerry Coffin 对这个问题的出色回答谈到了快速排序的一些变化，它们通过切换使用哪种排序算法来保证 O(n log n) 最坏情况的行为，这是寻找更多信息的好地方。

于 2019-06-26T18:09:53.917 回答
2

好吧，它并不总是 n(log n)。这是选择的枢轴大约在中间时的表演时间。在最坏的情况下，如果您选择最小或最大元素作为枢轴，那么时间将为 O(n^2)。

为了可视化“n log n”，您可以假设枢轴是最接近要排序的数组中所有元素的平均值的元素。这会将数组分成两个长度大致相同的部分。在这两个上，您都应用快速排序过程。

就像在将数组长度减半的每一步一样，您将执行 log n(base 2) 次，直到达到 length = 1，即 1 个元素的排序数组。

于 2012-05-03T05:28:34.257 回答
1

将排序算法分为两部分。首先是分区和第二个递归调用。分区的复杂度是 O(N)，递归调用理想情况的复杂度是 O(logN)。例如，如果您有 4 个输入，那么将有 2(log4) 个递归调用。将两者相乘得到 O(NlogN)。这是一个非常基本的解释。

于 2019-08-11T14:33:08.820 回答
0

事实上，您需要找到所有 N 个元素的位置（枢轴），但是每个元素的最大比较次数是 logN（第一个是 N，第二个枢轴 N/2，第三个 N/4 ..假设枢轴是中值元素）

于 2016-02-21T05:27:43.950 回答