多关键字和桶排与基排

《多关键字和桶排与基排》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多关键字及桶排与基排多关键字及桶排与基排.txt爱情就像脚上的鞋，只有失去的时候才知道赤脚走路是什么滋味骗人有风险，说慌要谨慎。不要爱上年纪小的男人，他会把你当成爱情学校，一旦学徒圆满，便会义无反顾地离开你。多关键字排序在一些问题中，本身就涉及多个关键字，例如CCC2010的“买电脑”中综合评分和品牌名都是关键字。而在排序课题中，把唯一的关键字分离成多个关键字，常常能加速排序过程。1低关键字优先排序（基数排序、桶排序）在基数排序（桶排序）的算法中，既有拆分又有合并，下面以10个3进制数为例，演示线性表与子表的转换过程。观察这十个数据，最多3位数，所以排序共进行3轮。第一轮先按

2、顺序用最低位（个位）分3个子表：初始排列1022111122010101200211201个位0子表22010200个位1子表2111110111201个位2子表1022以0、1、2的顺序依次把3个子表连接成一个序列：2201020021111101112011022对上一行连成的序列再次拆分，依次以第二位数字分为3个子表：第二位0：2001012011022第二位1：1011111第二位2：22021按第一轮方式连接为：2001012011022101111122021按最高位拆分为3个子表最高位0：2101121最高位1：101102111最高位2：200201220再按

3、第一轮的连接方式得到最后结果：21011211011021112002012202基数排序的链描述自然数X的每一位数字都可以看成一个独立的关键字，下面的代码从低到高，分别根据每一个十进制位分成子链，再顺次连接，重复若干轮后完成排序。#include#includeusingnamespacestd;ifstreamcin("px.in");ofstreamcout("px.out");structnode{intdata;node*next;node(){next=0;}}t[10],*w[10],s,*e,*p;intmain(){intn

4、,i,x,m=0,j,r=1,y=1,tt=clock();e=&s;cin>>n;for(i=1;i<=n;i++){p=newnode;cin>>p->data;e->next=p;e=p;m=max(p->data,m);}m=int(log10(m)+1);for(i=1;i<=m;i++){p=s.next;for(j=0;j<10;j++){t[j].next=0;w[j]=&t[j];}for(j=0;jdata/y%10;//X为当前的一位关键字w[x]->next=p;w[x]=p;p=p->next;}e=&s;for(j=0;j

5、<10;j++)if(t[j].next>0){e->next=t[j].next;e=w[j];}y*=10;e->next=0;}e=s.next;for(i=1;i<=n;i++){cout<data<<'';e=e->next;}cout<<(clock()-tt)/1000.0<#includeusingnamespacestd;unsignedlonglongintx[10000001],y[10000001];intc[10000001];intmai

6、n(){freopen("jspx.in","r",stdin);freopen("jspx.out","w",stdout);intn,l,i,w,p,q,t;unsignedlonglongintm=0;t=clock();scanf("%d",&n);scanf("%d",&l);//输入关键字的二进制位数p=int(pow(2.0,l)+0.5)-1;q=p;unsignedlonglongint*a=x,*b=y;for(i=0;i<=n-1;i++){scanf("%lld",&a[i]);if(a[i]>m)m=a[i];}for(w=0;(m>>w)>0;w+

7、=l){for(i=0;i<=n-1;i++)c[(a[i]&q)>>w]++;for(i=1;i<=p;i++)c[i]+=c[i-1];for(i=n-1;i>=0;i--)b[--c[(a[i]&q)>>w]]=a[i];memset(c,0,sizeof(c));swap(a,b);q<<=l;}for(i=0;i<=n-1;i++)printf("%lld",a[i]);t=clock()-t;printf("%d",t);return0;}对小于2^32的自然数排序，可以用65536