1、记数排序
概念：
简述：将整个数组中的各个数据的个数数出来，然后讲这些数据重新填入原数组中
将要排序的数组先遍历一遍，选出最大的和最小的，以max-min+1(左闭右闭区间)为范围range
intmin=arr[0],max=arr[0];//这里很巧妙，以arr[0]作为min和max，可以解决排序负数的问题for(inti=0;i<n;i++){if(arr[i]>max)max=arr[i];if(arr[i]<min)min=arr[i];}以range为数组大小开一个数组count，将数组中的数据全都初始化为0,
这里存在一个问题：我们难道要将0到max的值全部开出来吗
答：不是，我们采用“相对值”的方法（即将数据储存在相对于最小值的位置）
intrange=max-min+1;int*count=(int*)calloc(range,sizeof(int));//nullptr判断if(nullptr==count){perror("calloc fail");}我们再将原数组中的数据中的每个数据的个数统计出来
for(inti=0;i<n;i++){count[arr[i]-min]++;}然后将count中的数依次填入原数组
intj=0;for(inti=0;i<range;i++){while(count[i]-->0){arr[j++]=i+min;}}实现：
voidCountSort(int*arr,intn){intmin=arr[0],max=arr[0];//这里很巧妙，以arr[0]作为min和max，可以解决排序负数的问题for(inti=0;i<n;i++){if(arr[i]>max)max=arr[i];if(arr[i]<min)min=arr[i];}intrange=max-min+1;int*count=(int*)calloc(range,sizeof(int));if(nullptr==count){perror("calloc fail");return;}for(inti=0;i<n;i++){count[arr[i]-min]++;}intj=0;for(inti=0;i<range;i++){while(count[i]-->0){arr[j++]=i+min;}}}分析：
时间复杂度：O(N+range)
空间复杂度：O(range)
这使得记数排序适合排序数的大小范围较集中的数据
（当然，数据量足够大的时候这个方面的影响会减弱）
2、基数排序
太废了，不做进一步了解
3、桶排序
太废了，不做进一步了解
在这里插入图片描述
