我被这个问题困扰了（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)
尝试基数排序 -http://en.wikipedia.org/wiki/Radix_sort http://en.wikipedia.org/wiki/Radix_sort
如果将给定的 750 视为常数，则排序时间为 O(n)。
基于比较的排序无法在小于 O(nlogn) 的时间内进行排序，但如果值的数量受 D 限制，则可以在 O(D*n) 或 O(n)（如果将 D 视为常数）中进行排序。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
