algorithm - 最快的分拣技术

Question

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

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

Answer 1

最快的通用排序是合并排序，它可以利用 map/reduce 模式（快速排序不能）

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

你不能比没有意义的 O(n) 更快地排序：你必须至少处理每个元素一次

针对您提到的基数排序：

（来自维基百科）

对于具有 k 位或更少位数的 n 个键，基数排序的效率为 O(k·n)。有时 k 表示为一个常数，这将使基数排序（对于足够大的 n）比最好的基于比较的排序算法更好，这些算法都是 O(n·log(n))。然而，一般来说，k 不能被认为是一个常数。特别是，在所有键都是不同的常见（但有时是隐含的）假设下，那么 k 必须至少是 log(n) 的数量级，这不会导致比其他类型更好的结果。

Answer 2

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

然后对各个桶进行排序，这将很快。

对于数据的均匀分布（即以每个字母开头的 400 个字符串，当然你不会有），我猜测这将是 O(N) + O(Nlog N/M)，其中 M 是数字桶。

您显然可以为第二个字母嵌套存储桶，但是您拥有的存储桶越多，您的空间需求就越大，因为必须动态扩展存储桶会花费您的执行时间，因此您希望它们足够大以开始使用。这意味着它们中的许多将比它们需要的大得多，因为您并不了解有关数据分布的所有信息。

图书馆排序可能也值得一看。

Answer 3

一些以线性时间运行的排序算法是计数排序、基数排序和桶排序。这些算法的问题是它们需要对输入进行假设。计数排序和基数排序假设输入由小范围内的整数组成。桶排序假设输入是由一个随机过程生成的，该过程将元素均匀地分布在一个区间上。第 3-6 页，很好地概述了上述算法。

Answer 4

如果您想了解整数值的最快排序技术，那么我建议您参考以下链接： https ://github.com/fenilgmehta/Fastest-Integer-Sort

它对大数组使用基数排序和计数排序，对小数组使用合并排序和插入排序。据统计，这种排序算法比 C++ std::sort 处理整数值要快得多。

std::sort对于“int64_t array[10000000]” ，它比 C++ STL 快 6 倍。

Answer 5

（编辑我之前的坏帖子，对不起大家）

提高排序算法性能的一种方法是并行处理：

并行排序算法

在这篇文章中，使用整数列表比较了顺序和并行快速排序算法的性能。双核机器的性能显着增强。根据这篇文章，QuickSort 甚至可以在具有 n 个处理器的系统上以 O(log n) 执行：

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

拥有这么多可用的内核可能听起来不现实，但对于基础设施即服务（亚马逊云、Azure ......），它可以成为关键任务实施的可用选项。