基数排序属于"分配式排序"，又称"桶子法"，它是一种借助多关键字的思想对单逻辑关键字进行排序的算法。

基数排序有两种方法：

假设初始序列为:Array{3,1,13,24,36,23,21,44,25,19}

任何一个整数各个位上的基数都可以0~9来表示，我们不妨把0~9视为10个桶。

我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：Array[0] = 3，个位数上是3，将这个数存入编号为3的桶中。

分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。

这时，得到的序列就是个位数上呈递增趋势的序列。 

按照个位数排序： {1, 21, 3, 13, 23, 24, 44, 25, 36, 19}。

接下来，对十位数也按照这种方法进行排序。

这是得到序列：{1，3, 13，19，21，23，24，25，36, 44}。

也可以从下图中看出基数排序的过程：

下面是代码实现：

int getMaxBit(int *arr, int length) //辅助函数，求数据的最大位数
{
	int bitNum = 1; //保存最大的位数
	int p = 10;
	for (int i = 0; i < length; ++i)
	{
		while (arr[i] >= p)
		{
			p *= 10;
			++bitNum;
		}
	}
	return bitNum;
}

void RadixSort(int *arr, int length)//基数排序
{
	int bitNum = getMaxBit(arr, length);
	int *tmp = new int[length];
	int *count = new int[10];//计数器
	int i, j, k;
	int radix = 1;
	for (i = 1; i <= bitNum; i++)//进行bitNum次排序
	{
		for (j = 0; j < 10; j++)
			count[j] = 0;//每次分配前清空计数器
		for (j = 0; j < length; j++)
		{
			k = (arr[j] / radix) % 10;//统计每个桶中的记录数
			count[k]++;
		}
		for (j = 1; j < 10; j++)
			count[j] = count[j - 1] + count[j];
		// 这里要从右向左扫描，保证排序稳定性
		for (j = length - 1; j >= 0; j--)//将所有桶中记录依次收集到tmp中
		{
			k = (arr[j] / radix) % 10;
			tmp[count[k] - 1] = arr[j];
			count[k]--;
		}
		for (j = 0; j < length; j++)
			arr[j] = tmp[j];
		radix *= 10;
	}
	delete[] tmp;
	delete[] count;
}

基数排序的性能

如果有什么问题，乐意和大家讨论。

另外，其他排序算法，可以参考我的另外一篇博客

“排序算法及并向析”：http://blog.csdn.net/secyb/article/details/51319391。