数据结构自学Day15 -- 非比较排序--计数排序

一、计数排序（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;
}

三、计数排序优缺点

四、应用场景：

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

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

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

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