一、计数排序（Counting Sort）

计数排序是一种非比较型的排序算法，它的核心思想是：

利用“元素的值”来确定它在结果数组中的位置，通过“统计每个数出现的次数”来完成排序。

二、如何实现计数排序（核心步骤）

1、设有一个待排序数组 arr，长度为 n，值的范围是 [min, max]。

2、找最大最小值，确定计数数组大小

3. 创建计数数组并统计频次

4. 恢复到原数组（非稳定排序）

思维导图

代码实现

void Count_Sort(int* arr,int size){assert(arr);int min = arr[0];int max = arr[0];for(int i = 1;i<size;i++){if(arr[i]<min){min = arr[i];}if(arr[i]>max){max = arr[i];}}int Range = max-min+1;int index = 0;int* Count_Arr = (int*)calloc(Range,sizeof(int));for(int i = 0;i<size;i++){Count_Arr[arr[i]-min]++;};for(int j = 0;j<Range;j++){while (Count_Arr[j]--){arr[index++] = min+j;}}return;
}

三、计数排序优缺点

四、应用场景：

• 排序范围已知、较小的数据（例如考试成绩、年龄、投票数等）

• 多关键字排序中的一环（如基数排序的子排序）

五、所学习过的排序算法总结

稳定性的介绍：数组中相同值，排完序的相对顺序是否可以做到不变，如果不变就是稳定的，如果会变化就是不稳定的。