你可以在O（n）摊销复杂性中排序n个整数吗？

Question

从理论上讲，是否可以在一个分期复杂的O（n）中对n个整数数组进行排序？

如何尝试创建O（n）复杂度的最坏情况？目前大多数算法都是建立在O（nlogn）平均值+ O（n^2）最坏的情况下。 有些使用更多内存时O（nlogn）最差。

你可以没有限制内存使用创建这样的算法？ 如果你的记忆力有限，该怎么办？这将如何伤害你的算法？

Answer 1

任何网页上的基于比较的排序will tell you交易的intertubes你不能排序比O(n lg n)更快地比较排序。也就是说，如果你的排序算法通过比较两个元素来决定顺序，你不能做得比这更好。例子包括quicksort，bubblesort，mergesort。

一些算法，如计数排序或桶排序或基数排序不使用比较。相反，它们依赖于数据本身的属性，如数据中值的范围或数据值的大小。

那些算法可能有更快的复杂性。下面是一个示例场景：

要排序10^6整数，每个整数是0和10之间。然后你可以计算零，一，二等的数量，并按排序顺序将它们吐出。这是如何countort工作，在O(n + m)其中m是您的数据可以采取的值的数量（在这种情况下，m=11）。

另：

要排序10^6二进制字符串的长度均在最5字符。您可以使用基数排序：首先根据它们的第一个字符将它们拆分成2个桶，然后将它们排序为第二个字符，第三个，第四个和第五个。只要每一步都是稳定的排序，您应该在O(nm)中得到一个完美的排序列表，其中m是您的数据中的位数或位数（在这种情况下为m=5）。

但在一般情况下，您不能比O(n lg n)可靠排序（使用比较排序）。

Answer 2

我相信你在寻找radix sort。

Answer 3

如果整数在有限的范围内，那么对它们进行O（n）“排序”将涉及具有“n”位的位向量......循环所讨论的整数并将n％8位该字节数组中的offset n // 8的值为true。这是一个“O（n）”操作。通过该位阵列的另一个循环来列出/枚举/返回/打印所有的设置位，同样是O（n）操作。 （自然O（2n）减少到O（n））。

这是一个特殊情况，其中n足够小以适应内存或文件（使用seek（））操作）。这不是一个通用的解决方案;但它在Bentley的“程序珍珠”中有所描述---据称这是解决现实世界问题的一种实际解决方案（涉及诸如电话号码的“freelist”之类的东西......例如：找到第一个可用的电话号码发给一个新的用户）。 （注意：log（10 * 10）是〜24位来表示长度最多为10位数的每个可能的整数......所以在典型的Unix/Linux最大值中，有大量的空间位于2个 * 31位中大小的内存映射）。

Answer 4

到目前为止，我对接受的答案并不满意。所以我正在重试一个答案：

理论上可以在分期复杂的O（n）中对n个整数数组进行排序吗？

这个问题的答案取决于将执行排序算法的机器。如果你有一个随机存取机器，它可以正好在1位上运行，你可以对最多k位的整数进行radix sort，这已经被建议了。所以你最终的复杂性为O(kn)。
但是，如果您使用的字大小至少为k位（所有消费者计算机都是）的固定大小的字机，则您可以实现的最佳效果是O(n log n)。这是因为要么是log n < k，要么是先执行count sort，然后再用O (n log n)算法进行排序，这也会产生第一种情况。

如何尝试创建O（n）复杂度的最坏情况？

这是不可能的。已经有一个链接。证明的思想是，为了能够排序，如果任何要排序的元素大于或小于其他元素，则必须决定要排序的每个元素。通过使用传递性，这可以表示为决策树，其最多具有n节点和log n深度。所以如果你想要比Ω(n log n)更好的性能，这意味着从决策树中删除边缘。但是，如果决策树不完整，那么您如何确保您对某些元素a和b做出了正确的决定？

你可以不限制内存使用量创建这样的算法吗？

因此，从上面这是不可能的。因此，其余问题与此无关。