编程教程

　　 编程问答　 ACM与蓝桥杯竞赛入门　 C语言教程　 C++教程　 数据结构教程　 Python教程　 JAVA教程　 编译器教程　 C语言函数库　 更多教程
  1. 首页
  2. 教程
  3. 算法竞赛教程
  4. 排序算法

计数排序算法C/C++代码图文讲解

98530 阅读 0 评论

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。


（1）算法的步骤：

1. 找出待排序的数组中最大和最小的元素

2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项

3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1


（2）计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

2. 时间复杂度：O(MAX(N,范围))

3. 空间复杂度：O(范围)

4. 稳定性：稳定 


（3）动图演示：

计数排序


（4）C语言代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
 
//交换数值
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
//打印数组
void printArray(char msg[],int arr[],int len){
    printf("%s:",msg);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
//计数排序(稳定)
void count_sort(int a[],int len){
    //计算出元素最大值和最小值
    int maxvalue=a[0],minvalue=a[0];
    for(int x=0;x<len;x++){
        maxvalue=a[x]>maxvalue?a[x]:maxvalue;
        minvalue=a[x]<minvalue?a[x]:minvalue;
    }
    //算出最大临时数组长度
    int arrlength= maxvalue-minvalue+1;
    //用来存放最终有序数组
    int *arr=(int*) malloc(arrlength * sizeof(int));
    //用于元素计数
    int *temp=(int*) malloc(arrlength * sizeof(int));
    //初始化为0
    for(int k=0;k<arrlength;k++){
        temp[k]=0;
    }
    //temp下标即为数组a[i]相对mivalue值，每次算出对应的temp下标则自增++，遇到相同的元素temp[pos]>1
    for(int i=0;i<len;i++){
        temp[a[i]-minvalue]++;
    }
    printf("元素计数：\n");
    for(int i=0;i<arrlength;i++){
        printf("temp[%d]=%d\n",i+minvalue,temp[i]);
    }
    //使用累加(temp[n]=temp[n]+temp[n-1]，有点类似斐波那契数列)计算出元素所在位置，保证结果有序
    for(int j=1;j<arrlength;j++){
            temp[j]+=temp[j-1];
    }
    printf("元素位置：\n");
    for(int i=0;i<arrlength;i++){
        printf("temp[%d]=%d\n",i+minvalue,temp[i]);
    }
    for(int j=len-1;j>=0;j--){
        //获取a[j]在temp数组的下标
        int pos = a[j]-minvalue;
        //获取元素位置mappos，--temp[pos]：每放一个元素到数组arr，temp[pos]值自减，保证结果稳定有序
        int mappos=(--temp[pos]);
        arr[mappos]=a[j];
    }
    //回填到a数组
    for(int j=0;j<len;j++){
        a[j]=arr[j];
    }
    //释放内存
    free(arr);
    free(temp);
}
int main()
{
    int len=10;
    int arr[len];
    srand((unsigned)time(NULL));
    //随机生成长度为"len"的数组
    for(int i=0;i<len;i++){
        arr[i]=rand()%200;
    }
    printArray("未排序前",arr,len);
    count_sort(arr,len);
    printArray("计数排序：",arr,len);
    //防止windows下控制台窗口闪退
    int s;
    scanf("%d",&s);
    return 0;
}

如果我们编译并运行上述程序，那么它应该产生以下结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
未排序前:149 192 114 163 65 178 72 154 98 112 
元素计数：
temp[65]=1
temp[66]=0
temp[67]=0
temp[68]=0
temp[69]=0
temp[70]=0
temp[71]=0
temp[72]=1
temp[73]=0
temp[74]=0
temp[75]=0
temp[76]=0
temp[77]=0
temp[78]=0
temp[79]=0
temp[80]=0
temp[81]=0
temp[82]=0
temp[83]=0
temp[84]=0
temp[85]=0
temp[86]=0
temp[87]=0
temp[88]=0
temp[89]=0
temp[90]=0
temp[91]=0
temp[92]=0
temp[93]=0
temp[94]=0
temp[95]=0
temp[96]=0
temp[97]=0
temp[98]=1
temp[99]=0
temp[100]=0
temp[101]=0
temp[102]=0
temp[103]=0
temp[104]=0
temp[105]=0
temp[106]=0
temp[107]=0
temp[108]=0
temp[109]=0
temp[110]=0
temp[111]=0
temp[112]=1
temp[113]=0
temp[114]=1
temp[115]=0
temp[116]=0
temp[117]=0
temp[118]=0
temp[119]=0
temp[120]=0
temp[121]=0
temp[122]=0
temp[123]=0
temp[124]=0
temp[125]=0
temp[126]=0
temp[127]=0
temp[128]=0
temp[129]=0
temp[130]=0
temp[131]=0
temp[132]=0
temp[133]=0
temp[134]=0
temp[135]=0
temp[136]=0
temp[137]=0
temp[138]=0
temp[139]=0
temp[140]=0
temp[141]=0
temp[142]=0
temp[143]=0
temp[144]=0
temp[145]=0
temp[146]=0
temp[147]=0
temp[148]=0
temp[149]=1
temp[150]=0
temp[151]=0
temp[152]=0
temp[153]=0
temp[154]=1
temp[155]=0
temp[156]=0
temp[157]=0
temp[158]=0
temp[159]=0
temp[160]=0
temp[161]=0
temp[162]=0
temp[163]=1
temp[164]=0
temp[165]=0
temp[166]=0
temp[167]=0
temp[168]=0
temp[169]=0
temp[170]=0
temp[171]=0
temp[172]=0
temp[173]=0
temp[174]=0
temp[175]=0
temp[176]=0
temp[177]=0
temp[178]=1
temp[179]=0
temp[180]=0
temp[181]=0
temp[182]=0
temp[183]=0
temp[184]=0
temp[185]=0
temp[186]=0
temp[187]=0
temp[188]=0
temp[189]=0
temp[190]=0
temp[191]=0
temp[192]=1
元素位置：
temp[65]=1
temp[66]=1
temp[67]=1
temp[68]=1
temp[69]=1
temp[70]=1
temp[71]=1
temp[72]=2
temp[73]=2
temp[74]=2
temp[75]=2
temp[76]=2
temp[77]=2
temp[78]=2
temp[79]=2
temp[80]=2
temp[81]=2
temp[82]=2
temp[83]=2
temp[84]=2
temp[85]=2
temp[86]=2
temp[87]=2
temp[88]=2
temp[89]=2
temp[90]=2
temp[91]=2
temp[92]=2
temp[93]=2
temp[94]=2
temp[95]=2
temp[96]=2
temp[97]=2
temp[98]=3
temp[99]=3
temp[100]=3
temp[101]=3
temp[102]=3
temp[103]=3
temp[104]=3
temp[105]=3
temp[106]=3
temp[107]=3
temp[108]=3
temp[109]=3
temp[110]=3
temp[111]=3
temp[112]=4
temp[113]=4
temp[114]=5
temp[115]=5
temp[116]=5
temp[117]=5
temp[118]=5
temp[119]=5
temp[120]=5
temp[121]=5
temp[122]=5
temp[123]=5
temp[124]=5
temp[125]=5
temp[126]=5
temp[127]=5
temp[128]=5
temp[129]=5
temp[130]=5
temp[131]=5
temp[132]=5
temp[133]=5
temp[134]=5
temp[135]=5
temp[136]=5
temp[137]=5
temp[138]=5
temp[139]=5
temp[140]=5
temp[141]=5
temp[142]=5
temp[143]=5
temp[144]=5
temp[145]=5
temp[146]=5
temp[147]=5
temp[148]=5
temp[149]=6
temp[150]=6
temp[151]=6
temp[152]=6
temp[153]=6
temp[154]=7
temp[155]=7
temp[156]=7
temp[157]=7
temp[158]=7
temp[159]=7
temp[160]=7
temp[161]=7
temp[162]=7
temp[163]=8
temp[164]=8
temp[165]=8
temp[166]=8
temp[167]=8
temp[168]=8
temp[169]=8
temp[170]=8
temp[171]=8
temp[172]=8
temp[173]=8
temp[174]=8
temp[175]=8
temp[176]=8
temp[177]=8
temp[178]=9
temp[179]=9
temp[180]=9
temp[181]=9
temp[182]=9
temp[183]=9
temp[184]=9
temp[185]=9
temp[186]=9
temp[187]=9
temp[188]=9
temp[189]=9
temp[190]=9
temp[191]=9
temp[192]=10
计数排序：:65 72 98 112 114 149 154 163 178 192


作业：
1497 蓝桥杯算法提高VIP-冒泡排序计数
点赞(70)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

其他教程

Java常见的异常

枚举算法的思想与实例讲解

wxPython(5)-事件管理

域名和主机的选择

编程命名规范之下划线命名法

C语言tmpnam()函数:创建一个唯一的文件名

结合实例浅析构造题型

DataInputStream和DataOutputStream类的常用方法有哪些？

C语言实现彩色贪吃蛇游戏教程及源码

微调定时精确时间

Java实例变量和类变量

Python控制结构详解

归并排序算法实例详解

C语言数组与指针的区别与联系

回文树/回文自动机 (PAM) 实现及模板

打开文件fopen函数的用法

C语言sqrt()函数:计算一个非负实数的平方根

Python文件操作

常用的元字符及其在正则表达式中的写法

什么是栈溢出？

Dotcpp在线编译　 　　　 （登录可减少运行等待时间） 
#include<stdio.h>
int main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX