计数排序（Counting Sort）的详细解释

1. 问题描述

计数排序是一种非比较型整数排序算法。它的基本思想是通过统计每个元素出现的次数，然后根据统计信息将元素放回正确的位置。计数排序适用于输入数据范围较小（例如0到k）的整数排序，且当k = O(n)时，排序时间为线性。

关键特点：

• 时间复杂度：O(n + k)，其中n是元素个数，k是数据范围。
• 空间复杂度：O(n + k)。
• 稳定排序（可以设计为稳定）。
• 只能用于整数排序。

2. 核心思想

计数排序不通过比较元素大小来排序，而是通过以下步骤：

1. 统计频次：遍历数组，统计每个整数出现的次数，存储在计数数组中。
2. 计算位置：将计数数组转换为前缀和数组，此时每个位置的值表示小于等于该元素的个数。
3. 输出有序数组：从后向前遍历原数组，根据前缀和数组确定每个元素在输出数组中的位置，确保排序的稳定性。

3. 详细步骤

假设输入数组为 arr，长度为n，元素范围是 [0, k]。

步骤1：统计频次

创建一个长度为 k+1 的计数数组 count，初始化为0。
遍历 arr，对每个元素 arr[i]，执行 count[arr[i]]++。

示例：

arr = [4, 2, 2, 8, 3, 3, 1]
k = 8
count数组下标：0 1 2 3 4 5 6 7 8
统计后count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
（表示：0出现0次，1出现1次，2出现2次，3出现2次，4出现1次，8出现1次）

步骤2：计算前缀和

将 count 数组转换为前缀和数组，使得 count[i] 表示小于等于i的元素个数。
具体操作：count[i] += count[i-1]，从i=1到k。

接上例：

原count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
计算前缀和：
i=1: count[1] = 0+1 = 1
i=2: count[2] = 1+2 = 3
i=3: count[3] = 3+2 = 5
i=4: count[4] = 5+1 = 6
i=5: count[5] = 6+0 = 6
i=6: count[6] = 6+0 = 6
i=7: count[7] = 6+0 = 6
i=8: count[8] = 6+1 = 7
最终前缀和count = [0, 1, 3, 5, 6, 6, 6, 6, 7]
解释：小于等于1的元素有1个，小于等于2的有3个，...

步骤3：输出有序数组

创建一个输出数组 output，大小与 arr 相同。
从后向前遍历 arr（保证稳定性）：

• 对于 arr[i]，查找 count[arr[i]] 的值，这个值就是 arr[i] 在输出数组中的位置（注意：位置是从1开始计数的，实际索引要减1）。
• 将 arr[i] 放入 output[count[arr[i]] - 1]。
• 将 count[arr[i]] 减1。

接上例：
遍历 arr = [4,2,2,8,3,3,1] 从后向前：

1. i=6, arr[6]=1, count[1]=1 → output[0]=1, count[1]变为0
2. i=5, arr[5]=3, count[3]=5 → output[4]=3, count[3]变为4
3. i=4, arr[4]=3, count[3]=4 → output[3]=3, count[3]变为3
4. i=3, arr[3]=8, count[8]=7 → output[6]=8, count[8]变为6
5. i=2, arr[2]=2, count[2]=3 → output[2]=2, count[2]变为2
6. i=1, arr[1]=2, count[2]=2 → output[1]=2, count[2]变为1
7. i=0, arr[0]=4, count[4]=6 → output[5]=4, count[4]变为5

最终 output = [1, 2, 2, 3, 3, 4, 8]

4. 稳定性分析

为什么从后向前遍历保证稳定性？
因为当相同元素出现多次时，从后向前遍历确保后出现的相同元素被放在后面位置（由于每次放入后 count 值减1，相同元素的前一个会被放在更前位置），从而保持了原始相对顺序。

5. 时间与空间复杂度

• 时间复杂度：O(n + k)
  统计频次 O(n)，计算前缀和 O(k)，输出有序数组 O(n)。当 k = O(n) 时，为线性时间。
• 空间复杂度：O(n + k)
  需要输出数组 O(n) 和计数数组 O(k)。

6. 适用场景与限制

适用：

• 数据范围小（k 不大）的非负整数。
• 需要稳定排序且时间要求严格。

限制：

• 只能用于整数。
• 数据范围大时，空间消耗大。

7. 示例代码（Python）

def counting_sort(arr, k):
    n = len(arr)
    count = [0] * (k + 1)
    output = [0] * n
    
    # 统计频次
    for num in arr:
        count[num] += 1
    
    # 计算前缀和
    for i in range(1, k + 1):
        count[i] += count[i - 1]
    
    # 从后向前构建输出数组
    for i in range(n - 1, -1, -1):
        num = arr[i]
        output[count[num] - 1] = num
        count[num] -= 1
    
    return output

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

8. 思考与扩展

• 如果数据范围包含负数：可以通过整体加偏移量，将所有数变为非负，排序后再减回去。
• 与桶排序的关系：计数排序是桶排序的一种特例，每个桶只放一个数值。
• 实际应用：经常作为基数排序的子过程。