基本思想：

將待排數(shù)據(jù)中的每組關(guān)鍵字依次進(jìn)行桶分配。
具體示例：

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

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

然后從最低位個(gè)位開(kāi)始(從最次關(guān)鍵字開(kāi)始)，對(duì)所有數(shù)據(jù)的k1關(guān)鍵字進(jìn)行桶分配(因?yàn)椋總€(gè)數(shù)字都是 0-9的，因此桶大小為10)，再依次輸出桶中的數(shù)據(jù)得到下面的序列。

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

再對(duì)上面的序列接著進(jìn)行針對(duì)k2的桶分配，輸出序列為：

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

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

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

效率分析：

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

但是，對(duì)比桶排序，基數(shù)排序每次需要的桶的數(shù)量并不多。而且基數(shù)排序幾乎不需要任何“比較”操作，而桶排序在桶相對(duì)較少的情況下，桶內(nèi)多個(gè)數(shù)據(jù)必須進(jìn)行基于比較操作的排序。因此，在實(shí)際應(yīng)用中，基數(shù)排序的應(yīng)用范圍更加廣泛。

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

第二種方式是從最低有效關(guān)鍵字開(kāi)始排序，稱(chēng)為L(zhǎng)SD(Least Significant Dight)排序。首先對(duì)所有的數(shù)據(jù)按照次要關(guān)鍵字排序，然后對(duì)所有的數(shù)據(jù)按照首要關(guān)鍵字排序。要注意的是，使用的排序算法必須是穩(wěn)定的，否則就會(huì)取消前一次排序的結(jié)果。由于不需要分堆對(duì)每堆單獨(dú)排序，LSD方法往往比MSD簡(jiǎn)單而開(kāi)銷(xiāo)小。下文介紹的方法全部是基于LSD的。

通常，基數(shù)排序要用到計(jì)數(shù)排序或者桶排序。使用計(jì)數(shù)排序時(shí)，需要的是Order數(shù)組。使用桶排序時(shí)，可以用鏈表的方法直接求出排序后的順序。下面是一段用桶排序?qū)ΧM基數(shù)排序的程序：

#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中的每個(gè)元素按照的范圍值放入對(duì)應(yīng)桶中    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; //把桶中每個(gè)元素取出    delete Bucket[k];  }}void RadixSort(data *A,int N,int K){  for (int j=1;j>=0;j--) //從低優(yōu)先到高優(yōu)先 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;}

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

對(duì)于一個(gè)位數(shù)有限的十進(jìn)制數(shù)，我們可以把它看作一個(gè)多元組，從高位到低位關(guān)鍵字重要程度依次遞減。可以使用基數(shù)排序?qū)σ恍┪粩?shù)有限的十進(jìn)制數(shù)排序。