0

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

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);
}
4

2 回答 2

1

计数排序的工作原理是根据元素本身的值计算要排序的每个元素的目标索引。涉及三种通行证：

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

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

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

于 2013-04-08T20:06:02.793 回答
1

对于每个数字，我们计算它在排序数组中开始的索引。示例：
array: 0 0 0 0 2 2 3 3 3 9 9
index: 0 1 2 3 4 5 6 7 8 9 10
然后 c[0] = 0, c[1] = 4, c[2] = 4, c[3] = 6, c[4] = 9, ... c[9] = 9
。数字出现的排序数组取决于前一个数字的索引和前一个数字的数量。第二个循环计算这个。

于 2013-04-08T20:54:55.190 回答