根据伪代码实现计数排序但会产生段错误

Question

我已经根据其伪代码(即 written on the blackboard in this video explanation )实现了计数排序，但由于某些神秘的原因，它似乎无法正常工作。

每次运行此函数时，都会出现段错误，尽管理论上它应该可以工作。

我的问题是:我想知道为什么下面的代码会给出段错误作为输出。

void counting(int * array, int n){

    int *copy, *out, i,j, max, counter;

    out = (int*) malloc(sizeof(int) * n );

    max = array[0];


    // Find maximum value in main array and make a copy array of the same size
    for(i=0;i<n;++i) if(array[i] > max) max = array[i]; 
    copy = (int*) malloc(sizeof(int) * (max+1));


    // initialize copy array
    for(i=0;i<max;++i) copy[i] = 0;

    // count how often each value occurs
    for(i=0;i<n;++i) ++copy[array[i]];


    // perform cumulative sum over the array
    for(i=1;i<max;++i) copy[i] += copy[i-1];

    // sort
    for(i=n-1;i>=1;--i){
        out[copy[array[i]]] = array[i];
        --copy[array[i]];
    }

    // free memory
    free(copy);
    free(out);

    // copies end result to original array
    // for(i=0;i<n;++i) array[i] = out[i];

}

Answer 1

两个 for 循环都应该运行到最大值，而不是 max-1。

以下更改应该会有所帮助。

    for(i=0;i<=max;++i) copy[i] = 0;

    // count how often each value occurs
    for(i=0;i<n;++i) ++copy[array[i]];


    // perform cumulative sum over the array
    for(i=1;i<=max;++i) copy[i] += copy[i-1];

希望对您有帮助!