计数排序，排序数组的索引为0

Question

我有一个关于计数排序算法的问题。我正在阅读它，并在一个例子中一步一步地分析了它的代码，但我不认为我理解了一个小细节。如果我理解正确的话，为了让算法工作，你根本不应该使用排序数组的索引0，或者只是算法的这个实现，不使用它？

下面是实现的示例：

/*Lets say that we have the following array initialized,
  k is the maximum value and n is the length of the array*/
int A[] = {4,5,1,3,7};
    k = 7;
    n = 5;

void Counting_sort(int A[], int k, int n)
{   
    /*C is the count array and B is the sorted array*/
    int i, j;
    int B[n], C[k+1];
    for(i = 0; i <=  k; i++)
        C[i] = 0;

    for(j = 0; j < n; j++)
        C[ A[j] ] = C[ A[j] ] + 1;

    for(i = 1; i < k+1; i++)
        C[i] = C[i] + C[i-1];

    for(j = 0; j < n; j++) {
        B[ C [ A [j] ] ] = A[j];
        C[ A[j] ] = C[ A[j]] - 1;
    }
    //so in this loop I must always traverse from 1 to <= n and leave the Index 0?
    for (i = 1; i <= n; i++)
        cout << B[i] << endl;
}

所以我只是在问这是不是一个很好的例子，为了让Counting排序起作用，排序后的数组的大小始终是原始数组的+1，索引0不会被修改？

Answer 1

您的实现中有一个bug；即，您将B初始化为大小为n，但随后寻址Bn。

无论如何，如果您想从B中的索引0开始，那么您需要更改：

B[ C[Aj]]= Aj；

至

B[ C[Aj]-1]= Aj；

和您的后续for循环

for (i = 1；i< n；i++)

在B中从索引1开始的原因是，您将最小的元素放在索引中，等于要放置的元素剩余数量的计数-也就是说，最小的最后一个元素放在索引1中。