一、算法原理

基數排序算法又稱桶排序，是一種原理簡單實現相對麻煩一點的算法。基數排序屬于穩定排序法，適用于數值比較大的數據之間的排序。
常見的內部排序算法中都使用到了元素之間的比較大小，而基數排序算法不涉及元素之間的比較，而是根據基數將數據存放到相應的“桶”里，經過多趟這樣的存放過程，也就是一個漸進排序過程，就可以實現對一組散亂數據進行排序。總趟數是數組中位數最多的那個元素的位數。其實讀到這里，大家是不是有一種很熟悉的感覺，沒錯，這跟創建Hash（散列）表的原理類似。
第一趟排序的基數是1，即從“個位”上的數字開始，將根據每一個元素的“個位”數字將該元素存到到與數字相同的“桶里”，得到一次排序結果。第二趟排序的基數是10，在第一趟排序的基礎上，根據“百位”上的數字將元素重新放入相應的“桶”里，得到新一輪的排序。依次類推，直到所有元素中的最高位已經處理完畢，結束整個排序過程。從這里就可以看出基數排序就是一個漸進的排序過程。
需要注意的是使用靜態數組進行基數排序時，并不是真的把元素放入“桶”里，而是把某個“位”上數字相同的元素個數存放入“桶”里。是不是有點上當的趕腳，其實這樣做，無他，只是為了方便排序而已。而且“桶”的個數是10，這是因為阿拉伯數字就是10個，分別是0,1,2,3,4,5,6,7,8,9。每個桶中的值就是相同“位”上數字相同的元素個數。啰嗦了這么多，也不知讀者看懂了木有，還是拿具體的例子說話吧，這樣更清晰。

下面以具體的例子演示一下基數排序的基本原理。
Demo：設有數據如下：

準備工作：
1）創建10個桶。
2）求出最大的元素12608（也就是這里涉及到了比較大小，此外再無，童叟無欺），計算出其總位數是5，用于控制排序的總趟數。其實每一趟就是針對一個“位”上的元素進行排序。
3）為了方便求每一個元素不同“位”上的元素，設定一個基數，其取值分別是1,10,100，…，即第一趟排序時，值為1，用于求“個位”上的數字；第二趟排序時值為10，用于求“十位”上的數字，第三趟排序時，值為100，用于求“百位”上的數字，等等。
第一趟排序：
基數是1，根據“個位”數字將元素放入對應的桶里。

之后將根據“桶”號大小，將“桶”里元素按照桶號的大小順序放入數組，得到如下結果：

第二趟排序：
基數是10，在第一趟排序的基礎上，根據“十位”數字將元素放入對應的桶里。

之后再將“桶”里元素按照桶號的大小順序放入數組，結果如下：

第三趟排序：
基數是100，在第二趟排序的基礎上，根據“百位”數字將元素放入對應的桶里。

之后再將“桶”里元素按照桶號的大小順序放入數組，結果如下：

第四趟排序：
基數是1000，在第三趟排序的基礎上，根據“千位”數字將元素放入對應的桶里。

之后再將“桶”里元素按照桶號的大小順序放入數組，結果如下：

第五趟排序：
基數是10000，在第四趟排序的基礎上，根據“萬位”數字將元素放入對應的桶里。

之后再將“桶”里元素按照桶號的大小順序放入數組，結果如下：

至此，基數排序結束。
在上述演示過程中，可以發現，在每一趟的排序中，每個“桶里”存放的元素個數都可能不同，如果直接把元素存放到桶里，就給算法的具體實現帶來了很大麻煩。為了解決這個麻煩，“桶”里不再存儲元素，而是改為存儲元素的個數，同時引入一個新的數組作為緩存，存儲每一趟的排序結果，之后再把排序結果存儲到原數組中，這樣就可以方便的實現桶排序了。
例如第一趟排序中的“桶”里數據就行可以修改為存放元素的個數，具體如下：

再做元素值的累加得到：

這樣就可以得到原數組中每一個元素在排序后數組中的下標。有童鞋會突然發現有的桶里存放了多個元素，如何解決其位置呢？這個其實很簡單，“桶”的元素值每用一次，就執行減1操作，就可以解決了。例如用bucket表示桶數組，bucket[4]中實際存放了兩個元素，對應的原數組的元素分別是14和8844。bucket[4]的值是5，表示其中存放的元素在新數組的下標值是5，即當取走元素8844時，8844在新數組的下標是5，然后bucket[4]執行減1操作，其值就是4了，再取走元素14時，元素14在新數組的下標就是4了。

二、基數排序算法

