作者：[柒号华仔]
个人信条：星光不问赶路人,岁月不负有心人。
个人方向：专注于5G领域，同时兼顾其他网络协议，编解码协议，C/C++，linux等，感兴趣的小伙伴可以关注我，一起交流。
1. 计数排序介绍
1.1 定义
计数排序就是一种牺牲内存空间来换取低时间复杂度的排序算法，通过额外申请内存空间，根据统计符合条件的元素个数来确定排序位置。
1.2 基本原理
1.对于一个待排序数组，获取数组的最大值max和最小值min；
2.创建一个长度为max-min+1的计数数组count array，统计每个数值在待排数组中出现的次数，将次数填写到数组count array中，对应下标=数值-min；
3.创建一个输出数组out array，长度与待排序数组长度一致，根据每个元素出现的次数按顺序填写元素到out array，元素数值 = 计数数组下标+min。
例如：对于数组array[20] = {2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,4,6,9,2};进行排序
首先，找出待排数组最大值max = 9，最小值min = 1；
然后建立计数数组countArray[9],统计每个数值出现次数填入countArray
建立输出数组outArray[20],根据元素出现次数按顺序填写:
第一个元素数值为1，出现2次，因此outArray[0]=1,outArray[1]=1;
第二个元素数值为2，出现7次，因此outArray[2]~outArray[8]均等于2；
第三个元素数值为3，出现2次，因此outArray[9]=3,outArray[10]=3;
第四个元素数值为4，出现2次，因此outArray[11]=4,outArray[11]=4;
第五个元素数值为5，出现0次;
第六个元素数值为6，出现2次，因此outArray[12]=6,outArray[13]=6;
第七个元素数值为7，出现2次，因此outArray[14]=7,outArray[15]=7;
第八个元素数值为8，出现2次，因此outArray[16]=8,outArray[17]=8;
第九个元素数值为9，出现2次，因此outArray[18]=9,outArray[19]=9;
1.3 时间复杂度和空间复杂度
计数排序是非比较排序，时间复杂度是O(n+k)，空间复杂度是O(k)。
1.4 优缺点
优点：在对一定范围内的整数排序时，它的复杂度为O(n+k)，快于任何比较排序算法。
缺点：如果最大值和最小值相差非常大，元素数值分布间隔比较大，所申请额外内存空间很大，会造成空间浪费。
2. 代码实现
#include <stdio.h>
#include <string.h>
void printArray(int array[], int size)
{
int i;
for (i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
int countSort(int array[],int arrayLen)
{
int max,min,countLen;
int i,j;
max = array[0];
min = array[0];
for(int i = 1; i < arrayLen; i++) {
if (array[i] > max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
countLen = max - min + 1;
int countArray[countLen];
memset(countArray,0,sizeof(countArray));
for(i = 0;i<countLen;i++){
for(j = 0;j<arrayLen;j++){
if(array[j] == i+min)
countArray[i]++;
}
}
j = 0;
for (i=0; i<countLen; i++)
{
while (countArray[i] > 0)
{
array[j] = i + min;
j++;
countArray[i]--;
}
}
}
int main(int argc, char **argv) {
int array[] = {2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,4,6,9,2};
countSort(array,sizeof(array)/sizeof(int));
printArray(array, sizeof(array)/sizeof(int));
return 0;
}运行结果：
1 1 2 2 2 2 2 2 2 3 3 4 4 6 7 7 8 8 9 9
