为什么我的countsort无法将元素放入dst[0]？

Question

这是一个计数排序的函数，我是按照课本写的，有问题 dst[0] 是一个随机数，但它应该是 0；然而，0出现在dst[1]中，2出现在dst[2]中……最后8出现在dst[9]中； 好像有偏差，但不知道偏差在哪里

#include<stdio.h>
#include<malloc.h>

//count sort;
/*arr: pointer to array, ifas: index of start, ifae: index of end, nfs: number of start, nfe: number     of end*/ 
int* countsort(int* arr, int ifas, int ifae, int nfs, int nfe){
    int * ap = (int*)malloc(sizeof(int) * (nfe - nfs + 1)), tmp;
    int * dst = (int*)malloc(sizeof(int) * (ifae - ifas + 1));
    for(tmp = 0; tmp <= nfe - nfs; tmp++){
        ap[tmp] = 0;
    }
    for(tmp = ifas; tmp <= ifae; tmp++){
        ap[arr[tmp] - nfs]++;
    }
    
    for(tmp = 1; tmp <= nfe - nfs; tmp++){
        ap[tmp] += ap[tmp-1];
    }
    for(tmp = 0; tmp <= 9; tmp++){
        printf("%d ", ap[tmp]);
    }
    printf("\n");
    for(tmp = 0; tmp <= 9; tmp++){
        printf("%d ", arr[tmp]);
    }
    printf("\n");
    for(tmp = ifae - ifas; tmp >= 0; tmp--){
        dst[ap[arr[tmp] - nfs]] = arr[tmp];
        ap[arr[tmp]-nfs] = ap[arr[tmp]-nfs] - 1;
    }
    for(tmp = 0; tmp <= 9; tmp++){
        printf("%d ", dst[tmp]);
    }
    printf("\n");
    free(ap);
    return dst;
}

int main(){
    int arr[10] = {9,5,3,8,0,1,6,4,7,2};
    int* res = countsort(arr,0,9,0,9);
}

如果有人能找到错误的位置，我将不胜感激。

Answer 1

在此循环中：

    for(tmp = ifae - ifas; tmp >= 0; tmp--){
        dst[ap[arr[tmp] - nfs]] = arr[tmp];
        ap[arr[tmp]-nfs] = ap[arr[tmp]-nfs] - 1;
    }

对

dst

和

ap

的分配顺序错误。与Wikipedia中的算法相比，它有：

    for i = length(input) - 1 down to 0 do
        j = key(input[i])
        count[j] = count[j] - 1
        output[count[j]] = input[i]

您的

ap

数组对应于伪代码中的

count

，您需要在分配给输出之前而不是之后递减计数。这就是结果中所有内容都减 1 的原因。