Python 计数排序实现的算法？

计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于待排序元素为整数的场景，且元素取值范围相对较小。计数排序通过统计每个元素出现的次数，然后根据元素出现的次数将元素放到正确的位置上。

以下是一个使用 Python 实现的计数排序算法：

def counting_sort(arr):
    # 确定待排序数组的最大值和最小值
    max_val = max(arr)
    min_val = min(arr)

    # 计算待排序数组元素的取值范围
    range_val = max_val - min_val + 1

    # 初始化计数数组
    count_arr = [0] * range_val

    # 统计每个元素出现的次数
    for num in arr:
        count_arr[num - min_val] += 1

    # 累加计数
    for i in range(1, range_val):
        count_arr[i] += count_arr[i - 1]

    # 根据计数数组将元素放到正确的位置上
    output_arr = [0] * len(arr)
    for num in arr:
        output_arr[count_arr[num - min_val] - 1] = num
        count_arr[num - min_val] -= 1

    return output_arr

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)  # 输出: [1, 2, 2, 3, 3, 4, 8]

在这个实现中，我们首先找到待排序数组的最大值和最小值，然后计算元素的取值范围。接着，我们初始化一个计数数组，并统计每个元素出现的次数。然后，我们累加计数，使得计数数组中的每个元素都表示小于等于该元素值的元素个数。最后，我们根据计数数组将元素放到正确的位置上，得到排序后的数组。

需要注意的是，计数排序算法只适用于待排序元素为整数的场景，且元素取值范围相对较小。如果元素取值范围较大，那么计数数组的大小也会很大，可能会导致空间复杂度过高。此外，计数排序算法也是稳定的，即相同元素在排序后的相对位置不会改变。