编辑
哈喽大家好，我是保护小周ღ，本期为大家带来的是排序算法中的计数排序，非常的有意思，值得学习而且计数排序是非交换排序，分享所有源代码，粘贴即可运行，保姆级讲述，包您一看就会，快来试试吧~
编辑
目录
一、计数排序
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。[1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）
——百度百科
1.1 算法思想：
编辑
其实会发现一个主要问题，那么就是tmp数组（使用动态开辟）到底应该开辟多大的空间，怎么计算。
假设我们有组数据，100 101 102 101 109 105 105；
我们应该开辟多大的空间，因为最大值是109，从0开始需要开辟110个空间吗？那太浪费了。
编辑
所以我们只需要最大值-最小值+1的空间，max=109,min=100 , max-min+1=10；使用相对映射的位置。
编辑
1.2 程序设计
第一步：
我们自定义一个函数CountSort();将计数排序的功能实现一下，参数有数组a的地址（我们用指针接收，数组名其实就是地址），另一个参数是：计算数组a里有多少个元素，标准操作为：
sizeof ( a ) / sizeof ( a[ 0 ] );
第二步：
我们要在函数内部计算数组a里元素的最大值和最小值（遍历），然后求出数据的范围 range=max - min +1;
第三步：
定义动态开辟的数组tmp,因为我已经得到数据有多少，我们就可以开辟了。
但是我们又想要将tmp数组里的值初始化为0；
博主的方式是直接使用calloc();开辟，calloc() 与 malloc() 函数是一样的功能，只是 calloc() 的函数参数表达方式略有不同，其次是它会将动态开辟的空间值初始化为0；
还有一种方法是使用 memset()函数，menset(tmp, 0 , sizeof( int ) * range );这几个参数应该能理解吧？
只要是动态开辟的空间，我们用完之后一定要随手将它释放掉，就像打括号 { } 一样，可以先写着，避免遗忘。将free（tmp）；放到代码最后即可。
第四步：
统计数组a里的每个元素出现的次数，然后映射至tmp数组。（使用相对映射）；
第五步：
将tmp数组里不为0的元素的下标+min反赋给数组a,遍历结束，排序完成。
1.3 程序实现：
voidCountSort(int*a, intn) { intmax=a[0]; intmin=a[0]; for (inti=0; i<n; ++i)//遍历找打最大值和最小值 { if (a[i] >max) { max=a[i]; } if (a[i] <min) { min=a[i]; } } intrange=max-min+1;//计算范围int*tmp= (int*)calloc(range, sizeof(int));//动态开辟if (tmp==NULL)//如果空间申请失败，报个错，并中止程序 { perror("calloc"); return; } for (inti=0; i<n; ++i)//统计数组a每个元素出现的次数 { tmp[a[i] -min]++; } intj=0; for (inti=0;i<range;++i)// { while (tmp[i])//判断tmp数组该元素是否有计数。 { a[j++] =i+min;//如果有就把该元素的下标值反映射至数组atmp[i]--; } } //动态开辟的空间，主动释放free(tmp); tmp=NULL; } //打印voidPrint(int*a,intn) { for (inti=0;i<n;++i) { printf("%d ",a[i]); } } intmain() { inta[] = {-1,1,2,9,8,8,1,3,4,3,4,5}; CountSort(a, sizeof(a) /sizeof(a[0]));//计数排序Print(a, sizeof(a) /sizeof(a[0]));//打印return0; }
编辑
1.4 计数排序总结
计数排序：思想很巧妙，适用范围具有局限性(整型数据)
时间复杂度：O(N+range);非常块，但是数据范围很大的就差些，说明它适用于范围集中一组整型数据排序。
空间复杂度：O(range);
至此计数排序的算法思想博主已经分享完了，相信大家对这个逻辑有了一定的理解，大家可以自己动手敲敲代码，感受一下。
编辑
本期收录于博主的专栏——排序算法，适用于编程初学者，感兴趣的朋友们可以订阅，查看其它“常见排序”。 排序算法_保护小周ღ的博客-CSDN博客
感谢每一个观看本篇文章的朋友，更多精彩敬请期待：保护小周ღ *★,°*:.☆(￣▽￣)/$:*.°★*
文章存在借鉴，如有侵权请联系修改删除！
编辑
