基數(shù)排序有時(shí)也被稱作卡片排序，也是一種時(shí)間復(fù)雜度為O(n)的排序。為了給一個(gè)序列排序，基數(shù)排序需要大約相當(dāng)?shù)妮o助空間(通常使用隊(duì)列)，可見空間復(fù)雜度為O(n)。 假設(shè)有一個(gè)無序序列含有n 個(gè)整數(shù)，整數(shù)的基數(shù)是k，最大有d 位(例如： 對于十進(jìn)制整數(shù)而言， k = 10，可能的值是 0, 1, 2, ..., 8, 9，在 32 位系統(tǒng)上 d≤10，在64 位系統(tǒng)上 d≤20)，則基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+k)) = O(n)。當(dāng)對整數(shù)排序時(shí)，使用10進(jìn)制雖然比較容易理解，但是速度慢(因?yàn)闉榱说玫礁魑粩?shù)字需要做除法和取模等操作)，為了盡可能的減小時(shí)間開銷，通常使用2 的指數(shù)次冪進(jìn)制(例如：2, 4, 8, ..., 2r，r為2進(jìn)制的冪)，這樣可以借助位移運(yùn)算減小耗費(fèi)CPU 指令數(shù)，提升運(yùn)行速度。對于b位(在PC機(jī)上， b通常為32或64)的整數(shù)而言， d = b/r， k = 2r，于是時(shí)間復(fù)雜度O(d(n+k)) = O(b/r(n+2r))，理論上，當(dāng)b/r(n+2r)最小時(shí)，速度應(yīng)該最快。

以一個(gè)隨機(jī)整數(shù)序列為例，基數(shù)排序的過程見下表。

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 

個(gè)位排序結(jié)果

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

十位排序結(jié)果

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

百位排序結(jié)果

以上是以基數(shù)為10進(jìn)行排序的例子，實(shí)現(xiàn)時(shí)應(yīng)該使用2的指數(shù)為基數(shù)，從而避免除法和取模而采用位運(yùn)算來獲取較快的處理速度。
以下基數(shù)排序使用256個(gè)隊(duì)列，對int類型的序列從小到大排序，但是還是比快排慢一些，其實(shí)用多少隊(duì)列都比不上快排快。即使不用動態(tài)隊(duì)列，都用靜態(tài)隊(duì)列，還是比快排慢。根本原因在于這種基數(shù)排序的思想跟現(xiàn)代CPU架構(gòu)背道而馳，非常的不CPU cache friendly.從一個(gè)隊(duì)列換到另一隊(duì)列，然后再換回來，這種換來換去的機(jī)制導(dǎo)致CPU cache line不停的被重新填充，畢竟內(nèi)存的延遲和訪問速度比CPU cache要慢的多，大部分時(shí)間都耗費(fèi)在這里。結(jié)果這種看上去很理想的所謂的O(n)算法，只能徒有虛名。相信這些是那些純搞理論的算法專家和數(shù)學(xué)家永遠(yuǎn)都想不明白的！其實(shí)還不止基數(shù)排序如此，類似行為的計(jì)數(shù)排序和桶排序也快不起來，盡管它們的時(shí)間復(fù)雜度都是一色的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 }