-4

所以长话短说，我正在尝试为向量实现计数排序。我的代码中某处有一些错误，尽管我认为我已经非常严格地遵循了伪代码。

功能：

void csort(vector<int>& a, vector<int>& b)
{
   vector<int> c(a.size());

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

伪代码：

let C[k] be a new array
 for i = 0 to k
 C[i] = 0
 for j = 1 to A:length
 C[A[j]]  = C[A[j]] +1
 for i = 1 to k
 C[i] = C[i]+  C[i-1] 
 for j = A:length downto 1
 B[C[A[j]]]  = A[j] 
C[A[j]]  = C[A[j]] -1
4

2 回答 2

3

The code as it is is very unreadable and error prone. In any case, what I first saw is that in the snippet below you will access c[-1] at the first iteration, thus incurring in undefined behaviour.

for (int i = 0; i <= c.size(); i++)
{
    c[i] += c[i-1]; // Evaluation of c[i-1] is illegal for i == 0
}
于 2013-04-26T16:06:42.283 回答
1 
for(int i = a.size(); i < 1; i--)

这段代码根本不起作用。

for j = A:length downto 1

↑ 要实现这个伪代码，你应该这样做

for(int i(a.size()-1);i>=0;--i)

对于这样的代码（c[a[i]]），如果a[i]<0或a[i]>=c.size()

于 2013-04-26T17:35:31.163 回答