为什么在实践中，QuickSort比其他分类算法更好？

cs.stackexchange https://cs.stackexchange.com/questions/3

  •  15-10-2019
  •  | 
  •  

题

在标准算法课程中，我们被教导 QuickSort 在最坏情况下，是$ o（n log n）$，$ o（n^2）$。同时，在最坏情况下研究了其他分类算法，这些算法是$ o（n log n）$（例如 Mergesort 和 heapsort），甚至在最佳情况下是线性的时间（例如 Bubblesort）但是有一些其他内存需求。

快速瞥了一眼 更多的运行时间 很自然地说QuickSort 不应该 像其他人一样高效。

另外，考虑到学生在基本的编程课程中学习递归并不是一般不好的，因为它可能会使用过多的记忆，等等。真的很好，因为它是一种递归算法。

那么，为什么QuickSort在实践中的其他分类算法会优于其他分类算法？ 它与结构有关 现实世界数据？它与内存在计算机中的工作方式有关吗？我知道某些记忆比其他记忆要快，但是我不知道这是否是这种违反直觉表现的真正原因（与理论估计相比）。

更新1： 一个规范的答案说，平均情况的$ O（n log n）$涉及的常数小于其他$ O（n log n）$算法所涉及的常数。但是，我还没有看到正确的理由，而不是只有直觉的想法。

无论如何，在内存级别上，实际上似乎发生了真正的差异，在内存级别，实现利用计算机的内部结构，例如使用，例如，缓存内存比RAM快。讨论已经很有趣，但是我仍然想了解有关记忆管理的更多细节，因为看来 这 答案与它有关。

更新2： 有几个网页提供了分类算法的比较，有些比其他网页（最著名的是 sorting-algorithms.com）。除了提供一个很好的视觉辅助功能外，这种方法无法回答我的问题。

有帮助吗？

解决方案

简短的答案

缓存效率论点已经详细解释。此外，还有一个内在的论点，为什么QuickSort快速。如果像两个“交叉指针”一样实施 例如在这里, ，内部环的身体很小。由于这是最常执行的代码，因此这是有回报的。

长答案

首先，

这 平均情况不存在！

由于最好和最坏的情况通常是在实践中很少发生的极端情况，因此进行了平均病例分析。但是任何平均案例分析都假设一些 输入的分布呢对于分类，典型的选择是 随机排列模型 （在维基百科上默认假设）。

为什么要$ o $ - 注释？

在算法分析中丢弃常数是出于一个主要原因：如果我对 精确的 跑步时间， 我需要所有涉及的基本操作的（相对）费用 （即使仍然忽略了缓存问题，现代处理器中的管道...）。数学分析可以 数数 每次指令的执行频率频率，但是单个指令的运行时间取决于处理器的详细信息，例如32位整数乘法是否需要与添加一样多的时间。

有两种方法：

  1. 修复一些机器型号。

    这是在唐 诺斯的书系列 “计算机编程的艺术” 对于作者发明的人工“典型”计算机。在第3卷中，您找到了准确的 平均情况结果 对于许多分类算法，例如

    • QuickSort：$ 11.667（n+1） ln（n）-1.74n-18.74 $
    • Mergesort：$ 12.5 n ln（n）$
    • heapsort：$ 16 n ln（n） +0.01n $
    • Insertionsort：$ 2.25N^2+7.75n-3ln（n）$Runtimes of several sorting algorithms
      [资源]

    这些结果表明QuickSort最快。但是，它只有在Knuth的人造机器上证明，它并不一定意味着您的X86 PC。还要注意，对于小输入，该算法有所不同：
    Runtimes of several sorting algorithms for small inputs
    [资源]

  2. 分析摘要 基本操作.

    对于基于比较的分类，这通常是 掉期 和 关键比较. 。在罗伯特·塞奇威克（Robert Sedgewick）的书中，例如 “算法”, ，采用这种方法。你在那里找到

    • QuickSort：$ 2N ln（n）$比较和$ frac13n ln（n）$掉期交换
    • Mergesort：$ 1.44N ln（n）$比较，但最高$ 8.66n ln（n）$ array访问（Mergesort不基于交换，因此我们无法计算）。
    • Insertionsort：$ frac14n^2 $比较和$ frac14n^2 $换句。

    如您所见，这不容易允许将算法的比较与确切的运行时分析进行比较，但结果与机器详细信息无关。

