当按学生的分数或年龄排序时，可以通过统计元素出现的次数来实现。它的核心思想是 “统计频率，按序填充”。我一直不知道有个计数排序（Counting Sort）的说法，所以心里一直迷惑这么简单基础的排序算法怎么没有在书上读到？大学课本上好像没有提到计数排序（Counting Sort），你有没有同感？难道是我读大学时太不认真看书了？
问：我是一个研究生毕业的程序员，请给我解释一下基数排序算法
DeepSeek:
基数排序（Radix Sort）是一种非比较型的整数排序算法，它通过逐位处理数字的每一位来实现排序。基数排序的核心思想是“按位分配，多次收集”，适用于整数或固定格式的字符串排序。以下是详细解释：
核心思想
- 按位排序：从最低位（LSB）到最高位（MSB），依次对每一位进行排序（例如个位、十位、百位等）。
- 稳定性：每次按位排序必须使用稳定排序算法（如计数排序），保证相同数字的相对顺序不变。
算法步骤
- 确定最大位数：找到数组中最大数字的位数（记为 d），决定需要排序的轮数。
- 从低位到高位排序：
- 对每一位（个位、十位、…）执行一次稳定排序（通常用计数排序）。
3. 合并结果：每一轮排序后，数字会根据当前位有序，最终所有位处理完后整体有序。
示例
假设数组为 [170, 45, 75, 90, 802, 24, 2, 66]，步骤如下：
- 最大位数 d=3（802有3位）。
- 按个位排序：
- 分组：[170, 90], [802, 2], [24], [45, 75], [66]
- 合并：[170, 90, 802, 2, 24, 45, 75, 66]
- 按十位排序：
- 分组：[802, 2], [24], [45], [66], [170, 75], [90]
- 合并：[802, 2, 24, 45, 66, 170, 75, 90]
- 按百位排序：
- 分组：[2, 24, 45, 66, 75, 90], [170], [802]
- 合并：[2, 24, 45, 66, 75, 90, 170, 802]（最终有序）
时间复杂度
- 最优/平均/最坏：(O(d \cdot n))，其中 d 是最大位数，n 是元素数量。
- 空间复杂度：(O(n + k))（k 是计数排序的桶大小，通常 k=10 表示十进制数字）。
关键点
- 稳定性要求：每轮排序必须稳定，否则高位排序会破坏低位已排好的顺序。
- 适用范围：适合整数或定长字符串，不适合浮点数或可变长数据。
- 与计数排序的关系：基数排序常利用计数排序作为子过程。
代码实现（Python）
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10 # 0-9的计数器
# 统计当前位的数字出现次数
for num in arr:
digit = (num // exp) % 10
count[digit] += 1
# 计算累加次数（确定输出位置）
for i in range(1, 10):
count[i] += count[i - 1]
# 反向填充（保证稳定性）
i = n - 1
while i >= 0:
num = arr[i]
digit = (num // exp) % 10
output[count[digit] - 1] = arr[i]
count[digit] -= 1
i -= 1
# 将结果拷贝回原数组
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
exp = 1 # 从个位开始
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10 # 处理十位、百位...
# 测试
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("排序后:", arr) # 输出: [2, 24, 45, 66, 75, 90, 170, 802]
为什么有效？
- 低位优先：先处理低位可以逐步细化排序，高位最终决定全局顺序。
- 稳定性保证：相同高位的数字在后续排序中会按低位顺序排列。
基数排序在数据范围不大且位数较少时效率极高（如手机号排序），但在数据范围大时可能不如快速排序等通用算法。
问：那 计数排序 又是怎样的呢？
DeepSeek:
计数排序（Counting Sort）是一种非比较型的整数排序算法，通过统计元素出现的次数来实现排序。它的核心思想是 “统计频率，按序填充”，适用于整数范围较小且已知的情况（如年龄、成绩等）。以下是详细解释：
核心思想
- 统计频率：统计每个元素在数组中出现的次数。
- 计算位置：通过累加频率确定每个元素在有序数组中的最终位置。
- 填充结果：按统计结果将元素放入正确位置，保证稳定性。
算法步骤
- 统计频率：
- 遍历数组，统计每个整数出现的次数，存入计数数组 count。
- 累加频率：
- 对 count 数组进行累加操作，count[i] 表示值小于等于 i 的元素个数。
- 反向填充：
- 从原数组末尾开始遍历，根据 count 数组确定当前元素的位置，放入结果数组，同时减少计数（保证稳定性）。
示例
假设数组为 [4, 2, 2, 8, 3, 3, 1]，范围是 1~8（k=8）：
- 统计频率：
- count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
（索引 0 无用，count[1]=1 表示 1 出现 1 次，count[2]=2 表示 2 出现 2 次，依此类推）
- 累加频率：
- count = [0, 1, 3, 5, 6, 6, 6, 6, 7]
（count[2]=3 表示值 ≤2 的元素有 3 个）
- 反向填充：
- 遍历原数组最后一个元素 1，count[1]=1 → 放入结果索引 1-1=0 的位置，count[1] 减 1。
- 重复过程，最终得到有序数组 [1, 2, 2, 3, 3, 4, 8]。
时间复杂度
- 最优/平均/最坏：(O(n + k))，其中 n 是元素数量，k 是整数范围（如 0~100 则 k=101）。
- 空间复杂度：(O(n + k))（需要结果数组和计数数组）。
关键点
- 适用范围：仅适用于 整数 且 范围较小 的数据（如 0~100）。
- 稳定性：通过反向填充保证相同值的原始顺序不变（对基数排序至关重要）。
- 局限性：若 k 远大于 n（如排序 [1, 1000000]），则空间浪费严重。
代码实现（Python）
def counting_sort(arr):
if not arr:
return arr
max_val = max(arr)
min_val = min(arr)
k = max_val - min_val + 1 # 计算实际范围（优化空间）
# 初始化计数数组
count = [0] * k
output = [0] * len(arr)
# 统计频率
for num in arr:
count[num - min_val] += 1 # 偏移到 0-based
# 累加频率
for i in range(1, k):
count[i] += count[i - 1]
# 反向填充（保证稳定性）
for i in range(len(arr) - 1, -1, -1):
num = arr[i]
pos = count[num - min_val] - 1 # 计算位置
output[pos] = num
count[num - min_val] -= 1
return output
# 测试
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("排序后:", sorted_arr) # 输出: [1, 2, 2, 3, 3, 4, 8]
优化与变种
- 范围偏移：通过 min_val 偏移（如 -100~100 → 0~200），减少 k 的值。
- 负数支持：通过偏移处理负数（如 min_val 为负数时，num - min_val 转为非负）。
- 非整数扩展：需转换为整数（如浮点数乘 10 的幂次转为整数）。
为什么基数排序用计数排序？
基数排序的每一轮需要 稳定地 按某一位排序，而计数排序：
- 是稳定的；
- 时间复杂度 (O(n + k))（k=10 处理十进制位），高效且常数小。
对比其他排序
算法 | 是否比较排序 | 时间复杂度 | 适用场景 |
计数排序 | 否 | (O(n + k)) | 小范围整数 |
快速排序 | 是 | (O(n \log n)) | 通用排序 |
基数排序 | 否 | (O(d \cdot n)) | 定长整数/字符串 |
计数排序是基数排序的基础，理解它有助于掌握更复杂的非比较排序算法！