我用伪代码实现了一个计数排序算法。在伪代码中,最终循环在第一遍之后递减 C[A[j]]
。这是将所有内容都向右移动,所以我在第一次通过之前调试并递减以产生正确的结果。但我看不出除了它有效之外的原因,为什么我必须在之前而不是之后递减。
这是我递减之后的结果:
10 1 0 6 8 3 2 0 9 4
0 0 0 1 2 3 4 6 8 9
当我之前递减时:
10 1 0 6 8 3 2 0 9 4
0 0 1 2 3 4 6 8 9 10
很明显,因为一开始所有东西都向右移动,所以我把所有东西都向左移动了一个,但为什么它一开始就没有正确对齐呢?
int* counting_sort(int A[], int size, int k)
{
int* B = new int[size];
int* C = new int[k+1];
for(int i = 0; i <= k; i++)
C[i] = 0;
for(int j = 0; j < size; j++) {
C[A[j]]++;
}
for(int i = 1; i <= k; i++) {
C[i] += C[i-1];
}
//print(C,k+1);
for(int j = size-1; j >= 0; j--) {
B[--C[A[j]]] = A[j];
}
delete [] C;
return B;
}
最佳答案
for(int j = size-1; j >= 0; j--) {
B[--C[A[j]]] = A[j];
}
相当于:
for(int j = size-1; j >= 0; j--) {
int element = A[j];
int pos = C[element] - 1;
B[pos] = element;
C[element]--;
}
想象数组1 0 1
.现在元素的计数如下:
0
- 1 次
1
- 2 次p>
位置的准备根据它们之前的元素数量递增计数:
0
- 1
1
- 3
新(已排序)数组中元素的位置现在是(计数 - 1):
0
的位置= 1 - 1 = 0
第一名1
= 3 - 1 = 2
第二名1
= 2 - 1 = 1
制作 0 1 1
.
关于c++ - 递减计数排序算法中元素的计数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18936955/