基数排序有时也被称作卡片排序，也是一种时间复杂度为O(n)的排序。为了给一个序列排序，基数排序需要大约相当的辅助空间(通常使用队列)，可见空间复杂度为O(n)。 假设有一个无序序列含有n 个整数，整数的基数是k，最大有d 位(例如： 对于十进制整数而言， k = 10，可能的值是 0, 1, 2, ..., 8, 9，在 32 位系统上 d≤10，在64 位系统上 d≤20)，则基数排序的时间复杂度为O(d(n+k)) = O(n)。当对整数排序时，使用10进制虽然比较容易理解，但是速度慢(因为为了得到各位数字需要做除法和取模等操作)，为了尽可能的减小时间开销，通常使用2 的指数次幂进制(例如：2, 4, 8, ..., 2r，r为2进制的幂)，这样可以借助位移运算减小耗费CPU 指令数，提升运行速度。对于b位(在PC机上， b通常为32或64)的整数而言， d = b/r， k = 2r，于是时间复杂度O(d(n+k)) = O(b/r(n+2r))，理论上，当b/r(n+2r)最小时，速度应该最快。

以一个随机整数序列为例，基数排序的过程见下表。

178 207 982 510 477 295 963 095 274 614 810 579 700 618 301 766

待排序序序列

510 810 700 301 982 963 274 614 295 095 766 207 477 178 618 579 

个位排序结果

700 301 207 510 810 614 618 963 766 274 477 178 579 982 295 095

十位排序结果

095 178 207 274 295 301 477 510 579 614 618 700 766 810 963 982

百位排序结果

以上是以基数为10进行排序的例子，实现时应该使用2的指数为基数，从而避免除法和取模而采用位运算来获取较快的处理速度。
以下基数排序使用256个队列，对int类型的序列从小到大排序，但是还是比快排慢一些，其实用多少队列都比不上快排快。即使不用动态队列，都用静态队列，还是比快排慢。根本原因在于这种基数排序的思想跟现代CPU架构背道而驰，非常的不CPU cache friendly.从一个队列换到另一队列，然后再换回来，这种换来换去的机制导致CPU cache line不停的被重新填充，毕竟内存的延迟和访问速度比CPU cache要慢的多，大部分时间都耗费在这里。结果这种看上去很理想的所谓的O(n)算法，只能徒有虚名。相信这些是那些纯搞理论的算法专家和数学家永远都想不明白的！其实还不止基数排序如此，类似行为的计数排序和桶排序也快不起来，尽管它们的时间复杂度都是一色的O(n)。

 1 #include <queue> // use standard queue
 2 // non-portable implementation for LSD radix sort, for type int, 32 bit system
 3 template <typename ForwardIterator>
 4 void radix_sort(ForwardIterator first, ForwardIterator last)
 5 {
 6   // R: radix, K: k base, M: mask, B: ? bit system
 7   const unsigned R = 8, K = 1 << R, M = K - 1, B = 32;
 8   std::queue<int> q[K];
 9   for(unsigned i = 0; i < B; i += R)
10   {
11     for(ForwardIterator dit = first; dit != last; ++dit)
12     q[(*dit >> i) & M].push(*dit);
13     ForwardIterator cit = first;
14     for(unsigned j = 0; j < K; ++j)
15     while(!q[j].empty())
16     {
17       *cit++ = q[j].front();
18       q[j].pop();
19     }
20   }
21 }