通常，您需要进行非比较排序才能以O（n）的时间进行排序，但是前提是您已经获得了某些信息。有三种“主要”非比较排序算法可供选择：计数排序，基数排序和存储桶排序。

如果您知道输入是小整数，请使用计数排序。通过维基百科，“计数排序仅适用于键的变化不明显大于项数的情况。”
http://en.wikipedia.org/wiki/Counting_sort

如果您要排序的所有数字都具有相同数量的整数，则可以使用基数排序。例如：211、311、122。

桶分类似乎是您的最佳选择。您的方法听起来不错，但是您不需要从1到2n的数组，每个数字都有一个索引。在存储桶排序中，您可以使用1到20之间的数组，并且每个元素中都有类似链表的内容。因此，如果放置数字109，则它可能对应于索引10。