与常见的比较排序算法(如快速排序、归并排序)存在本质不同,基数排序不基于元素间的直接比较,而是依赖于元素的位权信息来排序。这使得基数排序能够在某些情况下实现线性时间复杂度,理论上达到
\(O(kn)\),其中
\(k\) 是位数,
\(n\) 是元素个数。即复杂度取决于值域规模。