基于MIT算法导论实现的Python计数排序仅部分生效原因排查

核心问题成因 #

两处实现细节和《算法导论》的标准计数排序逻辑存在偏差，直接导致输出结果错位：

• 前缀和计算的遍历边界错误。Python的range(a, b)为左闭右开区间，原代码中for i in range(1, k)实际仅遍历i=1到i=k-1的位置，漏掉了i=k的累加计算。按照计数排序逻辑，数组C的C[i]需要存储小于等于i的元素总个数，漏掉最高值的累加后，最大值对应的位置计数会出现偏差。
• 结果数组的索引偏移错误。计数排序中C[x]记录的是值x在有序结果中出现的最后一个位置的下一位（匹配Python 0起始的数组索引规则），写入元素时需要将索引减1才能对应正确位置。原代码直接使用C[A[j]]作为B数组的下标写入，导致所有元素的存储位置整体后移一位。两处错误叠加后，最后遍历到最大值59时，会直接覆盖B数组索引1位置存储的元素2，最终数组头部索引0的位置始终保留初始化的0值，与实际输出完全匹配。

修正方案与可运行代码 #

针对两处偏差调整后，即可得到正确排序结果：

• 将前缀和循环的结束值调整为k+1，确保覆盖到最大值对应的位置完成累加
• 写入结果数组时，将索引调整为C[A[j]] - 1，匹配0起始数组的位置规则

修正后的完整实现：

A = [2, 11, 3, 6, 9, 20, 11, 32, 45, 47, 52, 59]
B = [0] * len(A)

k = max(A)
C = [0] * (k + 1)

# 统计每个数值的出现次数
for j in range(len(A)):
    C[A[j]] += 1

# 计算累计计数，调整后覆盖i=k的位置
for i in range(1, k + 1):
    C[i] = C[i] + C[i-1]

# 写入有序结果，修正索引偏移
for j in range(len(A)):
    B[C[A[j]] - 1] = A[j]
    C[A[j]] -= 1

print(B)

修正后运行输出为：[2, 3, 6, 9, 11, 11, 20, 32, 45, 47, 52, 59]，符合预期排序结果。

内容的提问来源于stack exchange，提问作者PeterPefi