题目描述

给定一组数据，对其进行基数升序排序。

输入

测试次数t

每组测试数据一行：数字个数n，后跟n个数字（整数）

 

输出

对每组测试数据，输出每趟分配、收集的结果。若分配中该位没有数字，输出NULL。具体输出格式见样例。每组测试数据间以空行分隔。

 

样例输入

2 10 278 109 63 930 589 184 505 269 8 83 6 57 0 93 19 18 99

样例输出

0:->930->^ 1:NULL 2:NULL 3:->63->83->^ 4:->184->^ 5:->505->^ 6:NULL 7:NULL 8:->278->8->^ 9:->109->589->269->^ 930 63 83 184 505 278 8 109 589 269 0:->505->8->109->^ 1:NULL 2:NULL 3:->930->^ 4:NULL 5:NULL 6:->63->269->^ 7:->278->^ 8:->83->184->589->^ 9:NULL 505 8 109 930 63 269 278 83 184 589 0:->8->63->83->^ 1:->109->184->^ 2:->269->278->^ 3:NULL 4:NULL 5:->505->589->^ 6:NULL 7:NULL 8:NULL 9:->930->^ 8 63 83 109 184 269 278 505 589 930 0:->0->^ 1:NULL 2:NULL 3:->93->^ 4:NULL 5:NULL 6:NULL 7:->57->^ 8:->18->^ 9:->19->99->^ 0 93 57 18 19 99 0:->0->^ 1:->18->19->^ 2:NULL 3:NULL 4:NULL 5:->57->^ 6:NULL 7:NULL 8:NULL 9:->93->99->^ 0 18 19 57 93 99

提示

#include<iostream>
#include<queue>
using namespace std;
#define Radix 10
int keysize;
void printindex(queue<int>b[Radix])
{
    queue<int>B[Radix];
    for(int i=0;i<Radix;i++)
        B[i]=b[i];
    for(int i=0;i<Radix;i++)
    {
        cout<<i<<":";
        if(B[i].empty())
        {
            cout<<"NULL"<<endl;
        }
        else
        {
            cout<<"->";
            while(!B[i].empty())
            {
                cout<<B[i].front()<<"->";
                B[i].pop();
            }
            cout<<"^"<<endl;
        }
    }
}
void printa(int *a,int n)
{
    for(int i=0;i<n;i++)
    {
        if(i!=n-1)
            cout<<a[i]<<" ";
        else
            cout<<a[i]<<endl;
    }
}
 
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        keysize=0;
        int n;
        cin>>n;
        int *a=new int[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        int maxx=a[0];
        for(int i=0;i<n;i++)
        {
            if(a[i]>maxx)
                maxx=a[i];
        }
        while(maxx!=0)
        {
            keysize++;
            maxx/=10;
        }
        queue<int>B[Radix];
        int count=0;
        int div=1;
        while(count<keysize)
        {
            for(int i=0;i<n;i++)
            {
                int s=(a[i]/div)%10;
                B[s].push(a[i]);
            }
            printindex(B);
            int k=0;
            for(int j=0;j<Radix;j++)
            {
                while(!B[j].empty())
                {
                    a[k]=B[j].front();
                    B[j].pop();
                    k++;
                }
            }
            count++;
            div*=10;
            printa(a,n);
        }
        delete []a;
        if(T)
            cout<<endl;
    }
    return 0;
}