💞💞 前言
hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
前面我们学习过七种排序——直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序和归并排序，它们都是通过两数之间进行比较来排序的，今天我们就来学习非比较排序中的计数排序🥳🥳🥳
1.计数排序
基本思想：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
我们这里利用malloc开辟一个数组来统计相同元素出现的次数，用该数字下标表示相同元素，下标对应的值来统计次数
图示如下：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> void CountSort(int* a, int n) { //开辟数组 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } //将tmp数组的值初始化为0 for (int i = 0; i < n; i++) { tmp[i] = 0; } //遍历a for (int i = 0; i < n; i++) { //tmp下标对应值要++ tmp[a[i]]++; } //拷贝回元素组a int j = 0;//记录a下标 for (int i = 0; i < n; i++) { while (tmp[i]--) { a[j++] = i; } } free(tmp); } int main() { int a[] = { 1,3,3,9,7,5,8,7,6 }; printf("排序前："); for (int i = 0; i < 9; i++) { printf("%d ", a[i]); } printf("\n"); CountSort(a, 9); printf("排序后："); for (int i = 0; i < 9; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
结果如下：
🥲我们仔细观察发现我们开辟tmp数组的大小是n：
int* tmp = (int*)malloc(sizeof(int) * n);
而数组a里面有九个数，也就是tmp大小为9，下标最大也就是8，那么当a中出现比8大的数9时应该怎么计数呢？就不可以计数了，所以出错了；
✨✨那么我们应该开辟多大的数组呢？应该根据什么来开辟才可以呢？
根据a数组最大最小值之差来开辟好像可以，a数组之间的范围就可以作为判断标准；但是这次我们得考虑得全面一点，如果a数组是这样得：a[] = {45,43,36,50,49,44,47}这些呢？那我们岂不是要开辟50个int大小的数组才可以有这么大的下标，如果是考虑范围就是最大50-最小36 = 14，更不可以了；
✨✨解决办法：
利用相对值，还是开辟最大-最小的范围大小数组，然后最后拷贝数据的时候让下标+最小的数即可：
代码如下：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> void CountSort(int* a, int n) { //求a数组最大最小差的范围 int small = a[0]; int big = a[0]; for (int i = 1; i < n; i++) { //求最大值 if (a[i] > big) { big = a[i]; } //求最小值 if (a[i] < small) { small = a[i]; } } //范围 int gap = big - small; //比如0~4，差就是4，但是对应开辟的大小得是5，0~4有五个数 //开辟数组 int* tmp = (int*)malloc(sizeof(int) * (gap+1)); if (tmp == NULL) { perror("malloc fail"); return; } //将tmp数组的值初始化为0 for (int i = 0; i < gap+1; i++) { tmp[i] = 0; } //遍历a for (int i = 0; i < n; i++) { //tmp下标(a数组对应值-small)对应值要++ tmp[a[i]-small]++; } //拷贝回元素组a,记得+samll int j = 0;//记录a下标 for (int i = 0; i < gap+1; i++) { while (tmp[i]--) { a[j++] = i + small; } } free(tmp); } int main() { int a[] = { 1,3,3,9,7,5,8,7,6 }; printf("排序前："); for (int i = 0; i < 9; i++) { printf("%d ", a[i]); } printf("\n"); CountSort(a, 9); printf("排序后："); for (int i = 0; i < 9; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
结果如下：
当int a[] = {45,43,36,50,49,44,47}时结果如下：
可以发现，计数排序成功啦~🥳🥳🥳
2.计数排序复杂度分析
2.1空间复杂度
我们根据上述代码实现可以知道计数排序开辟了大小为gap的数组，而gap对应的是最大与最小值的差也就是范围，所以其空间复杂度应该为O(gap);
2.2时间复杂度
时间复杂度：
①求数组a最大最小值时遍历了一遍数组a，次数为n；
②初始化tmp数组为0时遍历了数组tmp，次数为gap；
③统计下标出现次数时遍历数组a，次数为n；
④拷贝回原数组时，遍历了数组tmp，次数为gap；
所以其时间复杂度应该是n+gap+n+gap,简化为O(n+gap);
3.计数排序缺陷分析
前面我们学习的七大排序，时间复杂度最好也要O(n*logn);
而计数排序时间复杂度却可以达到O(n);
俗话说金无足赤，人无完人；计数排序达到这么好的时间复杂度其对应的缺陷也是非常明显的：
💥 缺陷1：依赖数据范围，适用于范围集中的数组
💥 缺陷2：只能用于整形（因为使用数组下标来统计）
所以计数排序使用的条件是非常苛刻的
4.结语
计数排序的关键在于理解并运用它的思想， 以上就是计数排序的介绍与实现啦~，完结撒花 ~🥳🥳🎉🎉🎉
