计数排序是一种非基于比较的排序算法。当输入值的范围与元素数量相比较小时，它的效率极高。其核心思想在于统计每个元素出现的次数，然后利用这些计数来确定每个元素在有序输出中的正确位置。
计数排序的工作原理
- 找出输入数组中的最大元素。
- 初始化一个大小为 max + 1 的 countArray，并将所有值初始化为零。
- 统计输入数组中每个元素的出现频率，并将其存储在 countArray 对应的索引处。
- 例如：如果数字 2 出现了两次，则 countArray[2] = 2。
- 将 countArray 转换为前缀和，此时每个索引处的值表示该元素在最终有序序列中的位置。
- 通过从后向前遍历输入数组来构建输出数组（为了保持稳定性）。
- 将输出数组复制回输入数组。
算法步骤
- 创建一个计数数组 "countArray[max(input)+1]" 并初始化为 0。
- 遍历 inputArray 中的每个元素，并增加 countArray[element] 的值。
- 计算 countArray 中的前缀和。
- 创建一个大小为 N 的空数组 outputArray。
- 从后向前遍历输入数组，将每个元素放置在 countArray[element] – 1 的位置。
- 每次放置后，递减 countArray[element] 的值。
Python
def countSort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
output = [0] * len(arr)
for num in arr:
count[num] += 1
for i in range(1, len(count)):
count[i] += count[i – 1]
for num in reversed(arr):
output[count[num] – 1] = num
count[num] -= 1
for i in range(len(arr)):
arr[i] = output[i]
return arr
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = countSort(arr)
print("Sorted array is:", sorted_arr)
**输出**
CODEBLOCK_c0329eaa
****代码解析：****
- ****count[num] += 1: ****增加每个数字的计数，以记录其在列表中出现的次数。
- ****count[i] += count[i - 1]:**** 更新计数数组，使得每个位置存储的是小于或等于该索引的元素总数（即前缀和）。
- ****output[count[num] - 1] = num:**** 利用累加计数将每个数字放置在其正确的排序位置上。
- ****count[num] -= 1:**** 减少计数值，以便当遇到相同的数字时，能将其正确地放置在前一个位置。
- ****arr[i] = output[i]: ****将排序好的输出数组复制回原始数组。
## 使用 collections.Counter 实现计数排序
传统的计数排序通过手动计数并使用数组构建前缀和。而 Python 的 collections.Counter 提供了一种更简单的方法来达到同样的结果，它能自动统计元素的频率。
逻辑保持不变：
- 统计每个元素出现的次数。
- 根据计数值按顺序排列元素。
使用 Counter，我们可以跳过繁琐的数组操作，直接通过遍历排序后的键来重建有序输出。
Python
CODEBLOCK_f902d2ca
from collections import Counter
def count_sort(arr):
count = Counter(arr)
res = []
for num in sorted(count.keys()):
res += [num] * count[num]
return res
arr = [4, 2, 2, 8, 3, 3, 1]
sort_arr = count_sort(arr)
print( sort_arr)
CODEBLOCK_433a00b3
输出
[1, 2, 2, 3, 3, 4, 8]
代码解析：
- Counter(arr): 自动计算每个数字的出现次数。
- sorted(count.keys()): 获取排序后的唯一值列表。
- [num] count[num]:* 根据计数重复每个数字，生成该数字对应的列表片段。
相关文章：
> – 快速排序算法
> – 插入排序算法