其他输入分布

如上所述，平均情况总是与某些输入分布有关，因此除了随机排列以外，人们可能会考虑其他情况。例如研究 具有平等元素的QuickSort 还有关于 Java中的标准排序功能

其他提示

关于这个问题，可以提出多个要点。

QuickSort通常很快

尽管QuickSort具有最差的$ o（n^2）$行为，但通常很快：假设随机枢轴选择，我们很有可能选择将输入分为两个类似大小的子集的数字，这正是我们的目标想要有。

特别是，即使我们选择了一个枢轴，该枢轴每10次分裂（即MEH拆分）和1个元素-N-1 $元素拆分（否则，这是最糟糕的拆分，您可以可以，您可以，您可以get），我们的运行时间仍然是$ O（n log n）$（请注意，这会吹出常数到合并排序可能更快的一点）。

QuickSort通常比大多数情况更快

QuickSort通常比$ O（n log n）$慢的速度要快（例如，以其$ O（n^2）$运行时间插入排序），仅仅是因为大的$ n $运行时间爆炸。

与大多数其他$ O（n log n）$算法（如Heapsort）相比，QuickSort在实践中如此迅速的一个很好的理由是因为它相对可缓存效率。它的运行时间实际上是$ o（ frac {n} {b} log（ frac {n} {b}））$，其中$ b $是块大小。另一方面，Hepsort没有任何这样的加速：它根本没有访问内存高效。

此缓存效率的原因是，它线性扫描输入并线性划分输入。这意味着我们可以充分利用我们在读取加载到缓存中的每个数字之前所做的每个缓存负载，然后再将该缓存交换为另一个。特别是，该算法是符合缓存的算法，它为每个缓存级别提供了良好的缓存性能，这是另一个胜利。

缓存效率可以进一步提高到$ o（ frac {n} {b} log _ { frac {m} {m} {b}}}（ frac {n} {b}））$，其中$ m $是大小如果我们使用$ k $ -way QuickSort，则是我们的主要内存。请注意，Mergesort也具有与QuickSort相同的缓存效率，如果内存是严重的约束，则其K-Way版本实际上具有更好的性能（通过较低的恒定因素）。这引起了下一个点：我们需要将QuickSort与其他因素进行比较。

QuickSort通常比Mergesort快

这种比较完全涉及恒定因素（如果考虑典型情况）。特别是，选择是在乘坐速索的次优选择与Mergesort的整个输入的副本（或避免此复制所需的算法的复杂性）之间的选择。事实证明，前者更有效：这背后没有理论，它恰好更快。

请注意，QuickSort将拨打更多的递归电话，但是分配堆栈空间便宜（实际上，只要您不吹堆，就几乎免费），然后再使用它。在堆上分配一个巨大的块（或您的硬盘驱动器，如果$ n $是 真的 大）要贵得多，但是与上面提到的$ o（n）$工作相比，两者都是$ O（ log n）$开销。

最后，请注意，QuickSort对恰好处于正确顺序的输入略有敏感，在这种情况下，它可以跳过一些交换。 Mergesort没有任何此类优化，这也使QuickSort与Mergesort相比更快。

使用适合您需求的类型

总之：没有排序算法始终是最佳的。选择哪种适合您的需求。如果您需要大多数情况下最快的算法，并且您不介意在极少数情况下可能会有点慢，并且您不需要稳定的排序，请使用QuickSort。否则，请使用更适合您需求的算法。

在我的大学的一个编程教程中，我们要求学生比较QuickSort，Mergesort，插入分类与Python的内置列表的表现（称为sort.sort）（称为 蒂姆索尔）。自内置列表以来，实验结果使我感到非常惊讶。SORT的执行效果要比其他分类算法好得多，即使在很容易地使QuickSort的实例中，Mergesort崩溃也是如此。因此，结论是，通常的QuickSort实施是实践中最好的。但是我敢肯定，QuickSort的实现得多，或者在那里的某些混合版本。

