radix_sort

淩亂°似流年 2021-10-01 07:48 320阅读 0赞

**基数排序：**

**这里还要注意负数的输入，解决方法想了两种：一是把最小数找出来，然后每个数都加一次。**

**　　　　　　　　　　　　　　　　　　　　二是将正负数分开排序。**

1 #include<Stdio.h>
     2 void radix_sort(int a[],int n); 3 int main(){ 4     int a[100],n; 5     int i; 6     scanf("%d",&n); 7     for( i=0; i<n; i++) 8         scanf("%d",&a[i]); 9 radix_sort(a,n); 10     for( i=0; i<n; i++){ 11         printf("%d ",a[i]); 12 } 13     printf("\n"); 14     return 0; 15 } 16 
    17 void radix_sort(int a[],int n){ 18    int count_a[10],sort_a[100]; 19    int i,j,k=1; 20    int radix=10; 21    while(1){ 22         for( i=0; i<radix; i++){ 23             count_a[i] = 0; 24 } 25         for( i=0; i<n; i++){ 26             count_a[(a[i]/k)%radix]++;//(a[i]/k)%radix求出最低位的数值 27 } 28         if(n == count_a[0])//结束条件是所有的数的余10都等于0时 29             break; 30         for( i=1; i<10; i++){ 31             count_a[i] = count_a[i]+count_a[i-1]; 32 } 33         for( i=n-1; i>=0; i--){ 34             sort_a[count_a[(a[i]/k)%radix]-1] = a[i];//从末尾开始读数有利于数的稳定性
    35             count_a[(a[i]/k)%radix]--; 36 } 37         for( i=0; i<n; i++){
         //更新排序
    38             a[i] = sort_a[i]; 39 } 40         k *= radix; 41         for( i=0; i<n; i++){ 42             printf("%d ",sort_a[i]); 43 } 44         printf("\n"); 45         printf("k=%d\n",k); 46 } 47 
    48 }

![924293-20170326201927674-286705965.png][]

转载于:https://www.cnblogs.com/lpa1027/p/6623892.html

[924293-20170326201927674-286705965.png]: /images/20210724/c5af7d2e35a14c29b0e1e108e38911ae.png