基数排序

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int a[120],tmpa[120]; //记录节点
 6 int tong[20],poi[20];  //表示桶和每个位数是i的节点的数量
 7 int n;
 8 int MAX(int x,int y)
 9 {
10     return x>y?x:y;
11 }
12 int dig(int x)
13 {
14     int num=0;
15     while(x) x/=10,num++;
16     return num;
17 }
18 void Print()
19 {
20     for(int i=0;i<n;i++) cout<<a[i]<<" ";
21     cout<<endl;
22 }
23 void tong_paixu()
24 {
25     int i,j,mx,x,base=1;
26     cin>>n;
27     for(i=0;i<n;i++) cin>>a[i],mx=(i==0?a[0]:MAX(mx,a[i]));
28     int num=dig(mx);
29     while(num--)
30     {
31         memset(tong,0,sizeof(tong)); //每次记录位数是x的数字的数量
32         for(i=0;i<n;i++)
33         {
34             x=a[i]/base%10;
35             tong[x]++;
36         }
37         
38         memset(poi,0,sizeof(poi));
39         for(i=1;i<10;i++) poi[i]=poi[i-1]+tong[i-1]; //记录每个位数的起始位置
40         
41         memset(tmpa,0,sizeof(tmpa));
42         for(i=0;i<n;i++)
43         {
44             x=a[i]/base%10;
45             tmpa[poi[x]++]=a[i]; //记录每个位置的数字。
46         }
47         
48         for(i=0;i<n;i++) a[i]=tmpa[i]; //将tmpa的值赋值给a
49         base*=10;
50     }
51     Print();
52 }
53 
54 int main(void)
55 {
56     tong_paixu();
57     return 0;
58 }