这是一篇不错的博客文章 David R. Maciver 将Timsort解释为一种自适应合并的形式。

我认为，与其他排序算法相比，QuickSort如此之快的主要原因之一是因为它对缓存友好。当QS处理数组的段时，它会在段的开头和末端访问元素，并朝段的中心移动。

因此，当您启动时，您将访问数组中的第一个元素，并将一个内存（“位置”）加载到缓存中。而且，当您尝试访问第二个元素时，它已经（很可能）在缓存中，因此非常快。

其他算法（例如Heapsort）不做这样的工作，它们会经常跳入阵列，这使它们较慢。

其他人已经说过渐近 平均 QuickSort的运行时（在常数中）比其他排序算法（在某些设置）更好。

这意味着什么？假设随机选择任何排列（假设分布均匀）。在这种情况下，典型的枢轴选择方法提供了枢轴 期望 将列表/阵列大约分为一半；这就是将我们带到$ cal {o}（n log n）$的原因。但是，此外， 合并 通过递归获得的部分溶液仅需恒定时间（与Mergesort的线性时间相反）。当然，根据枢轴将输入分隔两个列表是线性的，但是通常几乎不需要实际交换。

请注意，QuickSort有许多变体（请参阅Sedgewick的论文）。它们在不同的输入分布（统一，几乎分类，几乎是反向分类，许多重复...）上的性能有所不同，而其他算法对某些人来说可能更好。

另一个值得注意的事实是，QuickSort是 减缓 与SIMPER算法相比，在短开销的简短输入中。因此，如果输入长度小于某些$ k 10 $，则良好的库不会重复到长度列表，而是（例如）插入排序。

与其他基于比较的排序算法相比，具有$ O（n lg n）$ time复杂性，通常认为Quick-Sort比Merge-Sort（如Merge-Sort）更好地认为，因为它是一个现场排序算法。换句话说，我们不需要（更多）内存来存储数组的成员。

PS：确切地说，比其他算法要好于任务。对于某些任务，最好使用其他排序算法。

也可以看看：

即使Quick-Sort的运行时间为$ theta（n^2）$，但QuickSort被认为是最好的排序，因为它的平均水平非常有效：其预期运行时间为$ theta（n log n log n ）$，与其他分类算法相比，常数很小。这是使用其他排序算法快速排序的主要原因。

第二个原因是它执行 in-place 分类并与虚拟内存环境非常有效。

更新： ：（在Janoma和Svick的评论之后）

为了说明这一点更好，让我以合并排序为例（因为合并排序是快速排序之后的下一个广泛采用的算法），并告诉您额外的常数来自哪里（据我所知，我认为为什么快速排序更好）：

考虑以下序列：

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

如果您完全关心最后阶段的发生方式，则将前12个与8和8进行比较，因此首先进行。现在，与21和12相比，现在12又是接下来的，依此类推。如果您将最终合并与其他4个元素进行4个元素，则会将很多额外的比较作为常数，而不会快速产生。这就是为什么优先选择快速排序的原因。

我使用现实世界数据的经验是 QuickSort是一个糟糕的选择. 。 QuickSort可以与随机数据合作，但是现实世界中的数据通常不是随机的。

早在2008年，我跟踪了一个悬挂的软件错误，可以使用QuickSort。一段时间后，我编写了简单的插入排序，QuickSort，堆排序和合并排序并测试这些简单的植入术。我的合并分类在处理大型数据集时优于其他所有内容。

从那时起，合并排序是我选择的排序算法。它很优雅。实现很容易。这是稳定的。它不会像QuickSort那样退化为二次行为。我切换到插入排序以排序小阵列。

在许多情况下，我发现我的自我认为，对于QuickSort来说，给定的实现非常出色，只是发现它实际上不是QuickSort。有时，实现在QuickSort和另一种算法之间会切换，有时它根本不使用QuickSort。例如，GLIBC的QSORT（）函数实际使用合并排序。只有分配工作空间失败时，它才能返回到就地的QuickSort 代码评论称之为“较慢的算法”.

