什么时候应该实现简单或高级的排序算法？

Question

除了显而易见的“当有很多元素时速度更快”之外。什么时候使用简单的排序算法(0(N^2))比使用高级排序算法(O(N log N))更合适？

我读过很多关于插入排序的例子，当你有一个小的数组，几乎是排序的时候，因为你得到了最好的情况N。为什么使用快速排序不好，例如，当你有20个元素的时候。不仅仅是插入或快速，而是在什么时候以及为什么更简单的算法比高级算法更有用？

编辑:例如，如果我们正在处理一个数组，那么我们有什么数据输入很重要吗？例如对象或基本类型(Integer)。

Answer 1

big-oh表示法捕获了N的大值时算法的运行时成本。它在测量小值时的算法运行时效率较低。

从一种算法到另一种算法的实际转换并不是一件微不足道的事情。对于较大的N，N的影响真正占主导地位。对于较小的数字，更复杂的效果变得非常重要。例如，一些算法具有更好的缓存一致性。当您对数据有所了解时，其他方法最好(就像您的插入排序示例一样，当数据接近排序时)。

随着时间的推移，平衡也会发生变化。在过去，CPU速度和内存速度更接近。缓存一致性问题不是什么大问题。在现代，CPU速度通常会将内存总线抛在后面，因此缓存一致性更为重要。

因此，对于何时应该使用一种算法而不是另一种算法，没有一个明确而明确的答案。唯一可靠的答案是分析您的代码并查看。

有趣的是:几年前我正在研究动态的不相交的森林问题。我偶然看到了一篇最先进的论文，它允许在一些愚蠢的东西中完成一些操作，比如O(log log N/ log^4N)。他们做了一些非常出色的数学运算才能做到这一点，但有一个问题。操作是如此昂贵，以至于对于我的50-100个节点的图，它比我最终使用的O(n log n)解决方案要慢得多。这篇论文的解决方案对于在500,000+节点图上操作的人来说要重要得多。

Answer 2

在编写排序算法程序时，您必须考虑到实现实际算法所需的工作量与其实际速度之间的关系。对于大O来说，实现高级算法的时间将超过减少的排序时间。对于小O，例如20-100个项目，差异很小，因此选择更简单的路线要好得多。

Answer 3

首先，O-Notation让您了解最坏的情况。因此，在数组几乎排序的情况下，执行时间可能接近线性时间，例如，它将比快速排序更好。在n足够小的情况下，我们确实考虑了其他方面。像Quick-sort这样的算法会因为调用了所有的递归而变得更慢。在这一点上，这取决于操作系统如何处理递归，递归最终可能比插入-排序中所需的简单算术操作慢。更不用说递归算法所需的额外存储空间了。