如果我有一个大小为n的列表,我知道列表中的数字将介于1和2n之间,我将如何解决它,最坏的情况是O(n)？
我在想,如果它在1和n之间,我可以只取数字并用数字的数值交换它 - 1然后如果有任何重复就不会排序.
我想到了一个类似的方法,列表的数字在1到2n之间,但我似乎无法弄明白.有什么帮助吗？
在您的情况下,计数排序可以在 O(n)中运行.看看维基百科的定义
count sort是一种根据小整数键对对象集合进行排序的算法; 也就是说,它是一个整数排序算法.它通过计算具有每个不同键值的对象的数量来操作,并对这些计数使用算术来确定输出序列中每个键值的位置.它的运行时间与项目数量和最大和最小键值之间的差异是线性的,因此它仅适用于键的变化不大于项目数的情况下的直接使用
http://en.wikipedia.org/wiki/Counting_sort
小智 5
您通常需要在 O(n) 时间内进行非比较排序，但前提是您已经获得了某些信息。有三种“主要”非比较排序算法可供选择：计数排序、基数排序和桶排序。
如果您知道输入是小整数，请使用计数排序。根据维基百科，“计数排序仅适用于键的变化不明显大于项目数的情况。” http://en.wikipedia.org/wiki/Counting_sort
如果要排序的所有数字都具有相同数量的整数，则可以使用基数排序。例如：211、311、122。
桶排序可能是您的最佳选择。你的方法听起来不错，但你不需要一个从 1 到 2n 的数组，每个数字都有一个索引。在桶排序中，您可以拥有一个从 1 到 20 的数组，并且在每个元素中都有一个类似于链表的东西。因此，如果您放置数字 109，它可能对应于索引 10。