基本思想：

將待排數據中的每組關鍵字依次進行桶分配。
具體示例：

278、109、063、930、589、184、505、269、008、083

我們將每個數值的個位，十位，百位分成三個關鍵字： 278 -> k1(個位)=8，k2(十位)=7，k3=(百位)=2。

然后從最低位個位開始(從最次關鍵字開始)，對所有數據的k1關鍵字進行桶分配(因為，每個數字都是 0-9的，因此桶大小為10)，再依次輸出桶中的數據得到下面的序列。

930、063、083、184、505、278、008、109、589、269

再對上面的序列接著進行針對k2的桶分配，輸出序列為：

505、008、109、930、063、269、278、083、184、589

最后針對k3的桶分配，輸出序列為：

008、063、083、109、184、269、278、505、589、930

效率分析：

基數排序的性能比桶排序要略差。每一次關鍵字的桶分配都需要O(N)的時間復雜度，而且分配之后得到新的關鍵字序列又需要O(N)的時間復雜度。假如待排數據可以分為d個關鍵字，則基數排序的時間復雜度將是O(d*2N) ，當然d要遠遠小于N，因此基本上還是線性級別的。基數排序的空間復雜度為O(N+M)，其中M為桶的數量。一般來說N>>M，因此額外空間需要大概N個左右。

但是，對比桶排序，基數排序每次需要的桶的數量并不多。而且基數排序幾乎不需要任何“比較”操作，而桶排序在桶相對較少的情況下，桶內多個數據必須進行基于比較操作的排序。因此，在實際應用中，基數排序的應用范圍更加廣泛。

舉例：
假設我們有一些二元組(a,b)，要對它們進行以a為首要關鍵字，b的次要關鍵字的排序。我們可以先把它們先按照首要關鍵字排序，分成首要關鍵字相同的若干堆。然后，在按照次要關鍵值分別對每一堆進行單獨排序。最后再把這些堆串連到一起，使首要關鍵字較小的一堆排在上面。按這種方式的基數排序稱為MSD(Most Significant Dight)排序。

第二種方式是從最低有效關鍵字開始排序，稱為LSD(Least Significant Dight)排序。首先對所有的數據按照次要關鍵字排序，然后對所有的數據按照首要關鍵字排序。要注意的是，使用的排序算法必須是穩定的，否則就會取消前一次排序的結果。由于不需要分堆對每堆單獨排序，LSD方法往往比MSD簡單而開銷小。下文介紹的方法全部是基于LSD的。

通常，基數排序要用到計數排序或者桶排序。使用計數排序時，需要的是Order數組。使用桶排序時，可以用鏈表的方法直接求出排序后的順序。下面是一段用桶排序對二元組基數排序的程序：

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>using namespace std;struct data{  int key[2];};struct linklist{  linklist *next;  data value;  linklist(data v,linklist *n):value(v),next(n){}  ~linklist() {if (next) delete next;}};void BucketSort(data *A,int N,int K,int y){  linklist *Bucket[101],*p;//建立桶  int i,j,k,M;  M=K/100+1;  memset(Bucket,0,sizeof(Bucket));  for (i=1;i<=N;i++)  {    k=A[i].key[y]/M; //把A中的每個元素按照的范圍值放入對應桶中    Bucket[k]=new linklist(A[i],Bucket[k]);  }  for (k=j=0;k<=100;k++)  {    for (p=Bucket[k];p;p=p->next) j++;    for (p=Bucket[k],i=1;p;p=p->next,i++)      A[j-i+1]=p->value; //把桶中每個元素取出    delete Bucket[k];  }}void RadixSort(data *A,int N,int K){  for (int j=1;j>=0;j--) //從低優先到高優先 LSD    BucketSort(A,N,K,j);}int main(){  int N=100,K=1000,i;  data *A=new data[N+1];  for (i=1;i<=N;i++)  {    A[i].key[0]=rand()%K+1;    A[i].key[1]=rand()%K+1;  }  RadixSort(A,N,K);  for (i=1;i<=N;i++)    printf("(%d,%d) ",A[i].key[0],A[i].key[1]);  printf("/n");  return 0;}

基數排序是一種用在老式穿卡機上的算法。一張卡片有80列，每列可在12個位置中的任一處穿孔。排序器可被機械地"程序化"以檢查每一迭卡片中的某一列，再根據穿孔的位置將它們分放12個盒子里。這樣，操作員就可逐個地把它們收集起來。其中第一個位置穿孔的放在最上面，第二個位置穿孔的其次，等等。

對于一個位數有限的十進制數，我們可以把它看作一個多元組，從高位到低位關鍵字重要程度依次遞減?？梢允褂没鶖蹬判驅σ恍┪粩涤邢薜氖M制數排序。