c - 每次执行计数排序都会使我的程序崩溃，无法发现 malloc/free 错误

Question

我已经被困在这个问题上一段时间了，绝对找不到解决我的问题的方法。我在 C 中遵循 Sedgewick 的算法来实现计数排序，但由于某种原因，我的 b 数组没有正确读取我的输入数组的值，并且在尝试释放时也会使程序崩溃。任何帮助将不胜感激。

void count_sort(int* a, int l, int r, int M)
{
    int i, j;
    int* cnt = (int*)malloc(M * sizeof(int));
    if (!cnt) {
        printf("Returned NULL PTR for cnt\n");
        exit(1);
    }
    int* b = (int*)malloc((r + 1) * sizeof(int));
    if (!b) {
        printf("Returned NULL PTR for b\n");
        exit(1);
    }
    printf("\n\n\n");

    for (j = 0; j < M; ++j)
        cnt[j] = 0;
    for (i = l; i <= r; ++i)
        cnt[a[i]]++;
    for (i = 1; i < M; ++i)
        cnt[i] += cnt[i - 1];

    /*
free(b);
free(cnt);
printf("Able to free here\n");
exit(0);
*/

    for (i = l; i <= r; ++i) {
        b[cnt[a[i]]] = a[i];
        printf("%d\n", b[cnt[a[i]]]);
        ++cnt[a[i]];
    }

    /*
free(b);
free(cnt);
printf("Able to free here\n");
exit(0);
*/
    for (i = l; i <= r; ++i)
        a[i] = b[i - l];

    free(cnt);
    free(b);
}

int is_sort(int* a, int N)
{
    int i;
    for (i = 0; i < N - 1; ++i) {
        if (a[i + 1] < a[i]) {
            printf("%d %d\t%d %d\n", i, a[i], i + 1, a[i + 1]);
            return 0;
        }
    }
    return 1;
}

int main(int argc, char** argv)
{

    srand(time(NULL));
    rand();

    int N = atoi(argv[1]);
    int M = atoi(argv[2]);

    int* arr = (int*)malloc(N * sizeof(int));
    int i;
    for (i = 0; i < N; ++i) {
        arr[i] = ((int)(1000 * (1.0 * rand() / RAND_MAX))) % M;
        printf("%d\n", arr[i]);
    }

    count_sort(arr, 0, N - 1, M);
    if (is_sort(arr, N))
        printf("sorted\n");
    else
        printf("not sorted");

    free(arr);
    return 0;
}

Answer 1

问题出在这几行:

    for (i = l; i <=r; ++i) {
        b[cnt[a[i]]] = a[i];            
        printf("%d\n", b[cnt[a[i]]]);
        ++cnt[a[i]];
    }

您想递减 cnt[a[i]]，而不是递增，并且您还想在赋值之前执行此操作 b[cnt[a[i]]] = a[ i];，不是之后。

通过这些修改，代码可以正常工作。