c - 基数排序的实现

Question

我一直在尝试用 C 语言编写基数排序算法。当我使用基数 10 运行代码时，它对所有输入都可以正常工作，但是，使用基数 16 时，它只能正确排序前 10 个元素。此外，对于任何其他基地，它都不起作用。我想实现一个适用于任何基础的实现。

这是到目前为止的代码，您能发现任何问题吗？

#include <stdio.h>
#include <stdlib.h>
int size=32;
int getMax(int arr[], int n) {
    int mx = arr[0];
    int i;
    for (i = 1; i < n; i++)
       if (arr[i] > mx)
           mx = arr[i];
    return mx;
}

void countSort(int arr[], int n, int exp, int base) {
   int output[n]; 
   int i;
   int count[base];
   memset(count,0,sizeof count);   
   for (i=0;i<n;i++)
       count[(arr[i]/exp)%base]++;
   for (i=1;i<base;i++)
       count[i]=count[i]+count[i-1];
   for (i=n-1;i>=0;i--) {
      output[count[ (arr[i]/exp)%base ]-1]=arr[i];
      count[ (arr[i]/exp)%base ]--;
   }
   for (i=0;i<n;i++)
       arr[i]=output[i];
}

void radixsort(int arr[],int n,int base) {
  int exp;
  int m=getMax(arr,n);
  for (exp=1;m/exp>0;exp=exp*10)
    countSort(arr,n,exp,base);
}

int main(int argc,char *argv[]) {    
  int num,i=0,j,n,m;
  int *arr,*newarr=NULL;
  FILE *fp1;
  FILE *fp2;
  int base=atoi(argv[1]);
  fp1=fopen(argv[2],"r");
  if (fp1 == NULL) {
     printf("Warning:File does not exists;please enter valid file name");
     exit(0);
  }
  fp2=fopen(argv[3],"w");
  if (fp2 == NULL) {
       printf("Warning:File does not exists");
       exit(0);
  }
  arr= malloc(sizeof(int)*size);
  fprintf(fp2,"before sorting:");
  while(fscanf(fp1,"%d",&num)==1) {
    if(i<size) {
       arr[i]=num;
       i++;
       fprintf(fp2,"%d ",num);
       n=i;
    } else {
       newarr = malloc(sizeof(int)*2*size);
       for(m=0;m<size;m++) {
           newarr[m]=arr[m];
       }
       free(arr);
       size=size*2;
       arr=&newarr[0];
    }
  }
  radixsort(arr,n,base);
  fprintf(fp2,"\nAfter Sorting:");
  for (j=0;j<n;j++)
     fprintf(fp2,"%d ",arr[j]);

  fclose(fp1);
  fclose(fp2);
  return 0;
}

Answer 1

看起来for (exp=1;m/exp>0;exp=exp*10)是问题所在。我认为您需要使用 base 而不是 10。

编辑:我尝试编译并运行此代码，但无法使其工作，即使对于基数 10 也是如此。