计数排序算法中元素的递减计数
计数排序算法中元素的递减计数
提问于 2013-09-21 19:56:07
我用伪码实现了一个计数排序算法。在伪码中，最后一个循环在第一次遍历后减少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;
}回答 1
Stack Overflow用户
回答已采纳
发布于 2013-09-21 20:25:28
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次
准备职位增量取决于它们之前的元素数量：
0 -1
1 -3
元素在新(排序)数组中的位置现在为(计数- 1)：
0的位置=1-1=0
第一1的位置=3-1=2
第二1的位置=2-1=1
让它成为0 1 1。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18936955
复制相关文章
相似问题
腾讯云开发者
