排序为O阵列（n）的运行时间 [英] Sorting Array in O(n) run time

问题描述

如果你没有内存方面的任何限制是否有任何算法给定的阵列，重复在O（n）的排序？

If you do not have any constraints regarding memory is there any algorithm to sort a given array with duplicates in O(n) ?

推荐答案

这要看情况。如果你能束缚你的输入以某种方式同时具有下限和上限（和最大precision /值长度），那么你可以使用的基数排序这是 O（N）。同样，桶排序可以有 O（N）的复杂性最好的情况，但降低到为O（n ^ 2）坏的投入。

It depends. If you can bound your input in some way with both a lower and upper bound (and maximum precision/value length), then you can use a Radix Sort which is O(n). Similarly, Bucket Sort can have O(n) complexity in the best case, but degrades to O(n^2) for bad inputs.

在一般情况下，但是，如果不能约束你的输入，需要使用一个基于比较的排序，它可以证明为O（n log n）的是最佳的。

In general, however, if you cannot bound your input and need to use a comparison based sort, it can be proven that O(n log n) is optimal.

在分拣固定precision整数或浮点数（通常高达64位），该值有效地为界，而基数排序是可能的。

When sorting fixed precision integers or floating point numbers (normally up to 64-bits), the values are effectively bounded, and radix sort is possible.

即使值的最大比特长度为界，在更长的比特长度，较大的常数。实际上，如果有n值进行排序，并且每个值可以具有的长度或precision高达m位时，算法的复杂度是O（nm）的

Even if the maximum bit-length of the values is bounded, the longer the bit-length, the larger the constant. In effect, if there are n-values to sort, and each value can have a length or precision up to m bits, the algorithmic complexity is O(nm).

这篇关于排序为O阵列（n）的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！