基本思想：
將待排數據中的每組關鍵字依次進行桶分配。
具體示例：
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個盒子里。這樣，操作員就可逐個地把它們收集起來。其中第一個位置穿孔的放在最上面，第二個位置穿孔的其次，等等。
對于一個位數有限的十進制數，我們可以把它看作一個多元組，從高位到低位關鍵字重要程度依次遞減。可以使用基數排序對一些位數有限的十進制數排序。
新聞熱點
疑難解答
圖片精選
