为什么快速排序很好?

QuickSort takes N^2 in worst case and NlogN average case. The worst case occurs when data is sorted. This can be mitigated by random shuffle before sorting is started. QuickSort doesn't takes extra memory that is taken by merge sort. If the dataset is large and there are identical items, complexity of Quicksort reduces by using 3 way partition. More the no of identical items better the sort. If all items are identical, it sorts in linear time. [This is default implementation in most libraries]

快速排序总是比归并排序好吗?

不是真的。

归并排序是稳定的，但快速排序不是。所以如果你需要输出的稳定性，你可以使用归并排序。在许多实际应用中需要稳定性。 现在内存很便宜。因此，如果Mergesort使用的额外内存对您的应用程序不是至关重要的，那么使用Mergesort也没有什么害处。

注意:在java中，Arrays.sort()函数对基本数据类型使用快速排序，对对象数据类型使用归并排序。因为对象消耗内存开销，所以为归并排序增加一点开销对于性能来说可能不是什么问题。

参考:在Coursera上观看普林斯顿算法课程第三周的快速排序视频

快速排序是最坏情况O(n²)，然而，平均情况始终执行归并排序。每个算法都是O(nlogn)，但你需要记住，当谈论大O时，我们忽略了较低的复杂度因素。当涉及到常数因子时，快速排序比归并排序有显著的改进。

归并排序也需要O(2n)内存，而快速排序可以就地完成(只需要O(n))。这是快速排序通常比归并排序更受欢迎的另一个原因。

额外信息:

快速排序的最坏情况发生在枢轴选择不佳时。考虑下面的例子:

[5, 4, 3, 2, 1]

If the pivot is chosen as the smallest or largest number in the group then quick sort will run in O(n^2). The probability of choosing the element that is in the largest or smallest 25% of the list is 0.5. That gives the algorithm a 0.5 chance of being a good pivot. If we employ a typical pivot choosing algorithm (say choosing a random element), we have 0.5 chance of choosing a good pivot for every choice of a pivot. For collections of a large size the probability of always choosing a poor pivot is 0.5 * n. Based on this probability quick sort is efficient for the average (and typical) case.

正如其他人所注意到的，快速排序的最坏情况是O(n²)，而归并排序和堆排序则停留在O(nlogn)。然而，在平均情况下，这三个都是O(nlogn);所以它们在大多数情况下是可比较的。

平均而言，快速排序更好的地方在于，内循环意味着将多个值与单个值进行比较，而在其他两个循环中，每次比较时两个项都是不同的。换句话说，Quicksort的读取次数是其他两种算法的一半。在现代cpu上，访问时间在很大程度上决定了性能，因此快速排序最终成为一个很好的首选。

在c/c++领域，当不使用stl容器时，我倾向于使用快速排序，因为它是构建的 进入运行时，而归并排序没有。

所以我相信，在许多情况下，这只是阻力最小的途径。

此外，对于整个数据集不适合工作集的情况，快速排序的性能可以高得多。

与归并排序不同，快速排序不使用辅助空间。而归并排序使用辅助空间O(n)。 归并排序的最坏情况时间复杂度是O(nlogn)而快速排序的最坏情况复杂度是O(n²)这发生在数组已经排序的时候。

快速排序有O(n2)最差情况运行时和O(nlogn)平均情况运行时。然而，在许多情况下，它优于归并排序，因为许多因素影响算法的运行时，并且，当把它们放在一起时，快速排序胜出。

In particular, the often-quoted runtime of sorting algorithms refers to the number of comparisons or the number of swaps necessary to perform to sort the data. This is indeed a good measure of performance, especially since it’s independent of the underlying hardware design. However, other things – such as locality of reference (i.e. do we read lots of elements which are probably in cache?) – also play an important role on current hardware. Quicksort in particular requires little additional space and exhibits good cache locality, and this makes it faster than merge sort in many cases.

此外，通过使用适当的枢轴选择，几乎完全避免快速排序的最坏情况运行时间O(n2)是非常容易的——比如随机选择它(这是一个很好的策略)。

在实践中，许多现代的快速排序实现(特别是libstdc++的std::sort)实际上是introsort，其理论上的最差情况是O(nlogn)，与归并排序相同。它通过限制递归深度，并在超过logn时切换到不同的算法(heapsort)来实现这一点。