计数排序详解及Python实例演示

计数排序（Counting Sort）是一种​​非比较型​​的整数排序算法，通过统计元素出现的次数来实现排序，​​时间复杂度为 O(n + k)​​（k 是数据范围），特别适合​​数据范围小但数量大​​的整数排序。下面从原理到代码详细讲解：

​​一、计数排序的核心思想​​

1. ​​统计频率​​：
   统计每个整数在数组中出现的次数，存入一个计数数组 count。

2. 例如：数组 [4, 2, 2, 8, 3, 3, 1] 的 count 数组为 [0, 1, 2, 2, 1, 0, 0, 0, 1]（下标 0~8）。

3. ​​累加计数​​：
   将 count 数组中的值累加，表示​​小于等于当前数字的元素个数​​。

4. 上述 count 变为 [0, 1, 3, 5, 6, 6, 6, 6, 7]（即 ≤8 的元素有 7 个）。
5. 这个小于等于不是小于等于元素 是小于等于这个索引值

6. ​​反向填充结果数组​​：
   从原数组末尾开始遍历，根据 count 数组确定元素在结果数组中的位置，并减少计数（保证稳定性）。（这个反向填充还挺重要的 确保排序的稳定性 这点学习学习）

我们从后往前看 看到1 索引为1的位置的数目是1 显示小于等于它的只有1个 那么它就是最小的 放在最前面

看到3 索引为三的位置 显示个数为2 然后小于等于它的有五个 那么从前往后数从第四个数开始 第四个第五个都是3 以此往下

现在知道这个过程之后我们来写代码（大家应该能看出来统计频率和累加次数这两个数组是有联系的）

class Solution(object):
    def merge(self, nums):
        for i in range(len(nums)):
            Count_A=[0]*(max(nums)+1)
            B = [0] * (max(nums)+1)
            for i in nums:
                if Count_A[i]==0:
                    Count_A[i]=1
                else:
                    Count_A[i]+=1#得到统计有多少个的数组
            for i in range(len(B)):
                B[i]=sum(Count_A[:i+1])
            return Count_A,B
solution=Solution()
result=solution.merge([4, 2, 2, 8, 3, 3, 1])
print(result)

好的 现在我们将统计频率和累加计数两个数组写好了 接下来该如何操作呢？就是反向填充数组（保证稳定性） 每看到一个数 去看小于等于它的有几个 就可以确定填充的起始位置和结束位置了 

class Solution(object):
    def merge(self, nums):
            Count_A=[0]*(max(nums)+1)
            B = [0] * (max(nums)+1)
            for i in nums:
                Count_A[i]+=1#得到统计有多少个的数组
            for i in range(len(B)):
                B[i]=sum(Count_A[:i+1])
            C=[0]*(len(nums))
            for i in range(len(nums)-1,-1,-1):
                num=nums[i]
                if num not in C:
                 m=B[num] - Count_A[num]
                 n=B[num]
                 C[m:n]=[num]*(n-m)#但是已经遇到了
            return C
solution=Solution()
result=solution.merge([4, 2, 2, 8, 3, 3, 1])
print(result)

对于统计频率和累加计数 自己静下心来好好想想 肯定是会写的

我说一下我对于排序的想法 首先是反向填充 倒着来 遇到这个数 看这个数有几个 看有几个小于等于它的 这样我就可以确定填充这个数字的开始位置和起始位置 如果这个数已经在数组中 就不必再管了 这就是我的思路

如果你觉得我的思路可以帮助到你的话，欢迎点赞收藏

您的鼓励是我更新的最大动力！

作者：m0_62653520