当特定的排序算法优于其他算法时，有哪些使用情况 - 归并排序 vs 快速排序 vs 堆排序 vs 'intro sort'等？
是否有建议指南可以根据数据结构的大小、类型、可用内存和缓存以及CPU性能来使用它们？
5个回答
339
首先，定义很重要：稳定排序是保证不重新排列具有相同键的元素的排序算法。
建议：
快速排序：当您不需要稳定排序且平均情况性能比最坏情况性能更重要时使用。平均情况下，快速排序的时间复杂度为 O(N log N)，在最坏情况下为 O(N^2)。良好的实现使用递归栈空间的 O(log N) 辅助存储。
归并排序：当您需要稳定的 O(N log N) 排序时，这是您唯一的选择。它唯一的缺点是它使用 O(N) 的辅助空间，并且具有比快速排序稍大的常数。有一些原地归并排序，但据我所知，它们都不稳定或比 O(N log N) 更糟。即使是 O(N log N) 的原位排序与普通的归并排序相比，其常数也更大，因此它们更多是理论上的好奇心而不是有用的算法。
堆排序：当您不需要稳定排序且您关心的是最坏情况性能而不是平均情况性能时使用。它保证为O(N log N)，并且使用 O(1) 的辅助空间，这意味着在非常大的输入上您不会意外地耗尽堆栈空间或堆空间。
内省排序：这是一种在递归深度达到一定程度后切换到堆排序的快速排序，以避免快速排序的 O(N^2) 最坏情况。它几乎总是优于普通的快速排序，因为您可以获得快速排序的平均情况，同时保证 O(N log N) 的性能。唯一使用堆排序而不是此算法的原因可能是在内存严重受限的系统中，O(log N) 栈空间实际上具有重要意义。
插入排序：当N保证较小，包括作为快速排序或归并排序的基本情况时使用。虽然其时间复杂度为 O(N^2)，但它具有非常小的常数，并且是稳定排序。
建议：
快速排序：当您不需要稳定排序且平均情况性能比最坏情况性能更重要时使用。平均情况下，快速排序的时间复杂度为 O(N log N)，在最坏情况下为 O(N^2)。良好的实现使用递归栈空间的 O(log N) 辅助存储。
归并排序：当您需要稳定的 O(N log N) 排序时，这是您唯一的选择。它唯一的缺点是它使用 O(N) 的辅助空间，并且具有比快速排序稍大的常数。有一些原地归并排序，但据我所知，它们都不稳定或比 O(N log N) 更糟。即使是 O(N log N) 的原位排序与普通的归并排序相比，其常数也更大，因此它们更多是理论上的好奇心而不是有用的算法。
堆排序：当您不需要稳定排序且您关心的是最坏情况性能而不是平均情况性能时使用。它保证为O(N log N)，并且使用 O(1) 的辅助空间，这意味着在非常大的输入上您不会意外地耗尽堆栈空间或堆空间。
内省排序：这是一种在递归深度达到一定程度后切换到堆排序的快速排序，以避免快速排序的 O(N^2) 最坏情况。它几乎总是优于普通的快速排序，因为您可以获得快速排序的平均情况，同时保证 O(N log N) 的性能。唯一使用堆排序而不是此算法的原因可能是在内存严重受限的系统中，O(log N) 栈空间实际上具有重要意义。
插入排序：当N保证较小，包括作为快速排序或归并排序的基本情况时使用。虽然其时间复杂度为 O(N^2)，但它具有非常小的常数，并且是稳定排序。
冒泡排序、选择排序：当你需要快速地完成某个任务，但由于某些原因不能使用标准库中的排序算法时，可以考虑使用这两种算法。它们唯一的优点在于比插入排序稍微容易实现一些。
非比较排序：在某些非常有限的情况下，可以打破O(N log N)的时间复杂度下限，并在O(N)的时间内完成排序。以下是一些值得尝试的情况：
计数排序：当你需要对范围有限的整数进行排序时。
基数排序：当log(N)远大于基数位数K时（其中K是基数位数），可以考虑使用基数排序。
桶排序：当你可以保证输入数据近似均匀分布时，可以考虑使用桶排序。
- dsimcha
17
2非常有趣。您能解释一下如何保证桶排序的“近似均匀分布”吗？ - NNN
2为什么Introsort比快排慢得多？唯一的开销是计算递归深度，这应该是微不足道的。只有在递归远超过良好快排情况下才会进行切换。 - dsimcha
2你没有提到冒泡排序的最佳情况是O(n)! - Tara
1插入排序非常适用于我们知道元素与其原始位置相差 k 个位置且 k 相对于 N 较小的情况。 - Haider Ali
显示剩余12条评论
40
快速排序通常是平均速度最快的，但它在最坏情况下的表现相当糟糕。因此，如果您需要保证没有糟糕的数据导致O(N^2)，则应避免使用它。
归并排序使用额外的内存，但特别适合外部排序（即不适合内存的大型文件）。
堆排序可以原地排序，并且没有最坏情况的二次方行为，但在大多数情况下平均速度比快速排序慢。
在只涉及到限定范围内的整数时，您可以使用某种基数排序来使其非常快。
在99%的情况下，您可以使用库排序，这些排序通常基于快速排序，可以满足需求。
- Eli Bendersky
4
9在99%的情况下，你使用库排序算法通常就可以了，这些算法通常基于快速排序。 - Jim G.
随机化枢轴使快速排序在所有实际情况下的运行时间为O(nlogn)，而不需要任何有关坏数据的保证。我真的不认为有人会在任何生产代码中实现O(n^2)的快速排序。 - MAK
2除了C标准库的qsort，还有哪些排序算法是常用的呢？（http://www.google.com/codesearch/p?hl=en&sa=N&cd=6&ct=rc#XAzRy8oK4zA/libc/stdlib/qsort.c&q=memmove%20android%20package:%22git://android.git.kernel.org/platform/bionic.git%22&d=1）- 大多数“生产代码”排序都依赖于它。 - Eli Bendersky
图书馆排序通常不基于快速排序，因为它不稳定。几乎所有高级语言（除了C）都提供稳定的排序。在我所知道的大多数情况下，您需要一个稳定的，或者至少是确定性的排序。 - 12431234123412341234123
8
维基百科关于排序算法的页面有一张很棒的比较表格。
http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
- Dan Lorenc
3
提供的比较/动画链接并未考虑数据量超过可用内存时的情况，此时对数据的遍历次数即I/O成本将主导运行时间。如果需要进行这种操作，请了解“外部排序”，该技术通常涵盖合并排序和堆排序的变体。
http://corte.si/posts/code/visualisingsorting/index.html 和 http://corte.si/posts/code/timsort/index.html 还展示了一些比较不同排序算法的有趣图片。
http://corte.si/posts/code/visualisingsorting/index.html 和 http://corte.si/posts/code/timsort/index.html 还展示了一些比较不同排序算法的有趣图片。
- Alex Brasetvik
0
@dsimcha 写道： 计数排序：当您对具有有限范围的整数进行排序时
我会改成：
计数排序：当您对正整数进行排序时（0-Integer.MAX_VALUE-2，由于鸽洞原理）。
您始终可以在线性时间内获取最大值和最小值作为效率启发式方法。
此外，您需要至少n个额外空间用于中间数组，它显然是稳定的。
/**
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
尽管实际上它允许到MAX_VALUE-2，但是请注意： Java数组有最大大小吗？
此外，我想解释一下基数排序的复杂度是O(wn)，其中n个键是大小为w的整数。有时w被表示为一个常数，这将使基数排序比所有执行O(n log n)比较以对n个键进行排序的最佳基于比较的排序算法更好（对于足够大的n）。然而，通常情况下，w不能被视为常数：如果所有n个键都不同，则为了能够将它们存储在内存中，随机访问机器的w至少必须为log n，这会给出最好的时间复杂度O(n log n)。（来自维基百科）
- Droid Teahouse
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接