計數排序根據僞執行，但不正常運行

Question

根據其僞我已經實現計數排序（這是written on the blackboard in this video explanation），但對於某些神祕的原因，它似乎並不正確排序。

對於測試輸入：10 9 8 7 6 5 4 3 2 1

它給出：3 4 5 6 7 8 1 0 0 9

這似乎是一個非常簡單的問題，但我無法弄清楚爲什麼會發生這種情況。

void counting(int * array, int n){ 

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

    copy = (int*) malloc(sizeof(int) * max); 

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

    max = array[0]; 

    // finds max size 
    for(i=0;i<n;++i) if(array[i] > max) max = array[i]; 

    // zeroes the counting array 
    for(i=0;i<max;++i) copy[i] = 0; 

    //counts 
    for(i=0;i<n;++i) ++copy[array[i]]; 

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

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

    //overwrite original array with sorted output 
    for(i=0;i<n;++i) array[i] = out[i]; 

} 

Answer 1

的問題是在其中分配計數器的陣列的順序：當你寫

copy = (int*) malloc(sizeof(int) * max); 

的max沒有被設置，那麼它的值是未定義的。因此，分配產生不確定的行爲，使你的程序無效。

你需要移動分配過去，計算max循環。分配max+1項目，因爲數組索引是從零開始：

int max = array[0]; 
for(i=0;i<n;++i) 
    if(array[i] > max) 
     max = array[i]; 
copy = malloc(sizeof(int) * (max+1)); 

您還需要free都copy和out末，以避免內存泄漏：

free(copy); 
free(out);