c++ - 计数排序中的循环解释

Question

有人可以向我解释一下这个计数排序实现中第二个循环的目的吗？:

short c[RADIX_MAX] = {0};
int i;

for (i = 0; i < LEN_MAX; i++) {
    if (i == len)
        break;
    int ind = a.getElem(i); 
    c[ind]++;
}

for (i = 1; i < RADIX_MAX; i++) {
    if (i == radix)
        break;
    c[i] += c[i - 1];
}

for (i = LEN_MAX - 1; i >= 0; i--) {
    int j = i - LEN_MAX + len;      
    if (j < 0)
        break;
    int ind = a.getElem(j);
    short t = ind;
    ind = --c[ind];
    b.setElem(ind, t);
}

Answer 1

计数排序的工作原理是根据元素本身的值计算每个待排序元素的目标索引。涉及三个 channel :

• 在第一个循环中，每个元素都被计数:例如我们的数组有六个“A”和两个“B”，五个“C”等等。

• 在第二个循环中，计算每个元素所在的索引。如果有六个“A”，那么第一个“B”需要位于索引 6(在基于 0 的索引中)。计数排序做的事情稍微复杂一些，目的是为了让代码更简单，排序更稳定。在第三个循环中，它将以反向顺序遍历原始数组，因此在第二个循环中，它计算的索引不是给定值的第一个实例，而是最后。在我们上面的示例中，最后一个“A”需要出现在索引 5 处，但最后一个“B”需要出现在索引 6 处(“A”s)+ 2(“B”s)- 1(从零开始)= index 7. 因此，对于每个值，它都会计算该值的结束索引。它向前移动计数数组，将先前计算的计数添加到当前计数。所以在我们的计数数组中，“A”的值保持为 6(没有前一个元素)，“B”的值是 6+2=8(六个“A”+两个“B”)，C 的值现在是 6+2+5=13(六个“A”+两个“B”+五个“C”)，依此类推

• 在最后一个循环中，值被插入到它们的位置，随着我们的进行递减索引。因此，最后一个“B”被插入到索引 7 处，前一个“B”插入到索引 6 处，依此类推。这保留了相等元素的原始顺序，使排序稳定，这对于基数排序至关重要。