为什么快速排序比归并排序更好？

快速排序的平均时间复杂度较好，但在某些应用中选择它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入，他可以轻易地构造一个需要o(n^2)最坏情况时间复杂度的集合。

归并排序的平均时间复杂度和最坏时间复杂度相同，因此不会出现同样的问题。归并排序的这一特性也使其成为实时系统的优选 - 恰恰因为没有导致它运行缓慢的病态情况。

出于这些原因，我更喜欢归并排序而不是快速排序。

这很难说。归并排序的最差时间复杂度是 n(log2n)-n+1，当 n 等于 2^k 时精确成立（我已经证明过这一点）。而对于任何 n，它的时间复杂度介于 (n lg n - n + 1) 和 (n lg n + n + O(lg n)) 之间。但对于快速排序来说，它的最佳时间复杂度是 nlog2n（同样在 n 等于 2^k 的情况下）。如果你把归并排序的时间复杂度除以快速排序的时间复杂度，当 n 趋近无穷大时会趋近于 1。因此，看起来归并排序的最差情况好像比快速排序的最佳情况要更好，那我们为什么要使用快速排序呢？但请记住，归并排序不是原地排序，它需要 2n 的内存空间，并且还需要进行许多数组拷贝，这些都没有计算在算法分析中。简言之，在理论上，归并排序确实比快速排序更快，但在实际中你需要考虑内存空间和数组拷贝的代价，合并操作比快速排序慢。我曾经做过一个实验，在 Java 中用 Random 类生成了 1000000 个数字，用归并排序需要 2610ms，而用快速排序只需要 1370ms。

快速排序和归并排序的小补充。

另外，这也取决于排序项的种类。如果访问项、交换和比较不是简单的操作，比如在平面内存中比较整数，那么归并排序可能是更好的算法。

例如，我们使用远程服务器上的网络协议对项目进行排序。

此外，在自定义容器（如“链表”）中，快速排序没有任何好处。
1. 在链表上进行归并排序时，不需要额外的内存。 2. 快速排序中的元素访问不是连续的（在内存中）。

一切条件相等的情况下，我预期大多数人会使用最方便的方法，而qsort(3)往往是这样的选择。除此之外，快速排序在数组上非常快，就像合并排序对于列表来说是常见的选择一样。

我想知道的是为什么 基数排序 或桶排序如此罕见。它们都是O(n)，至少对于链表而言，只需要一些将键转换为序数的方法即可。(字符串和浮点数也可以正常工作)

我认为原因与计算机科学教育有关。我甚至不得不向我的算法分析讲师证明比O(n log(n))更快的排序确实是存在的。（他有一个证明，你不能比较排序快于O(n log(n))，这是正确的。）

另外，浮点数可以作为整数进行排序，但排序后必须将负数转回。

编辑： 实际上，这是一种更加恶劣的将浮点数作为整数排序的方法：http://www.stereopsis.com/radix.html。请注意，无论您实际使用什么排序算法，都可以使用位翻转技巧...

虽然它们都属于同一复杂度类，但这并不意味着它们的运行时间相同。快速排序通常比归并排序更快，因为编写紧凑实现并且执行的操作可以更快。正是因为快速排序通常更快，人们才使用它而不是归并排序。

然而！我个人经常会使用归并排序或者快速排序变体，当快速排序表现不佳时会退化到归并排序。记住，快速排序只有在平均情况下才是O(n log n)。最坏情况下是O(n^2)! 归并排序始终是O(n log n)。在实时性能或响应性是必须的情况下，如果您的输入数据可能来自恶意来源，则不应使用普通快速排序。

快速排序是一种原地排序算法，因此更适合于数组。另一方面，归并排序需要额外的O(N)存储空间，更适合于链表。

与数组不同，在链表中我们可以在中间插入项，其空间和时间复杂度均为O(1)，因此归并排序中的合并操作可以在没有任何额外空间的情况下实现。然而，为数组分配和释放额外空间对归并排序的运行时间有不利影响。归并排序也更喜欢链表，因为数据是按顺序访问的，没有太多随机内存访问。

另一方面，快速排序需要大量的随机内存访问，使用数组时我们可以直接访问内存，而无需像链表那样进行遍历。此外，当用于数组时，快速排序具有良好的引用局部性，因为数组在内存中是连续存储的。

尽管这两种排序算法的平均复杂度都是O(NlogN)，但通常人们在普通任务中使用数组进行存储，因此快速排序应该是首选算法。

编辑：我刚刚发现归并排序的最坏/最佳/平均情况始终为nlogn，但快速排序的复杂度可以从n2（当元素已经排序时的最坏情况）到nlogn（当枢轴始终将数组分成两半的平均/最佳情况）。

考虑时间和空间复杂度。 对于归并排序： 时间复杂度：O(nlogn)， 空间复杂度：O(nlogn)

对于快速排序： 时间复杂度：O(n^2)， 空间复杂度：O(n)

现在，它们各自在一个场景中胜出。 但是，使用随机枢轴，您几乎总能将快速排序的时间复杂度降至O(nlogn)。

因此，在许多应用程序中，快速排序比归并排序更受青睐。

在 C/C++ 领域中，如果不使用 STL 容器，我倾向于使用快速排序，因为它已经内置在运行时中，而归并排序则没有。
因此，我相信在许多情况下，这只是最简单的方法。
此外，在整个数据集无法适应工作集的情况下，快速排序的性能可以更高。

其中一个原因是更具哲学性。快速排序是自上而下的哲学。对于要排序的n个元素，有n!种可能性。通过将m和n-m的2个分区互相排斥，可能性的数量会降低几个数量级。m！*（n-m）！比仅有n！小几个数量级。想象一下5！与3！* 2！之间的差异。5！比2个分区中的2和3各自的可能性多10倍。并推广到100万阶乘与900K！* 100K！之间。因此，不必担心在范围或分区内建立任何顺序，只需在分区的更广泛层面上建立顺序，并减少分区内的可能性。如果分区本身不是互相排斥的，则在范围内先建立的任何顺序稍后都会被打乱。
任何自下而上的排序方法，如归并排序或堆排序，都像工人或员工的方法，其中一个人早期就开始在微观层面上进行比较。但是，这种顺序很快就会丢失，因为稍后找到了它们之间的元素。这些方法非常稳定且极其可预测，但需要做一定量的额外工作。
快速排序类似于管理方法，最初不关心任何顺序，只关注满足广泛标准而不考虑顺序。然后缩小分区，直到得到排序的集合。在Quicksort中真正的挑战在于在你什么也不知道要排序的元素时，在暗中找到一个划分或标准。这就是为什么我们需要花一些精力去找到中间值或随机选择1个或某种任意的"管理"方法。找到完美的中位数可能需要很大的努力，并再次导致愚蠢的自下而上方法。因此，快速排序只需选择一个随机中轴线，并希望它会在中间位置或者做一些工作来查找3、5或更多来找到更好的中位数，但不要计划完美，也不要浪费时间在最初的排序上。如果你幸运的话，那么这看起来做得很好，有时候会降级到n^2当你没有得到一个中位数，只是冒险。无论如何，数据是随机的。对的。
因此，我更赞同快速排序的自上而下的逻辑方法，结果表明，它所节省的关于枢轴选​​择和比较的时间，在更多情况下似乎比任何细致和彻底的稳定自下而上的方法，如合并排序更有效。但是