个人兴趣图片集网站建设,wordpress怎么做下载文件,网页页面建设方案,北京网站设计精选刻前几天沈阳现场赛遇到了一道题#xff0c;其中的一部分不能用快排#xff0c;只能用基数排序#xff0c;当时不会写基数排序#xff0c;gg#xff0c;从银滑到了铜。。。。真是血的教训#xff0c;现在再来回顾一下。
输入n个整数#xff0c;最大的整数不超过6位#…前几天沈阳现场赛遇到了一道题其中的一部分不能用快排只能用基数排序当时不会写基数排序gg从银滑到了铜。。。。真是血的教训现在再来回顾一下。
输入n个整数最大的整数不超过6位这些数存在a数组里用基数排序的方法给这些数排序。
定义下面几个数组
bs[10]:基数排序的桶
rk[10]:rk[i]表示编号为i的数当前位的排名大小。
y[maxn]:y[i]表示低位排好序的结果
x[maxn]:x[i]表示低位再算上当前位排好序的结果
代码: int T 6;
for(int i 0;i n;i) y[i] i;
for(int t 0;t T;t){
for(int i 0;i n;i) rk[i] at(a[i],t); //rk[i]表示第i号数字的第t位上的数值也就是当前要考虑位的数值。
for(int i 0;i 10;i) bs[i] 0; //bs[i]初始化位0
for(int i 0;i n;i) bs[rk[y[i]]] ; //下面一句
for(int i 1;i 10;i) bs[i] bs[i-1]; //这两句做完后,第t位上i的数字共有bs[i]个
for(int i n-1;i 0;--i) x[--bs[rk[y[i]]]] y[i]; //倒着循环是关键这样可以使得高位相同时低位大的在后面。高位不同时直接以高位为准进行赋值。
swap(x,y);
}
