排序算法之基数排序

在学习基数排序之前，我们首先要了解基数排序的概念，首先我们要明白相比于其他排序，基数排序中并没有选择与交换的步骤，这就使它与归并和快排等排序算法之间有了较大的区别。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

这里我们利用扑克牌举例，在生活中，我们常常会接触扑克牌游戏，在扑克牌中，有两种不同的属性，其一为扑克牌的种花色，其二就是扑克牌的大小，我们可以利用这两种属性来对扑克牌进行一个比较对比，由此我们可以将类似的思想利用到排序算法中个，这就是我们今天要讲的基数排序。

首先我们对这样的一组数据进行排序

int arr[] = { 278,109,63,930,658,184,505,269,8,83 };

首先我们将个位与其相应的数组对齐并回收各个数字

 第一次排序之后的数组为以上形式，接下来在对十位进行对比排序归类：（位数不足自动补0） 

接下来为最后一次：
 

 最后就得到了我们想要达到的结果，接下来哦我们就用代码来具体实现一下思想：

在这里我们用C++来实现代码：

首先定义头文件：

#include
#include
using namespace std;
#include
#define K 3
#define RADIX 9

 在这里因为我们要使用队列的思想（先进先出），将下来我们写一个取出各位数的代码：

int Getkey(int value, int k)//帮助分解各个位数
{
	int key = 0;
	while (k >= 0)
	{
		key = value % 10;
		value /= 10;
		k--;
	}
	return key;
}

接着我们在写两个代码分别为分发代码与回收代码：

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();
		}
	}
}
//回收所有数字并覆盖原数组

完整代码如下：

#include
#include
using namespace std;
#include
#define K 3
#define RADIX 10
//定义基数
queue Q[RADIX];
int Getkey(int value, int k)//帮助分解各个位数
{
	int key = 0;
	while (k >= 0)
	{
		key = value % 10;
		value /= 10;
		k--;
	}
	return key;
}
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);
	}
}
int main()
{
	int arr[] = { 278,109,63,930,658,184,505,269,8,83 };
	int n = sizeof(arr) / sizeof(arr[0]);
	//基数排序
	RadixSort(arr, 0, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}