首页 / 算法 / DS基数排序

DS基数排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了DS基数排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2288字，纯文字阅读大概需要4分钟。

内容图文

题目描述

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

输入

测试次数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>
usingnamespace 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=newint[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;
    }
    return0;
}

原文：https://www.cnblogs.com/SZU-DS-wys/p/12183133.html

内容总结

以上是互联网集市为您收集整理的DS基数排序全部内容，希望文章能够帮你解决DS基数排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1236062.html

来源：【匿名】