基数排序与基数排序是两种非比较型排序。


计数排序：


//************计数排序*********//先最大-最小+1得到开辟空间数，开辟空间str，在遍历原数据arr在str相应位置计数，再遍历str将值写到原arr中//适用在密集型数据，无重复最优可转化为位图//时间复杂度O(N),空间复杂度O(最大数-最小数+1)//设数组元素非负voidCountingSort(int*a,size_tsize){size_ti=0,j=0;intmax=a[0],min=a[0];size_tspace=0;for(i=1;i<size;i++){if(max<a[i]){max=a[i];}if(min>a[i]){min=a[i];}}space=max-min+1;//str相应位置记录a中个数据的次数int*str=newint[space]();for(i=0;i<size;i++){str[a[i]-min]++;}//写回原数组a中for(i=0,j=0;i<space,j<size;i++){while(str[i]-->0){a[j++]=i+min;}}}


基数排序：

//***********基数排序**************//采用先排低位，在排高位//时间复杂度O(位数)空间复杂度O(N)//设数组元素非负size_tGetMaxRadix(int*a,size_tsize)//取数组中最大值的位数{assert(a!=NULL);size_ti=0;size_tnum=0;size_tcount=1;for(i=0;i<size;i++){while(a[i]/count>0){count*=10;num++;}}returnnum;}voidLSDSort(int*a,size_tsize){assert(a!=NULL);intMaxRadix=GetMaxRadix(a,size);intcount[10]={0};//同一位上数字相等的数字个数intstart[10]={0};//按位上数字所对应的起始位置int*bucket=newint[size];size_ti=0;intnum=1;while(MaxRadix--){memset(count,0,sizeof(int)*10);//count清零//按位排序for(i=0;i<size;i++)//count[]{count[a[i]/num%10]++;//取某一位上数字，在count相应位置++}for(i=0;i<10;i++)//start[]{//跳过0因为起始位置一定为0if(i==0){start[i]=0;}elsestart[i]=start[i-1]+count[i-1];}//写到bucket[]中for(i=0;i<size;i++){bucket[start[a[i]/num%10]++]=a[i];}//写回a[]中for(i=0;i<size;i++){a[i]=bucket[i];}num*=10;}}


test:

inta5[]={5,24,35,54,72,81,75,6,9,56,114,30,5};inta6[]={5,24,35,54,72,81,75,6,9,56,114,30,5};