大多数排序算法的复杂度为 O(NN) 或 O(NlogN) 来实现结果。但是，对于特定的输入集，有些算法的复杂度为 O(N)。我想知道是否有一种排序算法在所有情况下都具有 O(N) 的复杂度。
如果您只能比较（检查两个项目是否为 、==）正在排序的值，那么您不能做得比 O(n log(n)) 更好。它是现有算法中为数不多的经过验证的下限之一。证明并不太复杂（查看维基百科上的比较排序以了解详细信息），但它足够长，此处不再重复。
如果你能做一些除了比较之外的事情，你就会有更大的灵活性。如果你有数字，你可以查看桶排序（一种基数排序），它使 O(n) 排序成为可能。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
