c - C中排序算法的错误(基数排序的变化)

我正在学习C语言，我在网上读了一些排序算法。
我试着做我自己的排序算法，它看起来有点像基数排序。Radix sort on Wikipedia。下面是一个程序与我的排序算法。

#include <stdio.h>
#include <stdlib.h>

/* prints all elements of an array of n length */
void printArray(int *arr, int n){
  if (n < 0){
    return;
  } else if (n == 0){
    printf("()\n");
  } else {
    int i;
    printf("(%d", arr[0]);
    for(i=1; i<n; i++){
      printf(", %d", arr[i]);
    }
    printf(")\n");
  }
}

/* safe replacement for malloc. */
void *safeMalloc(int size) {
  void *ptr = malloc(size);
  if (ptr == NULL) {
    printf("\nError: memory allocation failed....abort\n");
    printf("\nNot enough space for %d int numbers\n", size);
    exit(-1);
  }
  return ptr;
}

/* safe replacement for realloc. */
int *resizeArray(int *arr, int newSize){
  int *ptr = realloc(arr, newSize*sizeof(int));
  if (ptr == NULL) {
    printf("\nError: memory allocation failed....abort\n");
    exit(-1);
  }
  return ptr;
}

/* check if array is sorted */
void checkArray(int length, int *a){
  int i;
  for(i=0; i<length-i; i++){
    if (a[i] > a[i+1]){
      printArray(a, length);
      printf("Error in: %d\n", i);
      return;
    }
  }
}

/*///////////////////////////////////////////////////
 * /////////////// SORTING ALGORITHM ////////////////
 * ////////////////////////////////////////////////*/
void sort(int length, int a[], int digits){
  /* base case */
  if ((length <= 1) || (digits == 0)){
    return;
  }
  /* recursive case */
  /* declare variables */
  int i, j, digit, idx = 0, sum = 0;
  int *copy[10], lengthCopy[10];
  for(i=0; i<10; i++){
    lengthCopy[i] = 0;
    copy[i] = safeMalloc(sizeof(int));
  }
  for(i=0; i<length; i++){
    /* get the n'th digit. Example: a[i]=12345 and digits=100 --> digit=3 */
    digit = (a[i]/digits)%10;

    lengthCopy[digit]++;
    if (lengthCopy[digit] > 1){
      resizeArray(copy[digit], lengthCopy[digit]);
    }
    copy[digit][lengthCopy[digit]-1] = i;
  }
  /* Get the values */
  for(i=0; i<10; i++){
    for(j=0; j<lengthCopy[i]; j++){
      copy[i][j] = a[copy[i][j]];
    }
  }
  /* fill in the elements of copy in the original array */
  for(i=0; i<10; i++){
    for(j=0; j<lengthCopy[i]; j++){
      a[idx] = copy[i][j];
      idx++;
    }
    /* copy[i] is no longer necessary, so free it */
    free(copy[i]);
  }

  for(i=0; i<10; i++){
    /* call recursive function */
    sort(lengthCopy[i], &a[sum], digits/10);
    sum += lengthCopy[i];
  }
}

int getMax(int length, int a[]){
  int i, max = 1;
  for(i=0; i<length; i++){
    while(a[i] > max*10){
      max *= 10;
    }
  }
  return max;
}

int main(int argc, char *argv[]){
  int i, *a, length=20;
  a = safeMalloc(length*sizeof(int));
  for(i=0; i<length; i++){
    a[i] = rand()%100;
  }
  sort(length, a, getMax(length, a));
  checkArray(length, a);
  printArray(a, length);
  free(a);
  return 0;
}

现在，当我尝试我的程序时，非常奇怪的事情是，当我在主函数中有一个分段错误：int length=1000，但如果我输入了：int length=20则不会；
我不知道这个错误是从哪里来的有人能帮我吗？
提前谢谢你，
帕特里克
对不起，我的英语不是第一种语言；）

最佳答案

正如鲁本斯建议的那样，使用valgrind会直接导致错误：

==7369== Invalid write of size 4
==7369==    at 0x400991: sort (/tmp/t.c:77)
==7369==    by 0x400BF2: main (/tmp/t.c:118)
==7369==  Address 0x4de46e4 is 0 bytes after a block of size 4 free'd
==7369==    at 0x402FD9E: realloc (valgrind/coregrind/m_replacemalloc/vg_replace_malloc.c:661)
==7369==    by 0x4007AA: resizeArray (/tmp/t.c:33)
==7369==    by 0x40096A: sort (/tmp/t.c:75)
==7369==    by 0x400BF2: main (/tmp/t.c:118)

在realloc之后，不能访问旧数组，必须使用新数组。resizeArray函数返回新数组是有原因的；忽略该返回值是个错误。
现在，你的程序仍然“工作”尽管有那个错误，但只是偶然的。堆腐败虫子就是这样的。

关于c - C中排序算法的错误(基数排序的变化)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26699738/