Python 排序算法：计数排序（Counting Sort）

# /*
# Python 排序算法：计数排序（Counting Sort）
# --------------------------------------------------------
# 概念：
# 计数排序是一种线性时间的非比较排序算法，
# 特别适合数据范围较小、值为整数的序列。
#
# 核心思想：
# 通过统计每个值出现的次数，再累加形成前缀和，
# 根据前缀和数组将元素放入正确位置，从而形成有序序列。
#
# 特点：
# 1) 时间复杂度 O(n + k)，适合大规模整数排序；
# 2) 属于稳定排序；
# 3) 数值范围过大时不适用；
# 4) 需要额外存储计数数组。
# */

# --------------------------------------------------------
# 示例数组
data = [4, 2, 2, 8, 3, 3, 1]

print("原始序列：", data)

# --------------------------------------------------------
# 计数排序函数
def counting_sort(arr):
    if not arr:
        return arr

    # 求最小值与最大值，确定计数数组长度
    min_val = min(arr)
    max_val = max(arr)
    rng = max_val - min_val + 1

    # 创建计数数组
    count = [0] * rng

    # 输出数组
    output = [0] * len(arr)

    # 统计出现次数
    for num in arr:
        count[num - min_val] += 1

    # 计数数组变为前缀和（累加）
    for i in range(1, rng):
        count[i] += count[i - 1]

    # 倒序将元素放入正确位置（保证稳定性）
    for num in reversed(arr):
        count[num - min_val] -= 1
        pos = count[num - min_val]
        output[pos] = num

    return output

# --------------------------------------------------------
# 调用示例
sorted_data = counting_sort(data)

print("计数排序结果：", sorted_data)

# --------------------------------------------------------
# 要点总结：
# 1) 通过计数数组记录每个值出现次数；
# 2) 前缀和确定元素最终位置；
# 3) 倒序放置可确保算法稳定；
# 4) 数据范围固定时效率极高；
# 5) 常用于整数键值的排序场景。
# */

# 原始序列： [4, 2, 2, 8, 3, 3, 1]
# 计数排序结果： [1, 2, 2, 3, 3, 4, 8]