最快排序技术

Question

在过去的几天里，我一直在尝试各种排序算法。从1) O(n^2)时间复杂度的排序算法开始2) O(n log n)时间复杂度的就地和非就地排序技术

我想知道是否有排序算法可以在线性时间或更短的时间内排序。我听说过基数排序，在最好的情况下，它接近线性时间排序，具有一定的空间复杂性。有没有人能开导我？

Answer 1

您永远不能排序小于O(N)，因为您必须查看所有N个元素才能确定列表是否已排序--所以这就是O(N)。如果您通过与列表中的其他元素进行比较来进行排序，那么您的排序速度也不会比O(NlogN)快-但如果您对数据有所了解，您就可以做到。例如，如果您知道数据是英文字符串，则可以在排序前将其放入存储桶中。例如，将所有以A开头的字符串放入一个存储桶中，将B放入另一个存储桶中，以此类推。这会很快的。您可能需要将每个存储桶设置得相当大-也许足够容纳1000个字符串，因为并不是所有的存储桶都包含相同数量的字符串。

然后对各个存储桶进行排序，这样会更快。

对于均匀分布的数据(即400个以每个字母开头的字符串，当然您不会有这样的字符串)，我估计这将是O(N) + O(Nlog N/M)，其中M是存储桶的数量。

显然，你可以为第二个字母嵌套存储桶，但是你拥有的存储桶越多，你的空间需求就越大，因为必须在运行中扩展存储桶会耗费你的执行时间，所以你想让它们从一开始就足够大。这意味着它们中的许多将比它们需要的要大得多，因为您不知道关于数据分布的一切。

库排序可能也值得一看。

Answer 2

最快的常规排序是合并排序，它可以利用map / reduce模式(快速排序不能)

但是，如果您对数据有所了解，在某些情况下，对数据集的排序甚至可以比这更快。

排序速度不能超过O(n)，这是没有意义的:每个元素必须至少处理一次

作为对您提到的基数排序的响应：

(来自维基百科)

基数排序的效率是O(k·n)，对于n个位数不超过k的键。有时k被表示为常数，这使得基数排序(对于足够大的n)比最好的基于比较的排序算法更好(对于足够大的n)，它们都是O(n·log(n))。然而，一般而言，k不能被认为是常数。特别是，在常见的(但有时是隐式的)假设下，所有键都是不同的，那么k必须至少是log(n)的量级，从而不会产生比其他排序更好的结果。

Answer 3

一些在线性时间内运行的排序算法有计数排序、基数排序和桶排序。这些算法的缺点是，它们需要对输入进行假设。计数排序和基数排序假设输入由小范围内的整数组成。存储桶排序假设输入是由一个随机过程生成的，该过程在一个间隔内均匀地分布元素。Page3-6，给出了上述算法的一个很好的概述。