计数排序是一种简单高效的排序算法，它属于非比较型排序算法，特别适用于整数排序，尤其是当数据的取值范围不大时。相比于冒泡排序、选择排序等基于比较的排序算法，计数排序通过统计元素出现的次数来确定元素的最终位置，从而实现排序，时间复杂度可以达到线性级别（O(n + k)，其中n是待排序元素的个数，k是数据的取值范围）。
基本思路¶
- 确定数据范围：首先找出待排序数组中的最小值和最大值，这样我们就能确定需要统计的元素范围，避免创建过大的计数数组。
- 统计元素出现次数：创建一个计数数组，长度为（最大值 - 最小值 + 1），用于记录每个元素出现的次数。
- 构建排序结果：根据计数数组的统计结果，从最小值开始，依次输出每个元素，输出的次数等于该元素在计数数组中记录的次数。
示例演示¶
以数组 [4, 2, 2, 8, 3, 3, 1] 为例，演示计数排序的过程：
- 确定数据范围：数组中的最小值是
1，最大值是8，因此数据范围是1~8，计数数组长度为8 - 1 + 1 = 8。 - 统计元素次数：遍历原数组，统计每个元素出现的次数：
- 元素1出现 1 次
- 元素2出现 2 次
- 元素3出现 2 次
- 元素4出现 1 次
- 元素8出现 1 次
- 其他元素（5、6、7）出现 0 次
因此计数数组为[1, 2, 2, 1, 0, 0, 0, 1]（索引 0~7 分别对应 1~8 的次数）。 - 构建排序结果：从最小值
1开始，依次输出计数数组中每个元素的次数：
- 输出1一次 →[1]
- 输出2两次 →[1, 2, 2]
- 输出3两次 →[1, 2, 2, 3, 3]
- 输出4一次 →[1, 2, 2, 3, 3, 4]
- 输出8一次 →[1, 2, 2, 3, 3, 4, 8]
Python 实现¶
def counting_sort(arr):
# 处理空数组或单元素数组（无需排序）
if not arr:
return []
if len(arr) == 1:
return arr
# 步骤1：确定最小值和最大值
min_val = min(arr)
max_val = max(arr)
# 步骤2：创建计数数组（长度为最大值-最小值+1，初始化为0）
count_size = max_val - min_val + 1
count = [0] * count_size
# 步骤3：统计每个元素出现的次数
for num in arr:
# 计算当前元素在计数数组中的索引（元素值 - 最小值）
index = num - min_val
count[index] += 1 # 对应元素出现次数+1
# 步骤4：根据计数数组生成排序结果
sorted_arr = []
for i in range(count_size):
# 当前元素值 = 最小值 + 计数数组索引
num = min_val + i
# 将当前元素重复 count[i] 次添加到结果数组
sorted_arr.extend([num] * count[i])
return sorted_arr
代码解释¶
- 边界处理：如果输入数组为空或只有一个元素，直接返回原数组（无需排序）。
- 数据范围确定：通过
min()和max()获取数组的最小值和最大值，避免创建过大的计数数组。 - 计数数组构建：长度为
max_val - min_val + 1，确保覆盖所有可能的元素。 - 统计次数：遍历原数组，对每个元素计算其在计数数组中的索引（
num - min_val），并累加次数。 - 生成结果：从最小值开始，按顺序输出每个元素，输出次数由计数数组中对应位置的值决定。
适用场景与特点¶
- 适用场景：数据为整数且取值范围较小（如考试分数、年龄等），或存在大量重复元素时。
- 稳定性：计数排序是稳定排序（相等元素的相对顺序在排序后保持不变），因为重复元素会按原顺序依次输出。
- 内存占用：若数据范围过大（如最大值远大于最小值），计数数组会占用较多内存，此时可能不适用。
测试示例¶
# 测试用例1：基础整数数组
arr1 = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr1)) # 输出：[1, 2, 2, 3, 3, 4, 8]
# 测试用例2：包含负数的数组
arr2 = [-3, 1, 2, -3, 0]
print(counting_sort(arr2)) # 输出：[-3, -3, 0, 1, 2]
通过上述步骤，计数排序能高效地对整数数组进行排序，尤其适合数据范围小且重复元素多的场景。