【数据结构】计数排序的原理及实现

👦个人主页：Weraphael
✍🏻作者简介：目前正在准备26考研
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章有啥瑕疵，希望大佬指点一二
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注😍

一、计数排序的介绍

计数排序和基数排序一样，是一种非比较排序算法，它的基本思想是：

1. 统计输入数据中每个元素出现的次数。
2. 然后根据这些计数信息将元素按顺序放置在正确的位置。最后数组就有序了。

算法思想非常简单，如果还有不理解的话可以看看下面的算法流程。当然也建议看看，因为编写代码的基础都是来源于它~

二、算法流程

比方说序列a = [4, 2, 2, 5, 3, 3, 1]，要求通过计数排序将原序列排位升序

如果按照以上序列的话，计数数组至少要开原数组中的最大值 + 1。因为我们要保证原序列的每个元素在计数数组中都能映射到相应的位置。并且，计数数组的每一个位置都要初始化为0。

接下来就要统计原数组中每个元素出现的个数并映射到计数数组中

最后，根据计数数组的信息，将元素按照顺序从左往右填充回原数组

看到这里，我相信你已经完全理解了计数排序。但接下来需要处理一些细节问题。

比方说，当序列为a = [1000, 1001, 3000, 4000]。难道你的计数数组还需要开原数组中的最大值 + 1，即4001个吗？这不妥妥的浪费空间！所以，我们其实仅需开[1000, 4001)即可。因此，计数数组的空间大小是由原数组中的最大值和最小值来决定的。（注：计数数组大小 = 最大值 - 最小值 + 1）

• 映射数组元素到计数数组的位置不再是countArr[a[i]]++，而是countArr[a[i] − min_val]++。（减去偏移量即可将元素值转化为计数数组中的索引）
• 同理，因为计数数组的下标已经不对应原序列的元素值了。因此，当我们根据这些计数信息将元素按顺序放置在正确的位置时，即遍历计数数组时，是需要通过当前下标 + min_val即可以得到原数组的值。

三、代码实现

// 计数排序
void count_Sort(int a[], int n)
{
    // 数组只有一个数或者没有，就没必要排序了
    if (n < 2) return; 

    // 1. 确定计数数组的大小（获取原序列的最大值和最小值）
    int max_val = a[0], min_val = a[0];
    for (int i = 1; i < n; i++)
    {
        if (a[i] > max_val)
        {
            max_val = a[i];
        }
        if (min_val > a[i])
        {
            min_val = a[i];
        }
    }

    // 2. 为计数数组开辟空间
    // 范围是 max_val - min_val + 1
    int range = max_val - min_val + 1;
    // calloc默认会将空间全部初始化为0
    int* countArr = (int*)calloc(range, sizeof(int)); 

    // 3. 统计原数组每个元素出现的个数, 并映射到计数数组中
    for (int i = 0; i < n; i++)
    {
        countArr[a[i] - min_val]++;
    }

    // 4. 遍历计数数组，将结果写会原数组
    int index = 0;
    for (int i = 0; i < range; i++)
    {
        while (countArr[i]--)
        {
            a[index] = i + min_val;
            index++;
        }
    }
    // 排完序后别忘了释放内存空间~
    free(countArr);
}

【输出结果】

四、时空复杂度分析

• 确定计数数组的大小时，遍历了一遍原序列。因此时间复杂度是O(n)

• 统计原数组每个元素出现的个数, 并映射到计数数组中，时间复杂度还是O(n)

• 遍历计数数组，时间复杂度是O(max_val - min_val + 1)，记作为O(k)

加起来的话就是T(n) = O(n) + O(n) + O(k)。因此，计数排序的时间复杂度就是O(n + k)。注意O(k)不能舍弃，如果原序列存在非常大的元素，那么计数排序的空间复杂度O(k)可能会变得非常高，近似O(n^2)，这时计数排序就不适用了。同时也会存在浪费空间的现象。因此，计数排序适用于数据范围较小，数据是整数或可以映射到整数的离散值（如字符、日期等）。主要还是数据范围较小！！！

而空间复杂度就不用说了，就是O(K)。