排序算法---基数排序 拼搏现实的明天。 2022-03-11 06:22 263阅读 0赞 基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序 比如这样一个数列排序: 342 58 576 356, 以下描述演示了具体的排序过程(红色字体表示正在排序的数位) 第一次排序(个位): 3 4 2 5 7 6 3 5 6 0 5 8 第二次排序(十位): 3 4 2 3 5 6 0 5 8 5 7 6 第三次排序(百位): 0 5 8 3 4 2 3 5 6 5 7 6 结果: 58 342 356 576 基本排序思想已搞定,可实现起来还是会有些许困难。 先看C语言代码: #include <stdio.h> int lengthOfNnm(int n){ if(n>=0&&n<10) { return 1; }else{ int m = 0; while(n>=1){ n=n/10; m++; } return m; } } int getKey(int n,int index){//获取第index 位上的数值 switch (index) { case 1: n=n%10; break; case 2: n=(n%100)/10; break; case 3: n=(n%1000)/100; break; //。。。此次测试 3个足矣 default:n=-1; break; } return n; } void sort(int v[] ,int index){ int temp[8]; int counts[10]; for(int i = 0;i<10;i++){//初始化操作 counts[i] = 0; } for(int i = 0;i<8;i++){//对 indx 位计数 counts[ getKey(v[i],index) ] ++; } for(int i = 1;i<10;i++){//累加操作 counts[i]+= counts[i-1]; } for(int i = 8-1 ;i>=0;i--){//从左端开始复制记录 int j = getKey(v[i],index) ; temp[ counts[j] - 1 ] = v[i]; counts[j]--; } for(int i = 0;i<8;i++){ v[i] = temp[i]; } } int main(int argc, char *argv[]) { int a[]={ 659,248,175,198,886,23,237,560 }; int max = a[0]; for(int i = 0;i<8;i++){ printf("%d ",a[i]); if(a[i] > max){ max = a[i]; } } printf("\n"); int times = lengthOfNnm(max); for(int i = 1;i<=times;i++){//最大数为几位则循环几次 sort(a,i); } for(int i = 0;i<8;i++){ printf("%d ",a[i]); } printf("\n"); return 0; }
还没有评论,来说两句吧...