每个排序算法何时使用？

当一个特定的排序算法优先于其他的时候有什么用例——合并排序 vs 快速排序 vs 堆排序 vs“介绍排序”等等？

是否有基于大小、数据结构类型、可用内存和缓存以及 CPU 性能的推荐使用指南？

119296 次浏览
小开

维基百科上关于排序算法的页面有一个很棒的比较图表。

Http://en.wikipedia.org/wiki/sorting_algorithm#comparison_of_algorithms

小开

所提供的比较/动画链接没有考虑的是当数据量超过可用内存时——这时数据传递的次数，即 I/O 成本，主导了运行时。如果你需要这样做的话，可以阅读一下“外排序”，它通常涵盖了合并排序和堆排序的变体。

Http://corte.si/posts/code/visualisingsorting/index.html 和 http://corte.si/posts/code/timsort/index.html也有一些很酷的图像比较各种排序算法。

小开

如果只涉及限制范围内的整数，则可以使用某种基数排序来使其非常快速。

在我的项目中有两个软件包: odp.proj和 odp.proj.test。有一些方法我希望只对这两个包中的类可见。我怎么能这么做？

在99% 的情况下，您可以使用库排序，它们通常基于快速排序。

小开

Bucket sort: 当您可以保证您的输入是近似均匀分布的时候。

小开

@ dsimcha 写道:

在 Java 中没有子包的概念，所以 odp.proj和 odp.proj.test是完全独立的包。

对正整数进行排序(0-Integer.MAX _ VALUE-2，因为存在鸽子洞)。

计数排序: 当对范围

有限的整数进行排序时

我会改成:

您总是可以得到最大值和最小值作为一个效率启发式在线性时间以及。

计数排序: 对正整数进行排序时(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;

您总是可以得到最大值和最小值作为一个效率启发式在线性时间以及。
另外，中间数组至少需要 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)

(即使它实际上允许 MAX _ VALUE-2) 参见: 参见: Java 数组有最大大小吗？

Java 数组有最大大小吗？

我还要解释的是，对于 n 个字长 w 的整数，基数排序的复杂度是 O (wn)。有时 w 表示为常量，这会使基数排序(对于足够大 n)比最好的基于比较的排序算法更好，后者都执行 O (n log n)比较来对 n 个键进行排序。然而，一般情况下 w 不能被认为是一个常量: 如果所有的 n 个键都是不同的，那么 w 必须至少是 log n，随机存取机器才能将它们存储在内存中，这最多只能给出一个时间复杂度 o (n log n)。(来自维基百科)


提交答案