计数排序（Counting Sort）是一种非基于比较的排序算法，适用于一定范围内的整数排序。它的核心思想是将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

原理：

  1. 找出待排序的数组中最大和最小的元素：这一步是为了确定计数数组的长度，因为计数数组的下标对应待排序数组的元素值，计数数组的长度就是待排序数组元素值的范围（最大值 - 最小值 + 1）。

  2. 统计每个值为i的元素出现的次数，存入计数数组的第i项。

  3. 对所有的计数累加（从计数数组中的第一个元素开始，每一项和前一项相加）。

  4. 反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。

实现：

以下是计数排序的Python实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def counting_sort(arr):
    # 获取数组中的最大值和最小值
    max_val = max(arr)
    min_val = min(arr)
    
    # 初始化计数数组，长度为最大值和最小值的差加1
    count_arr = [0] * (max_val - min_val + 1)
    
    # 统计每个元素出现的次数
    for num in arr:
        count_arr[num - min_val] += 1
    
    # 修改count_arr，使得每个索引对应的值为所有小于等于该索引的数的个数
    for i in range(1, len(count_arr)):
        count_arr[i] += count_arr[i - 1]
    
    # 创建输出数组
    output_arr = [0] * len(arr)
    
    # 从后向前遍历原始数组，将元素放到输出数组的正确位置
    for i in range(len(arr) - 1, -1, -1):
        output_arr[count_arr[arr[i] - min_val] - 1] = arr[i]
        count_arr[arr[i] - min_val] -= 1
    
    return output_arr

# 测试代码
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr))  # 输出: [1, 2, 2, 3, 3, 4, 8]

在这个实现中，我们首先找出数组中的最大值和最小值，然后创建了一个计数数组来记录每个元素的出现次数。接着，我们修改了计数数组，使得每个索引对应的值为所有小于等于该索引的数的个数。最后，我们创建了输出数组，并从后向前遍历原始数组，将元素放到输出数组的正确位置。

注意：

  1. 计数排序的时间复杂度为O(n+k)，其中n是待排序数组的长度，k是整数的范围。因此，当k不是很大时，计数排序是一种非常高效的排序算法。

  2. 计数排序是稳定的排序算法，即相等的元素在排序后保持原有的顺序。

  3. 计数排序要求输入的数据必须是有确定范围的整数，对于浮点数或者范围非常大的整数，计数排序并不适用。

  4. 计数排序的空间复杂度为O(k)，因此如果k很大，计数排序可能会消耗大量的内存空间。