基数排序是和其他的各类排序方式都不同的方式，之前的各类排序，如快速排序，堆排序，冒泡排序等等，都是通过关键字之间的比较和移动记录这两种操作来实现的，而基数排序不需要记录关键字之间的比较。所谓基数排序就是通过关键字排序的思想对单逻辑关键字进行的方法。

多关键字的排序：

 什么是多关键字的呢？

比如我们要比较一副扑克牌的，每一张牌的大小，那么除了点数的大小之外，还需要比较花色的大小，而花色和点数就是两个关键字。也就说，首先花色最大，其次才是点数大。

基数排序

 首先基数排序分为两种方式：

最高位优先法（MSD）：如上述扑克牌例子，有花色和点数，花色是最大的关键字，那么先把整副扑克牌用花色排序分为多个子序列，而每一个子序列中，又以点数来排序，如：1,2,3·····，J,Q,K···等等这样的基数排序就是 最高位排序。

最低位优先法（LSD）：合上述相反，比如：4个1在一起，4个2在一起 ······  按照大小排序为多个子序列，然后子序列中由按照花色来进行排序。

比如这组数据：

虽然是乱序，但是这些数的 个位 十位 百位 都是 0-9 这是个数字来组成的，那么我们就可以根据这是个数字来分为三个 子序列：
 先按个位来分为一个子序列：

 然后再按照基数的数据来进行回收，也就是从0开始到9来依次回收数据：

 回收出的这些数据就已经以个位的大小排序好了。

然后再按 十位 子序列来排序，也是按照数组的顺序来依次排序：

 然后再回收：

 然后再按百位来进行排序：

回收：

 这个时候我们发现，再次回收之后，数组和中的元素已经排序好了。

我们利用 c++ 当中的队列来实现每一个基数列的入数据和回收：

#include <stdio.h>
#include<iostream>
#include<queue>
using namespace std;

#define K 3
#define RADIX 10

//定义基数
//构造十个队列
queue<int> Q[RADIX];

// value = 278
// k  : 0
int GetKey(int value, int k)
{
	int key = 0;
	while (k >= 0)
	{
		key = value % 10;
		value /= 10;
		k--;
	}
}

//分发数据
// k 表示每一次使用什么位来进行分发的 0 给 1 十位 ····
void Distribute(int arr[], int left, int right, int k)
{
	for (int i = left; i < right; i++)
	{
		int key = GetKey(arr[i], k);
		Q[key].push(arr[i]);
	}
}

//回收数据
void Collect(int arr[])
{
	int k = 0;
	for (int i = 0; i < RADIX; i++)
	{
		while (!Q[i].empty())
		{
			arr[k++] = Q[i].front();
			Q[i].pop();
		}
	}
}

void RadixSort(int arr[], int left, int right)
{
	for (int i = 0; i < K; i++)
	{
		//分发数据
		Distribute(arr, left, right, i);

		//回收数据
		Collect(arr);
	}
}

void main()
{
	int array[] = { 278,109,63,930,589,184,505,269,8,83 };
	int n = sizeof(array) / sizeof(array[0]);

	for (int i = 0; i < n; i++)
	{
		printf("%d", array[i]);
	}
	printf("\n");

	//基数排序

	for (int i = 0; i < n; i++)
	{
		printf("%d", array[i]);
	}
	printf("\n");
}