基本解法
第一步
以LSD為例，假設原來有一串數值如下所示：
73,22,93,43,55,14,28,65,39,81
首先根據個位數的數值，在走訪數值時将它們分配至編号0到9的桶子。
第二步
接下來将這些桶子中的數值重新串接起來，成為以下的數列：
81,22,73,93,43,14,55,65,28,39
接着再進行一次分配，這次是根據十位數來分配。
第三步
接下來将這些桶子中的數值重新串接起來，成為以下的數列：
14,22,28,39,43,55,65,73,81,93
這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。LSD的基數排序适用于位數小的數列，如果位數多的話，使用MSD的效率會比較好。
MSD的方式與LSD相反，是由高位數為基底開始進行分配，但在分配之後并不馬上合并回一個數組中，而是在每個“桶子”中建立“子桶”，将每個桶子中的數值按照下一數位的值分配到“子桶”中。在進行完最低位數的分配後再合并回單一的數組中。
效率分析
時間效率：設待排序列為n個記錄，d個關鍵碼，關鍵碼的取值範圍為radix，則進行鍊式基數排序的時間複雜度為O(d(n+radix))，其中，一趟分配時間複雜度為O(n)，一趟收集時間複雜度為O(radix)，共進行d趟分配和收集。空間效率：需要2*radix個指向隊列的輔助空間，以及用于靜态鍊表的n個指針。
實現方法
最高位優先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關鍵碼k1相等，再對各組按k2排序分成子組，之後，對後面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序後。再将各組連接起來，便得到一個有序序列。
最低位優先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重複，直到對k1排序後便得到一個有序序列。
實現原理
基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(Tabulation Machine)上的貢獻。它是這樣實現的：将所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。
然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後,數列就變成一個有序序列。
基數排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。
語言實現
C語言
#include
#include
testBS()
{
int a[]={2,343,342,1,123,43,4343,433,687,654,3};
int *a_p=a;
//計算數組長度
int size=sizeof(a)/sizeof(int);
//基數排序
bucketSort3(a_p,size);
//打印排序後結果
int i;
for(i=0;i
printf("%dn",a[i]);
}
int t;
scanf("%d",t);
}
//基數排序
void bucketSort3(int *p,int n)
{
//獲取數組中的最大數
int maxNum=findMaxNum(p,n);
//獲取最大數的位數，次數也是再分配的次數。
int loopTimes=getLoopTimes(maxNum);
int i;
//對每一位進行桶分配
for(i=1;i<=loopTimes;i++){
sort2(p,n,i);
}
}
//獲取數字的位數
int getLoopTimes(int num)
{
int count=1;
int temp=num/10;
while(temp!=0){
count++;
temp=temp/10;
}
return count;
}
//查詢數組中的最大數
int findMaxNum( int *p,int n)
{
int i;
int max=0;
for(i=0;i
if(*(p+i)>max){
max=*(p+i);
}
}
return max;
}
//将數字分配到各自的桶中，然後按照桶的順序輸出排序結果
void sort2(int *p,int n,int loop)
{
//建立一組桶此處的20是預設的根據實際數情況修改
int buckets={};
//求桶的index的除數
//如798個位桶index=(798/1)%10=8
//十位桶index=( 798/10 )%10=9
//百位桶index=( 798/100 )% 10=7
//tempNum為上式中的1、10、100
int tempNum=(int)pow(10,loop-1);
int i,j;
for( i=0;i
int row_index=(*(p+i)/tempNum)%10;
for(j=0;j<20;j++){
if(buckets[row_index][j]==NULL){
buckets[row_index][j]=*(p+i);
break;
}
}
}
//将桶中的數，倒回到原有數組中
int k=0;
for(i=0;i<10;i++){
for(j=0;j<20;j++){
if(buckets[i][j]!=NULL){
*(p+k)=buckets[i][j];
buckets[i][j]=NULL;
k++;
}
}
}
}
Java語言
public class RadixSort{
public static void sort(int[] number,int d){
int k=0;
int n=1;
int m=1;//控制鍵值排序依據在哪一位
int[][]temp=new int[number.length][number.length];
int[]order=new int[number.length];
while(m<=d){
for(int i=0;i
int lsd=((number[i]/n)%10);
temp[lsd][order[lsd]]=number[i];
order[lsd]++;
}
for(int i=0;i
if(order[i]!=0)
for(int j=0;j
number[k]=temp[i][j];
k++;
}
order[i]=0;
}
n*=10;
k=0;
m++;
}
}
public static void main(String[]args){
int[]data=
{73,22,93,43,55,14,28,65,39,81,33,100};
RadixSort.sort(data,10);
for(int i=0;i
System.out.print(data[i]+"");
}
}
pascal
type link=^node;
node=record
data:integer;
next:link;
end;
var i,j,l,m,k,n:integer;
a:array[1..100]of integer;
s:string;
q,head:array[0..9]of link;
p,p1:link;
begin
readln(n);
writeln('Enter data:');
for i:=1 to n do read(a[i]);
for i:=5 downto 1 do
begin
for j:=0to9 do
begin
new(head[j]);
head[j]^.next:=nil;
q[j]:=head[j]
end;
for j:=1to n do
begin
str(a[j],s);
for k:=1 to 5-length(s)do
s:='0'+s;
m:=ord(s[i])-48;
new(p);
p^.data:=a[j];
p^.next:=nil;
q[m]^.next:=p;
q[m]:=p;
end;
l:=0;
for j:=0to9 do
begin
p:=head[j];
while p^.next<>nil do
begin
l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data;
end;
end;
end;
writeln('Sorted data:');
for i:=1to n do
write(a[i]:6);
end.
c++
int maxbit(int data[],int n)//輔助函數，求數據的最大位數
{
int d=1;//保存最大的位數
int p=10;
for(int i=0;i
{
while(data[i]>=p)
{
p*=10;
++d;
}
}
return d;
}
{
int d=maxbit(data,n);
int*tmp=new int[n];
int*count=new int;//計數器
int i,j,k;
int radix=1;
for(i=1;i<=d;i++)//進行d次排序
{
for(j=0;j<10;j++)
count[j]=0;//每次分配前清空計數器
for(j=0;j
{
k=(data[j]/radix)%10;//統計每個桶中的記錄數
count[k]++;
}
for(j=1;j<10;j++)
count[j]=count[j-1]+count[j];//将tmp中的位置依次分配給每個桶
for(j=n-1;j>=0;j--)//将所有桶中記錄依次收集到tmp中
{
k=(data[j]/radix)%10;
t
}
for(j=0;j
data[j]=tmp[j];
radix=radix*10;
}
}
C#實現基數排序
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LearnSort
{
class Program
{
static void Main(string[] args)
{
int[]arr=CreateRandomArray(10);//産生随機數組
Print(arr);//輸出數組
RadixSort(ref arr);//排序
Print(arr);//輸出排序後的結果
Console.ReadKey();
}
public static void RadixSort(ref int[]arr)
{
int iMaxLength=GetMaxLength(arr);
RadixSort(ref arr,iMaxLength);
}
//排序
private static void RadixSort(ref int[] arr,int iMaxLength)
{
List list=new List();//存放每次排序後的元素
List[]listArr=new List;//十個桶
char currnetChar;//存放當前的字符,比如說某個元素123中的2
string currentItem;//存放當前的元素,比如說某個元素123
for(int i=0;i
listArr[i]=new List();
for(int i=0;i
{
foreach(int number in arr)//分桶
{
currentItem=number.ToString();//将當前元素轉化成字符串
try{currnetChar=currentItem[currentItem.Length-i-1];}//從個位向高位開始分桶
catch{listArr.Add(number);continue;}//如果發生異常，則将該數壓入listArr。比如說5 是沒有十位數的，執行上面的操作肯定會發生越界異常的，這正是期望的行為，我們認為5的十位數是0，所以将它壓入listArr的桶裡。
switch(currnetChar)//通過currnetChar的值，确定它壓人哪個桶中。
{
case'0':listArr.Add(number);break;
case'1':listArr.Add(number);break;
case'2':listArr.Add(number);break;
case'3':listArr.Add(number);break;
case'4':listArr.Add(number);break;
case'5':listArr.Add(number);break;
case'6':listArr.Add(number);break;
case'7':listArr.Add(number);break;
case'8':listArr.Add(number);break;
case'9':listArr.Add(number);break;
default:throw new Exception("unknow error");
}
}
for(int j=0;j
foreach(int number in listArr[j].ToArray())
{
list.Add(number);
listArr[j].Clear();//清空每個桶
}
arr=list.ToArray();//arr指向重新排列的元素
//Console.Write("{0}times:",i);
Print(arr);//輸出一次排列的結果
list.Clear();//清空list
}
}
//得到最大元素的位數
private static int GetMaxLength(int[]arr)
{
int iMaxNumber=Int32.MinValue;
foreach(int i in arr)//遍曆得到最大值
{
if(i>iMaxNumber)
iMaxNumber=i;
}
return iMaxNumber.ToString().Length;//這樣獲得最大元素的位數是不是有點投機取巧了...
}
//輸出數組元素
public static void Print(int[]arr)
{
foreach(int i in arr)
System.Console.Write(i.ToString()+'t');
System.Console.WriteLine();
}
//産生随機數組。随機數的範圍是0到1000。參數iLength指産生多少個随機數
public static int[]CreateRandomArray(int iLength)
{
int[] arr=new int[iLength];
Random random=new Random();
for (int i=0;i
arr[i]=random.Next(0,1001);
return arr;
}
}
}
AAuto
第一步
io.open();//打開控制台
/*
*-------------------------------------------------------
*基數排序
**------------------------------------------------------
*/
/*
第二步
基數排序從低位到高位進行，使得最後一次計數排序完成後，數組有序。
其原理在于對于待排序的數據，整體權重未知的情況下，
先按權重小的因子排序，然後按權重大的因子排序。
例如比較時間，先按日排序，再按月排序，最後按年排序，僅需排序三次。
但是如果先排序高位就沒這麼簡單了。
基數排序源于老式穿孔機，排序器每次隻能看到一個列，
很多教科書上的基數排序都是對數值排序，數值的大小是已知的，與老式穿孔機不同。
将數值按位拆分再排序，是無聊并自找麻煩的事。
算法的目的是找到最佳解決問題的方案，而不是把簡單的事搞的更複雜。
基數排序更适合用于對時間、字符串等這些整體權值未知的數據進行排序。
這時候基數排序的思想才能體現出來，例如字符串，如果從高位（第一位）往後排就很麻煩。
而反過來，先對影響力較小，排序排重因子較小的低位（最後一位）進行排序就非常簡單了。
這時候基數排序的思想就能體現出來。
又或者所有的數值都是以字符串形式存儲，就象穿孔機一樣，每次隻能對一列進行排序。
這時候基數排序也适用，例如：對{"193";"229";"233";"215"}進行排序
下面我們使用基數排序對字符串進行排序。
對每個位循環調用計數排序。
*/
第三步
//計數排序算法
radix_sort=function(array,maxlen){
//AAuto在字符串索引越界時，會返回0，這使基數排序的實現更加簡單。
//我們首先找出最大的排序長度，然後對于不足此長度的字符串，尾部都假定以0補齊。
//對于超出此長度的位在比較時忽略
if(!maxlen){
maxlen=0;
for(i=1;#array;1){
maxlen=math.max(maxlen,#array[i])
}
}
//else{
//最大排序長度也可以從參數中傳過來，這樣就不用遍曆所有字符串了
//}
第四步
//從字符串的最後一位開始，到第一位
for(pos=maxlen;1;-1){
//按當前位的字節碼計數排序
var array_sorted={};
var count={};
for(i=0;256){
count[i]=0;
}
var bytecode;
for(i=1;#array;1){
//如果pos大于字符串長度，AAuto會返回0，這使基數排序的實現更容易
bytecode=array[i][pos];
count[bytecode]++;//count[n]包含等于n的個數
}
第五步
//統計位置
for(i=1;256;1){
count[i]+=count[i-1];//count[i]包含小于等于i的個數
}
var n;
for(i=#array;1;-1){
n=array[i][pos]
array_sorted[count[n]]=array[i];
count[n]--;//防止相同的元素n再次出現，将計數減一
}
array=array_sorted;
}
return array
}
io.print("----------------")
io.print("基數排序(線性時間排序)")
io.print("----------------")
array={"AAuto is quicker and better,just try it!";"AAuto Quicker";"193";"229";"233";"215";"Hello
Word";"abc";"abcd";"xd";"adcd";"eddd";"ah";"ai";"aj";"ajkk"};
第六步
//排序
array=radix_sort(array)
第七步
//輸出結果
for(i=1;#array;1){
io.print(array[i])
}
execute("pause")//按任意鍵繼續
io.close();//關閉控制台
