在O(n)时间排序？

Question

我坚持这个问题(2周).任何想法如何处理它？

令L是n个不同整数的列表,假设L的x的元素在[1,750]的范围内.设计线性排序算法以排序L的元素

我已经尝试过插入排序.但我不确定我的做法是否正确:

Construct an array of bits. Initialize them to zero.
Read the input, for each value you see set the respective bit in the array to 1.
Scan the array, for each bit set, output the respective value.

复杂度=> O(2n)= O(n)

Answer 1

尝试Radix排序 - http://en.wikipedia.org/wiki/Radix_sort

如果将750视为常量,则将其排序为O(n).

基于比较的排序不能排序小于O(nlogn),但如果值的数量由D限制,则可以在O(D*n)或O(n)中排序(如果您将D视为常量).

Answer 2

我不会给出完整的方法，但这里有一个应该有所帮助的观察。

您已经知道这些数字严格在该范围内[1, 750]。在线性时间内算出每个数字有多少并不是特别困难。

一旦获得这些信息，如何取回排序后的列表（同样是在线性时间内）？

至于您给出的方法，这不是插入排序，它更像是桶排序或计数排序（这就是我试图暗示的）。我看到的一件事是，如果数组可以包含重复项，您的方法将不起作用。如果你被告知没有，那么你就可以走了。否则，您将需要修改必须处理的内容。