基本思想参考代码图示
回到顶部
基本思想
假设数序列中小于元素a的个数为n，则直接把a放到第n+1个位置上。当存在几个相同的元素时要做适当的调整，因为不能把所有的元素放到同一个位置上。计数排序假设输入的元素都是0到k之间的整数。
回到顶部
参考代码
#include <stdio.h>
void COUNTINGSORT(
int *A,
int *B,
int array_size,
int k)
{
int C[k+
1], i, value, pos;
for(i=
0; i<=k; i++
)
{
C[i] =
0;
}
for(i=
0; i< array_size; i++
)
{
C[A[i]] ++
;
}
for(i=
1; i<=k; i++
)
{
C[i] = C[i] + C[i-
1];
}
for(i=array_size-
1; i>=
0; i--
)
{
value =
A[i];
pos =
C[value];
B[pos-
1] =
value;
C[value]--
;
}
}
int main()
{
int A[
8] = {
2,
5,
3,
0,
2,
3,
0,
3}, B[
8], i;
COUNTINGSORT(A, B, 8,
5);
for (i=
0; i<=
7; i++
)
{
printf("%d ", B[i]);
}
printf("\n");
return 0;
}
回到顶部
图示
对于数据2 5 3 0 2 3 0 3程序执行的过程如下图所示：
现在有个问题，若必须是0到n的自然数，是不是用途很小？我想了想，其实可以任意整数的，即找出最小的数来，看看与0的距离d,把所有的数同时减去d,划到0到n的范围内，计数排序。到最后待恢复就可以了
