是否有时间复杂度为 O(N) 的排序算法? [英] Is there a sorting algorithm available which has time complexity of O(N)?

问题描述

大多数排序算法的复杂度为 O(NN) 或 O(NlogN) 以实现结果.然而，有些算法的复杂度为 O(N)特定的输入集.我想知道是否有可用的排序算法在所有情况下都具有 O(N) 的复杂度.

Most of the sorting algorithm have a complexity of O(NN) or O(NlogN) to achieve the result.However, there are algorithms which has a complexity of O(N) for specific set of input.I want to know if there is a sorting algorithm available that has a complexity of O(N) in all cases.

推荐答案

如果你只能比较(检查两个项目是否为 <,>,==)被排序的值，那么你不能比 O 做得更好(n log(n)).这是为数不多的经过验证的算法下界之一.证明并不太复杂(查看维基百科上的比较排序以了解详细信息)，但时间足够在这里不再重复.

If you can only compare (check if two item are <,>,==) the values being sorted, then you can't do better than O(n log(n)). It's one of the few proven lower bounds on algorithms out there. The proof isn't too complex (check comparison sort on wikipedia for the details), but it's long enough not to repeat here.

如果你可以做比较以外的事情，你就有更多的灵活性.如果您有数字，请查看桶排序(一种基数排序)，它使 O(n) 排序成为可能.

If you can do things other than compare you have more flexibility. If you have numbers, you check out bucket sort (a type of radix sort), it makes O(n) sorting possible.

这篇关于是否有时间复杂度为 O(N) 的排序算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！