基数排序！

一 基数排序的基本思想

不同于之前的八大排序算法，那些排序算法都是依靠比较或者交换来入手的，因此对上述算法进行优化，也是从这两个方面入手的。

基数排序：最基本的两个思想是发数据和收数据

但是基数排序就没有这方面的考虑了

他有两种做法，但是两种做法都会依赖一个数据结构：队列，先进先出的性质。

1 LSD-》从最低位置开始排序

首先我们需要选定基数，所谓的基数就是比较的数字，以十进制数字为例子，由于每一个位置上的数字都是0——9，因此基数的选择就是0——9.

从最低位置排序：依次比较数列中的每一个数字的最低位置，并且把它放在对应的保存基数的队列中，如果排升序，那么这些队列就小到大进行排序。如果有相同的，就入栈。

等把上述的数列中的数字都放在了下面的数列组成的数组中的时候，发数据就完成了。那么接下来我们需要收数据了，从前往后依次出队列。这样子我们第一次排序得到的数据就是个位按照升序排好的数据了

这是第一趟排序

完了之后我们排第二趟数据的时候是根据十位的数字进行排序的，也是按照上述的思想。等到将数组中所有的都排完之后，这个数列就完成了排序

如何确定所有的都排完了呢？这个数组中最多位数的一个数字就是这个数组需要排列的趟数。如果有些数字位数不同，就在比较小的数字前面补上0就行了

2 MSD-》从最高位进行排序

了解了LSD之后其实MSD也是好理解的，只不过排序的顺序从最低位到最高位变成了从最高位到最低位置

二 图解

第一次排序 个位数字被排好了

 

动图：（网上找的）

三 代码：

#define _CRT_SECURE_NO_WARNINGS 1 
#include<iostream>
#include<queue>
#include<assert.h>
using namespace std;
 
#define Radix 10
#define K 3
 
queue<int>q[Radix];
 
void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		cout<<a[i]<<" ";
	}
}
int Getkey(int num,int k)
{
	
	int ret = 0;
	while (k >= 0)
	{
		k--;
		ret = num % 10;
		num /= 10;
	}
	return ret;
}
void Send(int* a, int n,int k)
{
	assert(a);
	
		for (int i = 0; i < n; i++)
		{
				int key = Getkey(a[i], k);
				q[key].push(a[i]);
		}
	
 
}
 
void Collection(int* a, int n, int k)
{
	        assert(a);
			int i = 0;
			for (int k = 0; k < Radix; k++)
			{
				while (!q[k].empty())
				{
					a[i++] = q[k].front();
					q[k].pop();
				}
			}
}
void RadixSort(int* a, int n)
{
	    assert(a);
		for (int k = 0; k < K; k++)
		{
			Send(a, n, k);
			Collection(a, n, k);
		}
}
int main()
{
	int arr[] = { 278,109,63,930,589,184,505,269,8,83 };
	int sz = sizeof(arr) / sizeof(arr[0]);
 
	
	cout << "基数排序前：";
	Print(arr, sz);
	cout << endl;
 
	RadixSort(arr, sz);
 
	cout << "基数排序后：";
	Print(arr, sz);
	cout << endl;
 
	return 0;
}