什么是当一个特定的排序算法是preferred用例 - 归并排序 VS 快速排序 VS 堆排序 VS introsort 等？

What are the use cases when a particular sorting algorithm is preferred - merge sort vs quick sort vs heap sort vs introsort, etc?

是否有基于所述大小使用它们推荐指南，数据strucutre，可用存储器和高速缓存和CPU性能的类型。

Is there a recommended guide in using them based on the size, type of data strucutre, available memory and cache, and CPU performance.

推荐答案

首先，定义，因为它是pretty的重要：A 稳定的排序是一个有保证不重新排序具有相同的元素钥匙。

First, a definition, since it's pretty important: A stable sort is one that's guaranteed not to reorder elements with identical keys.

建议：

快速排序：：当你不需要一个稳定的排序和平均情况下的性能超过最坏情况下的性能很重要。快速排序为O（N日志N）的平均值，O（N ^ 2）在最坏的情况下。一个很好的实现使用澳（日志N）的辅助存储在递归的堆栈空间的形式。

Quick sort: When you don't need a stable sort and average case performance matters more than worst case performance. A quick sort is O(N log N) on average, O(N^2) in the worst case. A good implementation uses O(log N) auxiliary storage in the form of stack space for recursion.

合并排序：：当你需要一个稳定的，O（N日志N）的排序，这是你唯一的选择。唯一的缺点是它，它使用的O（N）辅助空间并且具有比快速排序稍大恒定。有一些就地合并排序，但AFAIK他们都是要么不稳定或大于O（N日志N）的恶化。即使在发生各种各样的O（N日志N）有这么多的大常数比普通的旧合并那种他们比有用的算法更理论的好奇心。

Merge sort: When you need a stable, O(N log N) sort, this is about your only option. The only downsides to it are that it uses O(N) auxiliary space and has a slightly larger constant than a quick sort. There are some in-place merge sorts, but AFAIK they are all either not stable or worse than O(N log N). Even the O(N log N) in place sorts have so much larger a constant than the plain old merge sort that they're more theoretical curiosities than useful algorithms.

堆排序：：当你不需要一个稳定的排序，你照顾比一般情况下的性能更多有关最坏情况下的性能。它保证是O（N日志N），并且使用O（1）辅助空间，也就是说，您不会意外了堆或堆栈空间非常大的投入运行。

Heap sort: When you don't need a stable sort and you care more about worst case performance than average case performance. It's guaranteed to be O(N log N), and uses O(1) auxiliary space, meaning that you won't unexpectedly run out of heap or stack space on very large inputs.

Introsort：这是一个快速排序切换到堆排序有一定递归深度后绕过快速排序的O（N ^ 2）最坏的情况。这几乎总是比普通的老式快速排序好，因为你得到了一个快速排序的平均情况，有保障的O（N日志N）的性能。可能是唯一的理由使用堆排序，而不是这是在严重的内存受限的系统，其中O（日志N）的堆栈空间实际上是显著。

Introsort: This is a quick sort that switches to a heap sort after a certain recursion depth to get around quick sort's O(N^2) worst case. It's almost always better than a plain old quick sort, since you get the average case of a quick sort, with guaranteed O(N log N) performance. Probably the only reason to use a heap sort instead of this is in severely memory constrained systems where O(log N) stack space is practically significant.

插入排序：当N是保证小，包括作为一个快速排序的基本情况或归并排序。虽然这是O（N ^ 2），它具有一个非常小的常数，并且是稳定排序

Insertion sort: When N is guaranteed to be small, including as the base case of a quick sort or merge sort. While this is O(N^2), it has a very small constant and is a stable sort.

冒泡排序，选择排序：当你正在做一些快速而肮脏的，由于某种原因，你不能只使用标准库的排序算法。这些都在插入排序的唯一好处是稍微更容易实现。

Bubble sort, selection sort: When you're doing something quick and dirty and for some reason you can't just use the standard library's sorting algorithm. The only advantage these have over insertion sort is being slightly easier to implement.

非比较排序：在某些非常有限的条件下，它有可能打破O（N日志N）的障碍和排序为O（N）。这里有一些情况下，这是值得一试：

Non-comparison sorts: Under some fairly limited conditions it's possible to break the O(N log N) barrier and sort in O(N). Here are some cases where that's worth a try:

计数排序：当你排序整数，范围有限

Counting sort: When you are sorting integers with a limited range.

基数排序：：当日志（N）小于K，其中K是基数的位数显著较大

Radix sort: When log(N) is significantly larger than K, where K is the number of radix digits.

桶排序：当你能保证你的输入近似均匀分布

Bucket sort: When you can guarantee that your input is approximately uniformly distributed.