最快的分拣技术

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

（编辑我以前不好的帖子，对不起大家）改善排序算法性能

一种方式是并行处理：

Parallel Sort Algorithm

在这篇文章中，串行和并行快速排序的性能算法使用整数列表进行比较。双核机器的性能显着提升。快速排序，甚至可以在具有N个处理器的系统上O（log n）的执行，根据这篇文章：

http://en.wikipedia.org/wiki/Merge_sort#Parallel_processing

这听起来很虚幻有很多内核，但具备基础架构即服务（亚马逊云，Azure ......），它可以成为任务关键实施的可用选项。

Answer 3

最快的通用排序是归并排序，它可以利用地图/减少模式（其快速排序不能）

但如果你知道一些关于你的资料，数据集可以在某些情况下甚至更快分类比起那个来说。

无法排序快于O（N）是没有意义的：你必须至少应对每个元素一次

在回答您提的基数排序：

（维基百科）

对于k个或更少位数的n个键，基数排序的效率为O（k·n）。有时k表示为一个常量，这会使得基数排序比基于比较的最佳排序算法更好（对于足够大的n），这些排序算法都是O（n·log（n））。但是，通常k不能被认为是一个常数。特别是，在所有密钥都不同的常见（但有时是隐含的）假设下，k必须至少为log（n）的次序，结果不会比其他类型的结果更好。

Answer 4

线性时间运行的一些排序算法是计数排序，基数排序和桶排序。与这些算法有关的是他们需要关于输入的假设。计数排序和基数排序假定输入由小范围内的整数组成。桶排序假定输入由随机过程生成，该过程在一个时间间隔内均匀分布元素。 Page3-6，给出了上述算法的一个很好的轮廓。