記待排序的數組為data，元素個數為length。
**Step1：**創建桶bucket，有10個元素，初始值均為0，用于存放某“位”數字與桶元素編號相同的數組元素的個數;
求出數組的最大元素，同時算出其總位數count;
定義基數變量，例如base，其初始值為1；
分配緩存buff，其元素個數與原數組元素個數相同。
**Step 2：**數組的每個元素data[i]除以base之后對10求余數，記為k，執行bucket[k]++；轉下一步；
**Step 3：**重新計算“桶”bucket中的每一個元素的值，讓其等于前面元素之和，即
bucket[k+1] += bucket[k]
這樣就可以計算出原數組 data中的每一個元素在新數組buff中的位置。（這一步是不是很神奇）；轉下一步；
**Step 4：**根據“桶”里的元素，也就是位置序號，將原數組data中的元素依次存放到buff中，再將buff中元素依次存入data中；轉下一步；
**Step 5：**base *= 10，count–，判斷count > 0， 如果為真，則轉step2，否則結束排序。
三、基數排序的C程序
1. 基數排序代碼

//利用桶排序算法對數組data進行從小到大排序 
void RadixSort( int data[], int length )
{
	int i, k, maxVal, count, base;
	int bucket[10] = { 0 };
	int *buff = new int[ length ];
	//求數組中的最大元素 
	maxVal = data[0];
	for( i = 1; i < length; i++ )
	{
		if( data[i] > maxVal )
		{
			maxVal = data[i];
		}
	}
	//printf( "maxVal = %d\n", maxVal );
	//計算最大元素的位數 
	count = 0;
	while( maxVal > 0 )
	{
		count++;
		maxVal /= 10;
	}
	//printf( "count = %d\n", count );
	base = 1;
	for( k = 1; k <= count; k++ )
	{
		//求每一個元素的 base位上的數字，對應的桶元素做累加 
		for( i = 0; i < length; i++  ) 
		{
			bucket[ ( data[i] / base ) % 10 ]++;
		}
		//重新計算桶元素的值，每一個元素都是其前面元素之和
		//如此操作，可以得到每一個桶中的元素在排序之后的位置下標 
		for( i = 1; i < 10; i++ ) 
		{
			bucket[i] += bucket[i-1];
		}
		//根據桶元素的值，將data中的元素重新排位存入buff中
		for( i = length-1; i >= 0; i-- ) 
		{
			buff[ bucket[ ( data[i] / base ) % 10 ] - 1 ] = data[i];
			bucket[ ( data[i] / base ) % 10 ]--;
		}
		//將buff中元素對位存放到data中
		for( i = 0; i < length; i++ ) 
		{
			data[i] = buff[i];
		}
		//清空桶，即讓桶里元素歸0 
		for( i = 0; i < 10; i++ ) 
		{
			bucket[i] = 0;
		}
		//base的值乘以10,之后進入下一趟排序 
		base *= 10;
	}
	delete[] buff;
}

2.完成測試代碼

#include"stdio.h" 
void RadixSort( int data[], int length );

int main()
{
	int data[] = { 255, 12608, 31, 14, 21, 121, 268, 8844 };
	int length = 8;
	printf( " Initial Array    : " );
	for( int i = 0; i < length; i++ )
	{
		printf( "%8d", data[i] );
	}
	printf( "\n" );
	RadixSort( data, length );
	return 0;
}
//利用桶排序算法對數組data進行從小到大排序 
void RadixSort( int data[], int length )
{
	int i, k, maxVal, count, base;
	int bucket[10] = { 0 };
	int *buff = new int[ length ];
	//求數組中的最大元素 
	maxVal = data[0];
	for( i = 1; i < length; i++ )
	{
		if( data[i] > maxVal )
		{
			maxVal = data[i];
		}
	}
	//printf( "maxVal = %d\n", maxVal );
	//計算最大元素的位數 
	count = 0;
	while( maxVal > 0 )
	{
		count++;
		maxVal /= 10;
	}
	//printf( "count = %d\n", count );
	base = 1;
	for( k = 1; k <= count; k++ )
	{
		//求每一個元素的 base位上的數字，對應的桶元素做累加 
		for( i = 0; i < length; i++  ) 
		{
			bucket[ ( data[i] / base ) % 10 ]++;
		}
		//重新計算桶元素的值，每一個元素都是其前面元素之和
		//如此操作，可以得到每一個桶中的元素在排序之后的位置下標 
		for( i = 1; i < 10; i++ ) 
		{
			bucket[i] += bucket[i-1];
		}
		//根據桶元素的值，將data中的元素重新排位存入buff中
		for( i = length-1; i >= 0; i-- ) 
		{
			buff[ bucket[ ( data[i] / base ) % 10 ] - 1 ] = data[i];
			bucket[ ( data[i] / base ) % 10 ]--;
		}
		//將buff中元素對位存放到data中
		for( i = 0; i < length; i++ ) 
		{
			data[i] = buff[i];
		}
		//清空桶，即讓桶里元素歸0 
		for( i = 0; i < 10; i++ ) 
		{
			bucket[i] = 0;
		}
		//base的值乘以10,之后進入下一趟排序 
		base *= 10;
		
		//
		//向屏幕輸出每一趟排序結果，便于觀察 
		printf( " No. %d time sort : ", k );
		for( i = 0; i < length; i++ ) 
		{
			printf( "%8d", data[i] );
		}
		printf( "\n" );
		//
	}
	delete[] buff;
}

3.測試運行結果：