数据结构——lesson13排序之计数排序
前面我们学习过七种排序——直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序和归并排序，它们都是通过两数之间进行比较来排序的，今天我们就来学习非比较排序中的计数排序🥳🥳🥳
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.结语
计数排序的关键在于理解并运用它的思想， 以上就是计数排序的介绍与实现啦~，完结撒花 ~🥳🥳🎉🎉🎉