首页 > 代码库 > 【Sort】RadixSort基数排序
【Sort】RadixSort基数排序
太晚了,明天有时间在写算法思路,先贴代码
1 #include <iostream> 2 3 using std::cout; 4 5 void radixsort(int *a,int num); 6 int loop(int *a,int num); 7 int main() 8 { 9 int a[10]={3,2,1,4,7,6,5,8,9,0}; 10 radixsort(a,10); 11 for(int i=0;i<10;i++) 12 cout<<a[i]<<" "; 13 return 0; 14 } 15 int loop(int *a,int num) 16 { 17 int maxnum=0,i; 18 for(i=0;i<num;i++) 19 if(a[i]>maxnum) 20 maxnum=a[i]; 21 i=1; 22 maxnum/=10; 23 while(maxnum>10) 24 { 25 i++; 26 maxnum/=10; 27 } 28 return i; 29 } 30 void radixsort(int *a,int num) 31 { 32 int looptime=loop(a,num); 33 int *counts=new int[10]; 34 int *tmp=new int[num]; 35 int i,j,k,rs=1; 36 for(j=0;j<looptime;j++) 37 { 38 for(i=0;i<10;i++) 39 counts[i]=0; 40 for(i=0;i<num;i++) 41 { 42 k=(a[i]/rs)%10; 43 counts[k]++; 44 } 45 for(i=1;i<10;i++) 46 counts[i]+=counts[i-1];//确定范围 47 for(i=0;i<num;i++) 48 { 49 k=(a[i]/rs)%10; 50 tmp[counts[k]-1]=a[i]; 51 counts[k]--; 52 } 53 for(i=0;i<num;i++) 54 a[i]=tmp[i]; 55 rs*=10; 56 } 57 delete[]tmp; 58 delete[]counts; 59 }
【Sort】RadixSort基数排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。