主流排序是通过比较来确定顺序.而线性排序则是通过运算来确定顺序.
计数排序的基本思想:对每一个输入的元素X,确定小于X的元素的个数,从而知道X在数组中的位置
void CouSort(int src[],int des[],int size,int max)
{
int i;
int temp[100] = {0};
for (i = 1; i <= size; i++)
{
temp[src[i]]++;
}
for (i = 1; i <= max; i++)
{
temp[i] += temp[i-1];
}
for (i = 1; i <= size; i++)
{
des[temp[src[i]]] = src[i];
temp[src[i]]--;
}
}输入数据:
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
第一个for循环之后:
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
temp |
0 |
2 |
1 |
0 |
0 |
0 |
1 |
3 |
3 |
0 |
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
temp |
0 |
2 |
3 |
3 |
3 |
3 |
4 |
7 |
10 |
10 |
最后过程如图:
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
2 |
3 |
3 |
3 |
4 |
6 |
10 |
10 |
|
des |
|
|
|
|
|
|
8 |
|
|
|
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
2 |
3 |
3 |
3 |
4 |
5 |
10 |
10 |
|
des |
|
|
|
|
|
8 |
8 |
|
|
|
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
1 |
3 |
3 |
3 |
4 |
5 |
10 |
10 |
|
des |
|
2 |
|
|
|
8 |
8 |
|
|
|
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
0 |
3 |
3 |
3 |
4 |
5 |
10 |
10 |
|
des |
2 |
2 |
|
|
|
8 |
8 |
|
|
|
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
0 |
3 |
3 |
3 |
4 |
5 |
9 |
10 |
|
des |
2 |
2 |
|
|
|
8 |
8 |
|
|
9 |
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
0 |
3 |
3 |
3 |
4 |
5 |
8 |
10 |
|
des |
2 |
2 |
|
|
|
8 |
8 |
|
9 |
9 |
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
0 |
2 |
3 |
3 |
4 |
5 |
8 |
10 |
|
des |
2 |
2 |
3 |
|
|
8 |
8 |
|
9 |
9 |
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
0 |
2 |
3 |
3 |
4 |
5 |
7 |
10 |
|
des |
2 |
2 |
3 |
|
|
8 |
8 |
9 |
9 |
9 |
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
0 |
2 |
3 |
3 |
4 |
4 |
7 |
10 |
|
des |
2 |
2 |
3 |
|
8 |
8 |
8 |
9 |
9 |
9 |
|
下标 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
src |
8 |
8 |
2 |
2 |
9 |
9 |
3 |
9 |
8 |
7 |
|
temp |
0 |
0 |
0 |
2 |
3 |
3 |
3 |
4 |
7 |
10 |
|
des |
2 |
2 |
3 |
7 |
8 |
8 |
8 |
9 |
9 |
9 |
排序完成,