编辑：诸如Java，Python和Perl之类的编程语言也使用合并排序，或更精确的导数，例如Timsort或Merge Sort用于大型集和插入小型集。 （Java还使用比普通QuickSort快的双旋转QuickSort。）

1 - 快速排序是在现场的（不需要额外的memmory，除了恒定数量外。）

2 - 快速排序比其他有效的排序算法更容易实现。

3 - 与其他有效的排序算法相比，快速排序在运行时间中具有较小的恒定因素。

更新：对于合并排序，您需要进行一些“合并”，在合并之前需要额外的数组来存储数据；但是快速地，您不会。这就是为什么快速排序就位。还进行了一些额外的比较，以增加合并排序的恒定因素。

在什么条件下，特定的排序算法实际上是最快的？

1）当用硬件并行实施时，是否需要具有相当低的延迟，同时需要尽可能少的门？是 - >使用bitonic分类器或批处理奇数杂项，延迟为$ theta（ log（n）^2）$，比较器和多路复用器的数量为$ theta（n cdot log（n）^ 2）$。

2）每个元素可以具有多少个不同的值？罐子在内存或缓存中分配了一个唯一位置，是 - >使用计数排序或radix排序，通常具有$ theta（n cdot k）$（count stort）或$ theta（n）的线性运行时（n cdot k） cdot m）$（桶排序），但对大量不同的值放慢速度，因为$ k = 2^{＃ _of _possible _values} $和$ m = #maximum _length _length _keys $。

3）基础数据结构是否由链接元素组成？是 - > Allways使用合并排序。既有易于实现固定尺寸或自适应（又称自然）的自下而上，以合并各种不同的ARITE，链接数据结构，并且由于它们永远不需要在每个步骤中复制整个数据，并且它们也不需要递归，因此它们是比其他任何基于一般比较的类别都要快，甚至比快速排序更快。

4）排序需要稳定吗？是 - >使用合并排序，无论是否适当，固定大小或自适应，具体取决于基础数据结构和预期的数据种类，即使在否则会优选快速排序的情况下，可以稳定任意分类的情况在最坏的情况下，算法需要$ theta（n）$附加内存，该记忆由原始索引组成，这也需要与要在输入数据上执行的每个互换保持同步超过合并的排序可能受到挫败。

5）底层数据的大小可以绑定到中小型大小吗？例如，n <10,000 ... 100,000,000（取决于基础架构和数据结构）？是 - >使用Bitonic排序或批次奇数合元。 Goto 1）

6）您可以省去另一个$ theta（n）$内存吗？是 - > a）输入数据是否由已经分类的顺序数据组成？ - >使用自适应（又名自然）合并排序或tim排序是 - > b）输入数据主要包含几乎在正确位置的元素？ - >使用气泡排序或插入排序。如果您担心他们的$ theta（n^2）$时间复杂性（对于几乎分类的数据是病理学），则可以考虑使用（几乎）渐近最佳的间隙序列切换到Shell排序，某些序列产生$ theta（ n cdot log（n）^2）$最差的情况运行时间是已知的，或者可能尝试梳子排序。我不确定外壳排序或梳子排序在实践中表现出色。

否 - > 7）您可以省去另一个$ theta（ log（n））$内存吗？是的 - > a）非属性数据结构是否允许有向的顺序访问或更好？是的 - >它是否只允许一次直到达到数据末尾的读取/写入访问（例如，有向磁带访问）？是 - > i）使用合并排序，但是没有明显的方法可以使这种情况适当，因此可能需要额外的$ theta（n）$内存。但是，如果您有时间和球做到这一点，则有一种方法可以按$ theta（n）$ time合并2个阵列，仅使用$ theta（ log（n））$ space以稳定的方式合并。唐纳德·E·努斯（Donald E. Knuth）“计算机编程的艺术，第3卷：排序和搜索”，练习5.5.3。指出有L. trabb-pardo的算法是这样做的。但是，我怀疑这会比上面案例的Naive Mergesort版本或QuickSort更快。不，它允许多个同时访问一系列数据（例如，不是磁带驱动器） - > II）使用QuickSort，用于实际目的，我建议您进行随机或近似的中位数。如果您对病理$ theta（n^2）$案件保持警惕，请考虑使用介绍性排序。如果您在确定性行为上陷入困境，请考虑使用中位数算法选择枢轴元素，它需要$ theta（n）$时间，其天真的实现需要$ theta（n）$ space（可行的），尽管它可以仅需$ theta（ log（n））$ space（不平行）。但是，中位数算法为您提供了确定性的QuickSort，它具有最差的$ theta（n cdot log（n））$运行时间。否 - >您被搞砸了（对不起，我们至少需要一种访问每个数据元素的方式）

