问为什么我们总是使用快速排序？或者任何特定的排序算法？

EN

所有提出的算法都有类似的O(n lg n)的平均情况界限，这是comparison sort所能做的“最好”。

由于它们共享相同的平均界限，因此这些算法在随机数据上的预期性能应该是相似的-这就是研究结果所显示的。然而，问题的关键在于细节。这是一个非常快速的总结；点击链接获取更多详细信息。

Quicksort通常不稳定(但也有stable variations)。虽然快速排序的平均范围是O(n lg n)，但快速排序的最坏情况范围是O(n * n)，但有一些方法可以缓解这种情况。与堆排序一样，快速排序也是就地完成的。

Merge-sort是一个 sort。Mergesort有一个最坏的O(n lg n)界限，这意味着它的性能是可预测的。基本合并排序需要O(n)额外的空间，因此它通常不是就地排序(尽管有in-place variant，并且用于链表实现的内存是恒定的)。

Heapsort不稳定；它也具有O(n lg n)的最坏情况界限，但具有固定大小界限和就地的好处。它的缓存和并行性比merge-sort差。

确切地说哪一个是“最好的”取决于用例、数据和确切的实现/变体。

合并排序(或hybrid such as Timsort)是许多库/语言中的“默认”排序实现。在几个C++实现中使用了一个通用的Quicksort-based hybrid, Introsort。普通/普通的快速排序实现，如果提供的话，通常是次要的实现。

合并排序:一种稳定的排序，具有一致的性能和可接受的内存范围。

快速排序/堆排序:简单地就地工作，并且不需要额外的内存。

我们很少需要对整数数据进行排序。排序中最大的开销之一是进行比较所需的时间。快速排序通过与冒泡排序进行比较来减少所需的比较次数。如果你对字符串进行排序，这就更有意义了。作为一个现实世界的例子，几年前我写了一个排序/合并，使用冒泡排序需要40分钟，使用快速排序需要17分钟。(很久以前，它是一台z80处理器。我希望现在有更好的性能)。

你的结论是正确的:在大多数情况下，大多数关心这一点的人都是在浪费时间。这些算法在时间和内存复杂性方面的差异在特定情况下变得非常重要，在这种情况下：

对于实时系统来说，你有大量的元素是非常关键的(例如: sort

• performance systems)

• resources
• (例如:嵌入式系统)

(请注意真实的)

此外，还有对稳定性的担忧，这可能更重要。大多数标准库都提供了稳定的排序算法(例如: C#中的OrderBy、C++中的std::stable_sort、Python中的sort、Java中的sort方法)。