python计数算法-爱代码爱编程

计数算法（Counting Sort）是一种线性时间复杂度的排序算法，适用于数据范围小但值分布比较集中的场景。

算法思想：

统计待排序数组中每个元素出现的次数；
将统计结果累加，得到每个元素在排序数组中的位置；
遍历待排序数组，将元素放置到相应的位置上；
将排序结果输出。

def counting_sort(arr):
    # 找到数组中最大值和最小值
    min_val, max_val = min(arr), max(arr)
    # 统计每个元素出现的次数
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[num - min_val] += 1
    # 计算每个元素在排序数组中的位置
    for i in range(1, len(count)):
        count[i] += count[i-1]
    # 构建排序数组
    res = [0] * len(arr)
    for num in arr:
        res[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    return res

算法分析：

时间复杂度：计数算法的时间复杂度为O(n+k)，其中n为待排序数组的长度，k为待排序数组中元素的取值范围；

空间复杂度：计数算法的空间复杂度为O(k)。

需要注意的是，计数算法要求待排序数组中的元素都是非负整数，如果出现负数或者小数，需要对算法进行相应的修改。