n-數字字典順序

答:首先，在O(dn)=O(n)的時間內，將這些整數統壹轉換成N元表示。這樣每個整數不超過d位。如果把每壹位看作壹個字段，那麽這些整數的排序基就相當於這些字段的字典序(從高到低)。因此，整個排序可以通過直接應用基數排序算法來實現。上述基數排序過程包括d桶排序，累計耗時為d o (dn) = o (dn) = o (n)。