c++ - 对负值使用计数排序？

Question

我有以下代码，但这仅适用于无符号整数，我的目标是编写适用于所有整数的代码...

void CountingSort(vector<int> & a, vector<int> & b)
{
    int k=*max_element(a.begin(),a.end());
    k++;

    vector <int> c(k);

    for (int i=0;i<a.size();i++)
        c[a[i]]++;
    for (int i=1;i<k;i++)
        c[i]=c[i]+c[i-1];
    for (int i=0;i<a.size();i++)
    {
        b[c[a[i]]-1]=a[i];
        c[a[i]]--;
    }
}

我如何更改它以适用于所有整数类型？

Answer 1

从计算最小值和最大值开始:

int k_min=*max_element(a.begin(),a.end());
int k_max=*min_element(a.begin(),a.end());
int k = k_max - k_min + 1;

对以下代码进行一些更改，将 a[i] 替换为 a[i] - k_min；剩下的应该很容易。