否 - > 8）您可以省去少量的内存吗？是 - >基础数据结构是否允许随机访问？是 - >使用Heapsort，它具有$ theta（n cdot log（n））$的渐近最佳运行时，但是令人沮丧的缓存相干性且不能很好地平行。否 - >你被拧不清 - >你被拧紧了

QuickSort的实施提示：

1）幼稚的二进制QuickSort需要$ theta（n）$附加内存，但是，通过将最后一个递归调用重写为循环，将其降低到$ theta（ log（n））$相对容易。对于k> 2的k-ary quicksorts做同样的操作，需要$ theta（n^{ log_k（k-1）}）$ space（根据主定理），因此二进制QuickSort需要最少的内存，但是我很高兴听到是否有人知道K-Ary QuickSort for K> 2是否比在某些真实世界设置中的二进制QuickSort更快。

2）有自下而上的QuickSort迭代变体，但是Afaik，它们具有与自上而下的渐近空间和时间界相同的渐近空间和时间界，并且难以实施的额外的下降侧面（例如，明确管理队列）。我的经验是，出于任何实际目的，这些都是不值得考虑的。

Mergesort的实施提示：

1）Botsum-Up Mergesort总是比自上而下的Mergesort快，因为它不需要递归电话。

2）可以通过使用双缓冲区并切换缓冲区而不是在每个步骤后从时间数组中复制数据，而不是复制数据。

3）对于许多实际数据，自适应Mergesort比固定尺寸的Mergesort快得多。

4）合并算法可以通过将输入数据分配到k大约相同尺寸的零件中轻松平行。这将需要k引用到数据中，并且选择k是一件好事，以使所有k（或用于小常数c> = 1）的所有c*k都符合最接近的内存层次结构（通常是L1数据缓存）。选择最小的k元素以幼稚的方式（线性搜索）需要$ theta（k）$时间，而在这些k元素中构建一个分钟并选择最小的元素只需要amortized $ theta（ log（ log）（ log（ log） k））$时间（当然，选择最低限度为$ theta（1）$，但是我们需要进行一些维护，因为每个步骤中删除了一个元素并由另一个元素替换）。并行合并总是需要$ theta（n）$内存，无论k。

从我所写的内容来看，很明显，QuickSort通常不是最快的算法，除非以下条件适用：

1）不仅有“几个”可能的值

2）基础数据结构没有链接

3）我们不需要稳定的订单

4）数据足够大，以至于少量的渐近渐近运行时间是Bitonic分道机或批处理奇数杂项的启动

5）数据几乎没有排序，也不由较大的已经分类的零件组成

6）我们可以从多个位置同时访问数据序列

7）{记忆写作特别昂贵（因为那是Mergesort的主要劣势），只要它将算法放慢速度超出了QuickSort的可能的次优式拆分。 }或{我们只能拥有$ theta（ log（n））$额外内存，$ theta（n）$太多（例如外部存储）}

PS：有人需要帮助我进行文本的格式。

大多数排序方法都必须以简短的步骤移动数据（例如，合并排序在本地进行更改，然后合并了这一小数据，然后合并了一个更大的数据。）。因此，如果数据远离目的地，则需要许多数据移动。

QuickSort，另一侧试图互换数字，这些数字在内存的第一部分，很大，数字位于数组的第二部分，并且很小（如果您要排序$ a le B $，则在其他意义上，争论是相同的），因此他们在最终目的地附近迅速分配。

许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top