基数排序

简介(直接复制别人的)

基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。

我自己的理解步骤

①先把这一堆数的最大位数找出来。

②找出最大的位数之后，设置最外层的循环，循环步数就是这个最大位数，然后设置一个【位数除以计数器】，最初始是1，每次循环之后乘以10

③然后开始内部的编写，每次循环都是同样的步骤，只是进入桶的位数变化了罢了

④把每个数的相应的位数入桶，用的是bk[(num[i]/s)%10]++直接入桶

⑤然后把每个桶的数按照顺序加起来好顺序输出

⑥再用bk的编号把临时数组填充出桶的数(这里如果从0-n-1的话，bk的编号要减一，我目前还不清楚为什么，但是不减一肯定会出错）

⑦更新数组再进行下一次循环

⑧循环完成按照要出输出即可

我的代码（算法完全借鉴）

#include <iostream>
#include <cstring>
using namespace std;
int bk[10];
int num[1000010];
int fnum[1000010];
int n;
int find(int *a)
{
	int num=0;
	int s=1;
	for(int i=0;i<n;i++)
	{
		while(a[i]>=s)
		{
			s*=10;
			num++; 
		}
	} 
	return num;	
} 
main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	while(cin>>n)
	{
		memset(num,0,sizeof(num));
		for(int i=0;i<n;i++)
		cin>>num[i];
		int k=find(num);
		int s=1;
		for(int i=0;i<k;i++)
		{
			memset(bk,0,sizeof(bk));
			for(int j=0;j<n;j++)
			bk[(num[j]/s)%10]++;
			for(int j=1;j<=9;j++)
			bk[j]+=bk[j-1];
			for(int j=n-1;j>=0;j--)
			{
				fnum[bk[(num[j]/s)%10]-1]=num[j];
				bk[(num[j]/s)%10]--;
			}
			for(int j=0;j<n;j++)
			num[j]=fnum[j];
			s*=10;
		}
		for(int i=0;i<n;i++)
		cout<<num[i]<<" ";
		cout<<endl;
	}
}